11
$\begingroup$

Bug introduced in 10.0.2 and fixed in 10.2


The 10.0.2 Dataset type system complication breaks a recursive trie constructor that worked in 0.1:

byPrefix = Query[ 
   GroupBy[First],
   If[First@# == {}, First@Keys@#, byPrefix[#]] &,
   Rest]; 

Test on FDA NDC product dataset ~4k sorted nonproprietary drug names:

drugNames = {"levetiracetam", "prednisone", "lamotrigine", 
    "alprazolam", "amlodipine besylate", "amoxicillin", 
    "diltiazem hydrochloride", "bupropion hydrochloride", 
    "topiramate", "quetiapine fumarate", "carvedilol"} // 
   AssociationMap[{"SOS"}~Join~ Characters[#]~Join ~ {"EOF"} & ] // 
  Dataset

Then,

drugNames[byPrefix]

warns:

enter image description here

Element with head Association is not of the form _String

but the normal form is OK:

drugNames[byPrefix] // Normal

enter image description here

It's not just a warning, it breaks lookup, even though note All Keys are String, not composite as implicated in this 10.0.2 bug:

drugNames[byPrefix]["SOS", Keys] or drugNames[byPrefix]["SOS", "p"] raise msg:

Cannot take part ... of expression of the form _String

while, again, with normal form workaround:

drugNames[byPrefix] // Normal // Dataset // Query["SOS", Keys]

{"l", "p", "a", "d", "b", "t", "q", "c"}

The normal form of an expression should be the same as the normalizing twice. That's violated here.

EDIT // Timing study

Although this question is not about performance, adding a basic benchmark to address comments, which also reveals another consequence of this bug for StringLength > 146:

randomTestWord[len_] :=  
  RandomChoice[
    CharacterRange["a", "z"], {len}] // <|StringJoin[#] -> #|> &;

Using

randomWordData[len_, n_] := 
  Table[randomTestWord[len], {n}] // Association // Dataset;

test along two axes: by array length fixing StringLength = 8

words8Test = 
  Range[100, 1000, 100] // AssociationMap[ randomWordData[8, #] &] // 
   Dataset;

and by StringLength = {2, 4, 8, 16, 32, 64, 128} fixing array length = 100:

words100Test = 
  2^Range[7] // AssociationMap[makeDataset[#, 100] &] // Dataset;

Both look linear in input:

words8Test[All, First @ AbsoluteTiming @ byPrefix[#]&]  
words100Test[All, First @ AbsoluteTiming @ byPrefix[#]&]  

enter image description here enter image description here

BTW, another aspect of this bug:

randomTestWord[145] // Dataset // Query[byPrefix]  (* ok *)

But longer strings:

randomTestWord[146] // Dataset // Query[byPrefix] // Normal
(* ... <|"m" -> <|"c" -> <|"j" -> <|"b" -> <|"h" -> <|"j" -> <|"b" -> <|"s" \
-> <|"l" -> <|"r" -> <|"i" -> <|"x" -> <|"i" -> <|"k" -> <|"g" -> \
<|"z" -> <|"u" -> 
                    Dataset`Query`PackagePrivate`query[<|\
"elhhqbrjgenygqvgmlnnksmttunqfwbsgfifnhmxhirrybnrziyzodaboabnycxhawjsf\
ydvzrkfokuvekhoofakpatqijqvocuauicuvhgqoliqyhntxyyjuwitbhpdmcjbhjbslri\
xikgzue" -> {"e"}|>]|>|> ... *)
$\endgroup$
  • $\begingroup$ Are you certain this worked properly in 10.0.1? It seems to just hang for me there. $\endgroup$ – Stefan R Dec 31 '14 at 22:03
  • $\begingroup$ @StefanR The code functions under 10.0.1 but it exhibits exponential time complexity with respect to string length. If you trim the strings to (say) the first eight characters, then the code terminates in a reasonable amount of time. $\endgroup$ – WReach Dec 31 '14 at 23:14
  • $\begingroup$ @WReach, can you validate the exponential time complexity? That would not change from 10.0.1 to .2. Take a look at the timing studies I added, can you try larger parameters? $\endgroup$ – alancalvitti Jan 1 '15 at 19:44
  • $\begingroup$ @StefanR, yes it worked in 10.0.1. $\endgroup$ – alancalvitti Jan 1 '15 at 19:45
  • $\begingroup$ @alancalvitti I can confirm that the exponential time complexity occurs for the original code in 10.0.1 but not 10.0.2. I ran it again just now. randomTestWord[145] returns immediately on 10.0.2 but runs indefinitely in 10.0.1. randomTestWord[146] runs indefinitely for me in both versions. I can replicate your results for words8Test and words100Test in both versions. I suppose that they dodge the exponential behaviour as they do not nest queries. Note: I assumed that makeDataset[#, 100] in words100Test should actually be randomWordData[100, #]. $\endgroup$ – WReach Jan 1 '15 at 21:49
11
$\begingroup$

There appears to be a bug in the type inference mechanism here. If you evaluate

<<Dataset`
<<TypeSystem`

and then

res = drugNames[byPrefix];
res // GetType

(* Assoc[Atom[String], Atom[String], AnyLength] *)

which is bogus. Basically that says it thinks the result is an Association with keys and values that are both String. We can compare this to the correct type:

Dataset[Normal[res]] // GetType

(*Assoc[Atom[String], 
 Assoc[Atom[String], 
  Assoc[Atom[String], 
   Assoc[Atom[String], 
    Assoc[Atom[String], 
     Assoc[Atom[String], 
      Assoc[Atom[String], 
       Assoc[Atom[String], 
        Assoc[Atom[String], 
         Assoc[Atom[String], 
          Assoc[Atom[String], Assoc[Atom[String], AnyType, 1], 1], 1],
          1], 1], 1], 1], 1], AnyLength], AnyLength], 8], 1] *)

Perhaps the type inference code isn't quite sure what to do with recursive functions like byPrefix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.