Creations Posts ID:136544
 ID:136544   Aug 19 2002, 4:23 pm Just wondering what the practical limit was on an associative list. I am using a text-keyed list each entry of which will contain a 0 or 1. Also, is there a special way to declare such a list as to contain only a bit value to save on memory?
 #1 Aug 19 2002, 9:33 pm 65535 is the magic number for limits. I'm not sure about storing anything smaller than an integer or text though.
 #2 Aug 20 2002, 5:07 am In response to ACWraith (#1) ACWraith wrote: 65535 is the magic number for limits. I'm not sure about storing anything smaller than an integer or text though. I'm not sure if you're making a generalization here (2^16-1 being a popular number), or if you know about the number of entries in a associative list specifically. There may be some schema involved here that limits it in a much greater fashion. Not to mention, theoretical and actual numbers usually vary.
 #3 Aug 20 2002, 4:13 pm In response to Skysaw (#2) I'm not sure if you're making a generalization here (2^16-1 being a popular number), or if you know about the number of entries in a associative list specifically. There may be some schema involved here that limits it in a much greater fashion. Not to mention, theoretical and actual numbers usually vary. If you retrieve elements frequently, there could be some minor slowdown -- I believe Dan once said that the elements of an associative list are stored as a binary tree, which would mean it could take up to 16 samples to fetch a given element. (I think that's the maximum -- I don't remember much about binary trees, though, so allow for a margin of error of 65519 samples.)
 #4 Aug 20 2002, 4:36 pm In response to Gughunter (#3) I'm assuming this is about your dictionary library. So, I'd say divide the words into 26 lists depending on what their first letter is. var/list/words = list("A"=list(), "B"=list()) //and so on... Then check the first letter of the word that you're either checking or adding, and search or place it into the appropriate list. For example, if the first word is Carrot, stick it in words["C"]. That way, if you have 65535 words, you only have to search through lists of roughly 2500. That, and you're 26 times less likely to ever hit the list contents limit.
 #5 Aug 20 2002, 9:43 pm In response to Skysaw (#2) Skysaw wrote: ACWraith wrote: 65535 is the magic number for limits. I'm not sure about storing anything smaller than an integer or text though. I'm not sure if you're making a generalization here (2^16-1 being a popular number), or if you know about the number of entries in a associative list specifically. There may be some schema involved here that limits it in a much greater fashion. Not to mention, theoretical and actual numbers usually vary. My testing has so far revealed it to be a rumor. I'm going to go enjoy the larger limit and ponder where the heck I heard that rumor while I pound my head in for repeating it. Bye. *clunk*
In response to Gughunter (#3)
I believe Dan once said that the elements of an associative list are stored as a binary tree, which would mean it could take up to 16 samples to fetch a given element.

That's only true in a nice perfect binary tree. Butmost of the time the tree will be degenerate and have a larger max up to the number of items in the list if it's worst case scenario. Example being:
 ```Worst CaseA \ B \ C \ D \ E \ F \ GBest Case D / \ B F / / \ A C E G ```

As you can see the worst case scenario for a binary tree is a sorted list, and the best case is as unsorted as possible :). But chances are your max won't be log2(numItems).
 #7 Aug 21 2002, 9:57 am In response to Theodis (#6) Actually, associative lists are implemented as red-black trees, which means they remain nearly balanced and you can count on O(log(N)) behavior. Lists in general can contain up to 2^32 (4 billion) entries, but you will run into memory problems long before then. Also, associative lists will generally run into a 2^16 (65535) limit, because the number of unique text strings, datum objects, and so-forth, are each limited by that number. I am planning on increasing these limits sometime soon, especially if they are causing problems. As for memory usage concerns, there is no simple way to make it take advantage of your single-bit storage requirements. If you could find a way of grouping entries together such that the key value for 16 different entries all overlapped, then you could make them share the same bit-flag value in the list, each one assigned to a different power of 2. If this doesn't fit your situation too well, I wouldn't bother. --Dan
 #8 Aug 21 2002, 10:10 am In response to Dan (#7) Thanks for the info, that was very helpful. I am of course interested in the proposed limit increase, but I shouldn't run up against the wall any time soon.