[Python-3000] ordered dict for p3k collections? (original) (raw)
Jim Jewett jimjjewett at gmail.com
Wed Sep 26 17:35:15 CEST 2007
- Previous message: [Python-3000] ordered dict for p3k collections?
- Next message: [Python-3000] ordered dict for p3k collections?
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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
- Previous message: [Python-3000] ordered dict for p3k collections?
- Next message: [Python-3000] ordered dict for p3k collections?
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]