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 <bmsch...@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@lists.sugarlabs.org > http://lists.sugarlabs.org/listinfo/sugar-devel > >
_______________________________________________ Sugar-devel mailing list Sugar-devel@lists.sugarlabs.org http://lists.sugarlabs.org/listinfo/sugar-devel