Self reordering list in Python

Terry Hancock hancock at
Fri Sep 16 17:58:48 CEST 2005

On Friday 16 September 2005 06:03 am, Laszlo Zsolt Nagy wrote:
> You are right in that holding a reference will have a better time 
> complexity. But holding a reference makes it impossible to free the 
> object. :-) As I said, my list has a maximum length. I just can't store 
> any number of images in memory. I need to keep only the most frequently 
> used ones. I do not know which ones will be used the most frequently, 
> this is why I need a self reordering list. Accessing an element makes it 
> "more imporant" than the others. I already implemented this in Python 
> and it was ten times faster compared to the original version. (200 
> frames per sec instead of 20 fps)

This is actually the use-case for an "LRU cache"="least recently used
cache", which is probably already implemented in Python somewhere (or
even as a fast extension).  I'd do a google search for it.  It almost
certainly would use a dictionary interface within Python, ISTM.


Terry Hancock ( hancock at )
Anansi Spaceworks

More information about the Python-list mailing list