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?
ID:136544
 Aug 19 2002, 2:23 pm
|
|
ACWraith wrote:
65535 is the magic number for limits. 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. | |
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.) | |
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. | |
Skysaw wrote:
ACWraith wrote: 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* | |
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 Case 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). | |
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 | |
I'm not sure about storing anything smaller than an integer or text though.