[Python-Dev] PEP 372 -- Adding an ordered directory to collections ready for pronouncement

Guido van Rossum guido at python.org
Wed Mar 4 01:49:52 CET 2009


On Tue, Mar 3, 2009 at 3:05 PM, Scott David Daniels
<Scott.Daniels at acm.org> wrote:
> Forest wrote:
>>
>> On Tue, March 3, 2009 11:20 am, Forest wrote:
>>>
>>> Okay, but I'd also like a convenient and fast way to find the oldest
>>> entry
>>> in an OrderedDict, which I think I'd need for an LRU cache.  Skimming the
>>> current patch (od7.diff), I didn't notice one.  Perhaps I simply missed
>>> something.  Shouldn't popitem() allow the caller to choose which end from
>>> which to pop?
>>
>> Thinking it through a bit more, and LRU cache would actually need to
>> access the oldest item before knowing whether to remove it.  Besides,
>> popitem() should probably retain the signature of dict.popitem().  I
>> therefore retract my suggestion about popitem().
>>
>> Still, I think an LRU cache would be a very common use case for an ordered
>> dict.  The current implementation already uses a list to keep track of
>> order, which makes accessing the oldest key a simple matter of exposing
>> it.  Perhaps a new method like getfirst() would be worth while here?
>
> But you must decide if what you want really does LRU -- does accessing
> the oldest entry make it the most recent entry?

Beware, deleting an item from an OrderedDict (in the current
implementation) is O(N). To implement an LRU cache you are probably
better off ignoring OrderedDict so that you can manipulate the list of
keys directly.

-- 
--Guido van Rossum (home page: http://www.python.org/~guido/)


More information about the Python-Dev mailing list