[Python-3000] ordered dict for p3k collections?
jimjjewett at gmail.com
Wed Sep 26 17:35:15 CEST 2007
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.)
More information about the Python-3000