[Python-3000] ordered dict for p3k collections?

[Jim Jewett]

On 9/26/07, Guido van Rossum <guido at python.org> wrote:
> On 9/26/07, Mark Summerfield <mark at qtrac.eu> wrote:

> > Assuming you have a good sorteddict implementation ...
> > you can gain significant performance benefits.

> ... sorted dict implementation, the best performance you can get for
> random access and random insertions is O(log N), which is always beat
> by the O(1) of a hash table

It is possible to keep two structures in parallel, so that lookup
(using the hash) is still O(1) and traversal (using the tree) is still
O(N); the penalty is that you pay for both methods when you do a
mutation.  (In big O notation, that doesn't matter, but the overhead
may be important in practice.)

-jJ