Simple lru cache?

Tim Hochberg tim.hochberg at
Sat Oct 5 01:34:28 CEST 2002

"Paul Rubin" wrote in message:
> Ype Kingma <ykingma at> 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


More information about the Python-list mailing list