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

[Lucian Branescu]

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 <bmschwar at fas.harvard.edu>:
> James Zaki wrote:
>> Taking a guess with the information you've given perhaps a hash
>> table<http://en.wikipedia.org/wiki/Hash_table>could 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 mapping if the forward lookup is stored in a List (which is
> actually python's version of a dynamic array, like C++'s Vector).
> However, I am still stuck with O(N) performance in this case for insertion
> and deletion, because each such modification shifts the position of all
> subsequent objects.  This would correspond to changing the value
> associated with half the keys in the hash table, on average, for each
> insertion.
>
> I was hoping for a structure with log-time performance.
>
> --Ben
>
>
> _______________________________________________
> Sugar-devel mailing list
> Sugar-devel at lists.sugarlabs.org
> http://lists.sugarlabs.org/listinfo/sugar-devel
>
>