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

Ben, Perhaps try communicating the problem you're trying to solve with the data structure. ie, what you're storing, what would you be looking for when searching stored objects... This would yield better advice, and share information within the context of sugar. James. 2009/6/8 Benjamin M. Sch

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

I've had amazing difficulty communicating what I'm looking for here. Those closest thing is http://en.wikipedia.org/wiki/Rope_(computer_science) A rope is a binary tree that _imposes_ an ordering on its leaves that has nothing whatsoever to do with their values (the values are essentially opaque

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

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

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

Benjamin M. Schwartz writes: > 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

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

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/ No, an ordered dictionary is not enough. All these ordered dictionaries are ordered e

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

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/ 2009/6/7 Benjamin M. Schwartz : > Lucian Branescu wrote: >> This http://www.python.org/dev/peps/pep-0372/ might be

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

hash chaining only approaches order n if the table is very full (because of collisions). On Sun, Jun 7, 2009 at 8:07 AM, Benjamin M. Schwartz < bmsch...@fas.harvard.edu> wrote: > Lucian Branescu wrote: > > This http://www.python.org/dev/peps/pep-0372/ might be interesting. > > Perhaps it could ge

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

Lucian Branescu wrote: > This http://www.python.org/dev/peps/pep-0372/ might be interesting. > Perhaps it could get backported to 2.5. > > But it still has O(n) deletion. It also doesn't have insertion at all (only append), and indexing (and reverse indexing) is O(n). --Ben signature.asc Desc

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

This http://www.python.org/dev/peps/pep-0372/ might be interesting. Perhaps it could get backported to 2.5. But it still has O(n) deletion. 2009/6/7 Benjamin M. Schwartz : > James Zaki wrote: >> Taking a guess with the information you've given perhaps a hash >> table

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

Have you looked into an awk associative array? I understand it is stored internally as a hash table. I remember reading about a simulated multidimensional array (index,subscript); inserting a record in that case didn't involve any reindexing. Older awks were considered slow though, I have no idea

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

James Zaki wrote: > Taking a guess with the information you've given perhaps a hash > tablecould help? Python uses the term "Dict" to describe its built-in hash table. I do think a hash table could be helpful, for example, to maintain the reverse lookup ma

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

Hey Benjamin, Taking a guess with the information you've given perhaps a hash tablecould 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

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

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