Optimization to heapq module

[nilton]

BPO	4790
Nosy	@rhettinger
Files	heapq_optimization.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2008-12-31.01:48:53.911>
created_at = <Date 2008-12-31.01:07:19.109>
labels = ['library']
title = 'Optimization to heapq module'
updated_at = <Date 2008-12-31.21:47:38.468>
user = 'https://bugs.python.org/nilton'

bugs.python.org fields:

activity = <Date 2008-12-31.21:47:38.468>
actor = 'nilton'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2008-12-31.01:48:53.911>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2008-12-31.01:07:19.109>
creator = 'nilton'
dependencies = []
files = ['12501']
hgrepos = []
issue_num = 4790
keywords = ['patch']
message_count = 4.0
messages = ['78584', '78587', '78590', '78654']
nosy_count = 2.0
nosy_names = ['rhettinger', 'nilton']
pr_nums = []
priority = 'normal'
resolution = 'accepted'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue4790'
versions = ['Python 2.6', 'Python 2.5', 'Python 3.0', 'Python 3.1', 'Python 2.7']

[nilton]

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.

[rhettinger]

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

[rhettinger]

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 .

[nilton]

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.