curl == Friedger [EMAIL PROTECTED] writes:
What would be the most efficient data structure with respect to
speed? There is 1GB ram available.
I assume you main operation is checking for set membership?
I would use {Set-of String}. Is it efficient to insert an
element abc to a set of strings containing 134.999 elements?
Yes, our container classes are all quite scalable.
Set.member? and Set.insert are O(1) (amortized). The size of the
Set's representation doubles when it get gets too full (as does
Array's, HashTable's, etc). So a specific insert might be slow if it
has to reallocate the underlying arrays, but if you do the math it's
still O(1) on average, this this happens less and less often as the
size gets larger.
If you know the exact size the Set will be, it can be useful
to use the 'efficient-size' keyword argument when you create it.
If your set of strings were fixed and set membership were the critical
operation, you could investigate perfect hash algorithms (sorry, no
help for you in our API), but I seriously doubt it's worth the effort.
-Mat
***
To unsubscribe from this list, send a mail to:
mailto:[EMAIL PROTECTED]
To contact a human list administrator, send a mail to:
mailto:[EMAIL PROTECTED]
To recieve a list of other options for this list, send a mail to:
mailto:[EMAIL PROTECTED]
