RetroSearch Browse

Fri Nov 14 19:46:59 EST 2003 · https://mail.python.org/pipermail/python-dev/2003-November/040240.html

[Armin Rigo]
> from heapq import *
> def isorted(iterable):
>     heap = list(iterable)
>     heapify(heap)
>     while heap:
>         yield heappop(heap)
> 
> This generator is similar to the new list.sorted() but starts yielding
> elements after only O(n) operations (in heapify).  Certainly not a
> candidate
> for itertools, but it could be added to heapqmodule.c.  There are
numerous
> cases where this kind of lazy-sorting is interesting, if done
reasonably
> efficiently (unsurprizingly, this is known as Heap Sort).

How much of the iterator can be consumed before it becomes preferable
(in terms of speed and memory) to have used iter(list.sort())?

My guess is that the break-even point for speed is around 10% depending
on how much order already exists in the underlying list.  In terms of
memory, I think list.sort() always beats the above implementation.

Raymond Hettinger

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://mail.python.org/pipermail/python-dev/2003-November/040240.html below:

list.sort, was Re: [Python-Dev] decorate-sort-undecorate