[Python-3000] ordered dict for p3k collections? (original) (raw)

Charles D Hixson charleshixsn at earthlink.net
Wed Sep 26 21:39:49 CEST 2007

skip at pobox.com wrote:

Mark> With sorteddict you pay O(log N) for accessing, but you pay Mark> nothing for sorting.

Pay me now or pay me later, but maintaining a sorted sequence will always cost something. Skip Very frequently, however, I want frequent sorted access to a container.
I.e. I will want something like "what's the next key bigger than nnn"
(I said nnn because it often isn't a string). In such cases a B+Tree or B*Tree is a much better answer than a hash table. I'll grant that for the most common cases hash tables are superior...but not, by any means, for all cases.

There have been cases where I have maintained both a list and a dict for the same data. (Well, the list was an index into the dict, but you get the idea.) The dict was for fast access when I knew the key, and the list was for binary search when I knew things about the key.

An important note here is that the key to the dict/list was generally NOT a string in these situations. If strings suffice, then I've generally found a hash table to work well enough, and frequently been superior.

OTOH, if you don't need continual access while you are building the list, then I agree with you. The problem is that each time you sort a hash table you must pay for an entire sort, while adding a key or two to a B+Tree is relatively cheap.

More information about the Python-3000 mailing list