Self reordering list in Python

Laszlo Zsolt Nagy gandalf at
Fri Sep 16 13:03:33 CEST 2005

>I wonder why you don't use a dictionary? The only time I used a
>move-front algorithm I stored algorithms and had to evaluate a
>condition to select the correct algo. That means no constant search key
>was available for accessing the correct one. In case of an image list I
>would implement a self-ordering list if I have to do some pattern
>recognition in order to select the correct image. Holding a reference
>as a search key a Python hash-table will always have a better average
>time complexity no matter which language is used to implement
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)

Probably my problem was a "no-problem". I realized that it does not 
matter how fast is my list. The most time consuming part is still the 
rendering of the images that are not in the cache. I need to speed up 
rendering and have more RAM, of course. :-)


More information about the Python-list mailing list