[Python-Dev] Proposal: add odict to collections
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