A key parameter for heapq.merge
Hi, According to its own documentation, the merge() function in the heapq module is similar to sorted(). However, it has none of the key and reverse parameters that sorted() has. I think they could be just as useful as in sorted(). http://docs.python.org/dev/library/heapq.html#heapq.merge http://docs.python.org/dev/library/functions.html#sorted First of all what do you think of the idea? I’m working on a patch for a key parameter. I think it can be pretty straightforward, but I’ll measure if the "no key" case becomes slower (calls to lambda x: x) At worst we can always duplicate the loop. However, I am not sure how to implement reverse. Not all values have an "opposite value" that reverses order, _nsmallest and _nlargest are quite different, and merge uses neither. Anyway, if I get this to work, it will be my first contribution to CPython. I’m trying to follow the Developer’s guide, but is there something else I should be aware of? http://docs.python.org/devguide/ Regards, -- Simon Sapin
Simon Sapin wrote:
I’m working on a patch for a key parameter. I think it can be pretty straightforward, but I’ll measure if the "no key" case becomes slower (calls to lambda x: x) At worst we can always duplicate the loop.
In my experience, it is *much* faster to test against None every time through the loop than to call a do-nothing function. Instead of this: if key is None: key = lambda x: x for value in heap: do_something_with(key(value)) this is much faster: for value in heap: if key is None: do_something_with(value) else: do_something_with(key(value)) and this is faster still: if key is None: for value in heap: do_something_with(value) else: for value in heap: do_something_with(key(value)) YMMV; I encourage you to benchmark. -- Steven
Le 09/01/2012 00:46, Steven D'Aprano a écrit :
and this is faster still:
if key is None: for value in heap: do_something_with(value) else: for value in heap: do_something_with(key(value))
Yes, this is what I meant by duplicating the loop, though do_something_with() is a bit longer: http://hg.python.org/cpython/file/56e9d025078d/Lib/heapq.py#l336
YMMV; I encourage you to benchmark.
I have a working patch with tests. I’ll do a benchmarks next. After that is filing an issue? Thanks, -- Simon Sapin
On Jan 8, 2012, at 9:58 PM, Simon Sapin wrote:
According to its own documentation, the merge() function in the heapq module is similar to sorted(). However, it has none of the key and reverse parameters that sorted() has. I think they could be just as useful as in sorted().
A key-argument could be useful but a reverse parameter doesn't make as much sense. If you want to make a patch, add it to the tracker and assign it to me for review. Raymond
Le 09/01/2012 08:36, Raymond Hettinger a écrit :
A key-argument could be useful but a reverse parameter doesn't make as much sense.
If you want to make a patch, add it to the tracker and assign it to me for review.
I just opened http://bugs.python.org/issue13742 , but I can’t assign it. (New account on the tracker.) Thanks, -- Simon Sapin
On 1/9/2012 5:46 AM, Simon Sapin wrote:
Le 09/01/2012 08:36, Raymond Hettinger a écrit :
A key-argument could be useful but a reverse parameter doesn't make as much sense.
If you want to make a patch, add it to the tracker and assign it to me for review.
I just opened http://bugs.python.org/issue13742 , but I can’t assign it. (New account on the tracker.)
I assigned it to Raymond. Eric.
Le 09/01/2012 11:51, Eric V. Smith a écrit :
On 1/9/2012 5:46 AM, Simon Sapin wrote:
I just opened http://bugs.python.org/issue13742 , but I can’t assign it. (New account on the tracker.) I assigned it to Raymond.
Hi, I think my latest patch on #13742 looks good. Is something else missing? Thanks, -- Simon Sapin
participants (4)
-
Eric V. Smith -
Raymond Hettinger -
Simon Sapin -
Steven D'Aprano