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

[James Zaki]

Hey Benjamin,

Taking a guess with the information you've given perhaps a hash
table<http://en.wikipedia.org/wiki/Hash_table>could help?

Fast lookup/retrieval, but just have to consider what you would enumerate as
the key, and loading.

Let me know if you want some help applying this, memories of a uni
assignment have just come flooding back.


James.



2009/6/7 Benjamin M. Schwartz <bmschwar at fas.harvard.edu>

> I am looking for a fast data structure with the following properties:
>
> Maintains an indexed list of arbitrary, non-ordered objects (like a python
> List or C array)
> Allows fast:
> Insertion at any location
> Deletion at any location
> Lookup of an object by its index
> Reverse lookup, to determine the index of an object
>
> Python's List has O(1) lookup, but O(N) insert, delete, and
> reverse-lookup.  To make reverse lookup O(1) I could maintain a separate
> Dict mapping objects to indices, but this would cost an additional O(N) on
> every insertion and deletion.
>
> A linked list has O(1) insertion and deletion, but O(N) lookup and O(N)
> reverse lookup.  I could maintain a separate Dict for the forward and
> reverse mappings, but this would cost O(N) on every insertion and deletion.
>
> A standard self-balancing tree cannot be used because the objects are not
> ordered, and self-balancing trees require ordered keys.  I could use the
> index of an object as the sort key, but then insertion and deletion are
> O(N) because all subsequent keys must be altered.  I could fabricate new
> sort keys to ensure that insertions occur at the desired location, but
> then the length of the keys will grow like O(N), making all operations at
> least O(N).
>
> I feel like there should be some kind of standard tree-like data structure
> that meets my requirements, but I can't find one.  Do you know of one?  Am
> I on a unicorn hunt?
>
> --Ben
>
>
> _______________________________________________
> Sugar-devel mailing list
> Sugar-devel at lists.sugarlabs.org
> http://lists.sugarlabs.org/listinfo/sugar-devel
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.sugarlabs.org/archive/sugar-devel/attachments/20090607/6e7fea11/attachment.htm