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
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
