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

[Benjamin M. Schwartz]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: OpenPGP digital signature
Url : http://lists.sugarlabs.org/archive/sugar-devel/attachments/20090607/f82dc981/attachment-0001.pgp