Self reordering list in Python
Jules Dubois
not-even at dispsable.address.this.time
Fri Sep 16 01:36:26 EDT 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