The wrapper around heapq.nlargest and heapq.nsmallest is much slower
than it's C version.

$ python2.5 -mtimeit -s 'import random; random.seed(123); n=999999;
x=range(n); random.shuffle(x); import _heapq' '_heapq.nlargest(3, x)'
10 loops, best of 3: 142 msec per loop

$ python2.5 -mtimeit -s 'import random; random.seed(123); n=999999;
x=range(n); random.shuffle(x); import heapq' 'heapq.nlargest(3, x)'
10 loops, best of 3: 685 msec per loop


If the key argument is None, there is no need to use the wrapper. This
patch adds an a check to avoid this.

Am rejecting the patch because it violates the sort equivalence
guarantee (including sort's promise to maintain stability).

If you need the speed and don't care about sort stability, then just use
_heapq.nsmallest() or _heapq.nlargest() directly.

We could complexify the code a bit to achieve some automatic speed-up in
the case of key==None, but my timings don't show much of an improvement:

    if key is None:
        it = izip(iterable, count())                 # decorate
        result = _nsmallest(n, it)
        return map(itemgetter(0), result)            # undecorate
    else:
        in1, in2 = tee(iterable)
        it = izip(imap(key, in1), count(), in2)      # decorate
        result = _nsmallest(n, it)
        return map(itemgetter(2), result)            # undecorate

After looking at the ugly handling of this logic in the 3.0 translation,
I've reconsidered.  It is better to have a separate path for the case
where the key is None.  See r68095 and r68096 .

Nice!

Maybe we could add the decorate/undecorate step to guarantee stability
to the C implementation. I'll do some experiments and timings on this.
The heapq library has a lot of room for optimization, I think.