[Sugar-devel] I'm looking for a tree...
lucian.branescu at gmail.com
Sun Jun 7 10:56:43 EDT 2009
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
> I was hoping for a structure with log-time performance.
> Sugar-devel mailing list
> Sugar-devel at lists.sugarlabs.org
More information about the Sugar-devel