Simple lru cache?

[Tim Hochberg]

"Paul Rubin" wrote in message:
> Ype Kingma <ykingma at accessforall.nl> writes:
> > The alternative is a normal python list, but it would probably take
> > too much time for shifting the aging elements.
> > 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?
>
>         index = random() % len(cache)
>         entry = cache[index]
>         del cache[index]
>
>     then
>
>         cache.append(entry)   # append to end
>
>     or
>
>         cache.insert(0, entry)  # insert at beginning
>
> These move all the cache elements around but will be much faster than
> using Python loops to do it.  It's probably the best way if the cache
> size is less than a few thousand.

Another approach is to block copy the elements. It shouldn't make a
signifigant difference when appending to the end, but it should save you
from copying all of the elements on the insert(0, entry) when inserting at
the beginning.

        index = randint(1, len(cache)-1)
        entry = cache[index]
        cache[1:index] = cache[:index-1]
        cache[index] = entry

-tim