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

[James Zaki]

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