[Python-ideas] Contiguous-array-based ordering for OrderedDict

[Guido van Rossum]

On Sat, Dec 12, 2015 at 5:16 PM, Serhiy Storchaka <storchaka at gmail.com>
wrote:

> On 13.12.15 02:27, Guido van Rossum wrote:
>
>> I'm not following this thread all that closely, but am I the only one
>> who thinks that the LRU cache (discussed in another thread) could be
>> implemented with much less code on top of OrderedDict? Basically
>> whenever you access a key you just move it to the front, and when you
>> add a key when it is already at capacity you delete the first one.
>>
>
> I have doubts about this. First, an ordered dictionary is only a part of
> the LRU cache implementation, using OrderedDict wouldn't make the code much
> less. Second, the LRU cache needs only small and very limited part of
> OrderedDict, with different requirements to reentrancy, thread-safety, and
> errors handling (partially more strong, partially more lenient). The code
> currently used by the LRU cache is much simpler, likely faster, and more
> bug-free.
>

Fair enough. Perhaps it would have made more sense if we had a C version of
OrderedDict but not of lru_cache. Still, two things:

(1) Anything written in Python that implements a linked list feels like a
code smell to me (it's hard to make up for the constant factor with a
better algorithm unless the data structure is pretty large).

(2) If you want to implement something that's close to lru_cache but not
quite (e.g. one where items also come with a timeout, like DNS lookups),
you can't subclass its implementation, because it's all hidden in a
function. But you can wrap a little bit of extra logic around the 10 or so
lines it takes to implement a decent LRU cache on top of OrderedDict.

-- 
--Guido van Rossum (python.org/~guido)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20151213/9936aada/attachment.html>