[Sugar-devel] I'm looking for a tree...

James Zaki james.zaki at gmail.com
Mon Jun 8 06:14:21 EDT 2009


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 <bmschwar at 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.sugarlabs.org/archive/sugar-devel/attachments/20090608/7a0430b4/attachment.htm 


More information about the Sugar-devel mailing list