Self reordering list in Python

Jules Dubois not-even at dispsable.address.this.time
Fri Sep 16 07:36:26 CEST 2005


On Thursday 15 September 2005 07:14, Laszlo Zsolt Nagy
<gandalf at geochemsource.com>
(<mailman.421.1126790054.509.python-list at python.org>) wrote:

> Do you know how to implement a really efficient self reordering list in
> Python?

Yes.

> (List with a maximum length. When an item is processed, it 
> becomes the first element in the list.)

Search for "move to front list".  If you want a much bigger improvement in
speed -- O(N * log N) instead of O(N**2) -- search for "splay tree"; of
course, the algorithm is more complex and the optimized algorithm is even
more complex.

> Of course I could implement this in pure Python, I just wonder if there is
> a faster implementation that uses some cool feature of the standard 
> library. (Maybe a C implementation could be added to the collections
> module?)

Yes, you could write a C-language extension for more speed.



More information about the Python-list mailing list