Simple lru cache?

[Ype Kingma]

Alex,

<snip>

> 
> One that I haven't seen is based on dictionaries -- may not be
> best, but it's interesting, at least (it's somewhat of a
> surprise that a dict is often the best way to implement a
> FIFO queue in Python, for example -- now this case is a bit
> different, but...).
> 
> Say that what we want is to be able to access the X LRU items
> (e.g. to remove them) and that items are hashable.  Then:
> 
> oldest = newest = 0
> item_to_age = {}
> age_to_item = {}
> 
> def use_item(IT):
>     newest += 1
>     item_to_age[IT] = newest
>     age_to_item[newest] = IT
> 
> def prune_X_items(X):
>     pruned = 0
>     while pruned < X and oldest < newest:
>         oldest += 1
>         IT = age_to_item.get(oldest)
>         if IT is not None:
>             del age_to_item[oldest]
>             del item_to_age[IT]
>             pruned += 1
> 
> Now the computational cost of "use_item" is pretty darn
> close to O(1) [thanks to the performance characteristics
> of Python's dicts] -- although it's harder to estimate
> the computational cost of "prune_X_items", as it depends
> on how much "churning" there has been (I'd guess it's
> probably no good if older items are OFTEN 'used' again).

I'd expect in the order of 10000 items cached of which:
20% would be used around 4 times,
20% around 3 times,
20% around 2 times,
40% used once only.

I also realized that not all items take the same time to
fetch from the database, 10 msec is avarage, but I've seen
anything from close to 0 (hitting another cache) to 100 msecs.
Needless to say that these slow outliers would be most helpfull
in the cache. And off course the access pattern changes ao. by
using the cache, so access times will also change.

With your suggestion I now have 3 basic implementations (doubly
linked list, python list, FIFO by counters in dictionaries)
to try in practice.
I'd normally go for the simplest one first, but they hardly
differ in simplicity, so it's difficult to choose.

Thanks,
Ype