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

[Sean DALY]

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 if that would
be in the running performancewise.

Sean


On Sun, Jun 7, 2009 at 3:39 PM, Benjamin M.
Schwartz<bmschwar at fas.harvard.edu> wrote:
> 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
>
>