Simple lru cache?

[Alex Martelli]

Steve Holden wrote:
        ...
>> Or is there a way to pick one element randomly from a list
>> and move it to front or back and shift the rest to make place,
>> all in a single python statement, ie. without using a for statement?
>>
> What, you mean like
> 
>     mylst = mylst[:n] + mylst[n+1:] + [mylst[n]]
> 
> for example?

This builds a new list, rather than altering the old one.  It's
easy to fix so it alters the old one, of course (probably only
relevant if you have other names for the same list, but maybe a
little bit faster too):

mylst[n:] = mylst[n+1:] + [mylst[n]]


Somebody later mentioned that O(m) behavior might be a problem,
but that's inevitable when you want to "shift the rest" (m items).
Moving m items within a list is O(m).  If that's no good, then
a Python list is not the right data structure -- don't let the
name fool you, it's not implemented as a linked-list but rather
as a vector or array -- contiguous storage for references to
items.  So accessing mylst[n] is O(1), but shifting items around
ain't.  You can easily build lisp-like lists (use a 2-item list
to represent each node's car/cdr for example) if that's what you
want, or other kinds of linked lists (e.g. doubly-linked) since
everything's being done by-reference anyway.  I see from other
posts in this thread that several other viable alternatives have
also been proposed.

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).


Alex