Simple lru cache?

Ype Kingma ykingma at accessforall.nl
Sat Oct 5 10:52:55 CEST 2002


Tim, Paul,

Thanks for some more food for performance experiments...

Ype



Tim Hochberg schreef:
> 
> "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
> 


-- 

email at xs4all.nl



More information about the Python-list mailing list