[Python-Dev] Proposal: add odict to collections (original) (raw)

zooko zooko at zooko.com
Sun Jun 15 21:20:19 CEST 2008

On Jun 14, 2008, at 8:26 PM, Guido van Rossum wrote:

No, but an ordered dict happens to be a very common thing to need, for a variety of reasons. So I'm +0.5 on adding this to the collections module. However someone needs to contribute working code.

Here's an LRU cache that I've used a few times over the years:

http://allmydata.org/trac/pyutil/browser/pyutil/pyutil/cache.py

This is just like a dict ordered by insertion, except:

  1. That it removes the oldest entry if it grows beyond a limit.

  2. That it moves an entry to the head of the queue when has_key() is
    called on that item.

So, it would be easy to change those two behaviors in order to use
this implementation. There are actually three implementations in
that file: one that is asymptotically O(1) for all operations (using
a double-linked list woven into the values of the dict), and one that
uses a Python list to hold the order, so it is faster for small
enough dicts. The third implementation is an implementation that
someone else wrote that I included just for comparison purposes --
the comparison showed that each of mine was better.

Regards,

Zooko

More information about the Python-Dev mailing list