On Tue, Mar 3, 2009 at 3:05 PM, Scott David Daniels <scott.dani...@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/) _______________________________________________ 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
