Not sure if you have found an answer to this yet, but with more information about what you're trying to do could help with communicating the right solution. Again I think a hash table can answer your questions about fast-lookup, but it just depends your chosen key, and other requirements you might have about sorting.
If its not too sugar specific, feel free to contact me directly. Regards, James. 2009/6/7 Benjamin M. Schwartz <bmsch...@fas.harvard.edu> > Lucian Branescu wrote: > > Would an ordered dictionary otherwise be all right, or am I > > misunderstanding your requirements? There are other implementations, > > like > > http://www.xs4all.nl/~anthon/Python/ordereddict/<http://www.xs4all.nl/%7Eanthon/Python/ordereddict/> > > No, an ordered dictionary is not enough. All these ordered dictionaries > are ordered either by time or by sorting the keys. Neither will work for > me. The problem is simple: if I insert something at position 5, I need > the object currently at position 5 to move to position 6, and the object > currently at position 6 to move to position 7, etc. > > To accomplish this in an time-ordered odict, I would have to remove all > keys subsequent to the insertion point, make the insertion, and then > re-insert those keys. That's O(n). > > To accomplish this in a sorted-order odict, I would have to generate a new > key that causes my insertion to occur at the right location. If there are > repeated insertions at the same location, generating such keys becomes an > O(n) operation. To see this, suppose I am repeatedly inserting at the > second position. Initially, the keys are (0,1). The first insertion has > to pick a key between 0 and 1, e.g. 0.5. The second insertion has to pick > a key between 0 and 0.5: e.g. 0.25. The number of bits required to store > these keys to sufficient precision increases by one bit on each insertion. > This means that the length of the keys is O(n), so every comparison is > O(n). > > --Ben > >
_______________________________________________ Sugar-devel mailing list Sugar-devel@lists.sugarlabs.org http://lists.sugarlabs.org/listinfo/sugar-devel
