Home Original page

alwayssortedlist (was Re: On PEP 322 (ireverse))

Raymond Hettinger vze4rx4y at verizon.net
Wed Oct 29 16:00:05 EST 2003 
[Alex Martelli]
> Perfectly right.  If you DO want a listoid container that keeps its
> elements sorted, that's not hard to make for yourself.  There are
> basically two obvious implementation strategies:
>   -- ensure the underlying list is re-sorted at each insertion,
>      append &c, and/or
>   -- let the underlying list grow as it will on insertion &c, but
>      make sure it's sorted at any method that accesses it (you can
>      use a flag -- 'have there being any append/insert/... since
>      the last sort?' -- to re-sort only when needed).
>
> I'll choose the first for general use because:
>   -- accesses are much more frequent than modifications,
>   -- list.sort is VERY fast when a list is "nearly sorted"

That could also be an argument for the second approach.
The timsort excels at finding the unsorted part, sorting it,
and merging it with rest.  And, if there were any partial
ordering of the unsorted part, it tends to take advantage
of that.

For the second approach, I would keep a sorted flag.
Whenever a new element is added the flag would be
set to False.  Upon data access, a False flag indicates
a need to run sort() and then the flag is set to True.
IOW, sort only when needed and sort as many items
at a time as you can.


Raymond Hettinger
More information about the Python-list mailing list