Repository navigation
Add a key parameter (like sorted) to heapq.merge #57951
Description
| BPO | 13742 |
|---|---|
| Nosy | @rhettinger, @terryjreedy, @mdickinson, @giampaolo, @merwok, @ericsnowcurrently, @berkerpeksag, @serhiy-storchaka |
| Files |
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 2014-05-30.09:29:28.655>
created_at = <Date 2012-01-09.10:35:41.807>
labels = ['type-feature', 'library']
title = 'Add a key parameter (like sorted) to heapq.merge'
updated_at = <Date 2015-01-10.08:47:47.975>
user = 'https://bugs.python.org/ssapin'bugs.python.org fields:
activity = <Date 2015-01-10.08:47:47.975>
actor = 'terry.reedy'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2014-05-30.09:29:28.655>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2012-01-09.10:35:41.807>
creator = 'ssapin'
dependencies = []
files = ['24184', '24185', '24248', '29578', '30063', '35374', '35399']
hgrepos = []
issue_num = 13742
keywords = ['patch', 'needs review']
message_count = 21.0
messages = ['150927', '150928', '150931', '150954', '150969', '150983', '151369', '152802', '152984', '168070', '168116', '185259', '188066', '188067', '188080', '188085', '219380', '233792', '233793', '233795', '233804']
nosy_count = 12.0
nosy_names = ['rhettinger', 'terry.reedy', 'mark.dickinson', 'giampaolo.rodola', 'stutzbach', 'eric.araujo', 'python-dev', 'eric.snow', 'berker.peksag', 'ssapin', 'serhiy.storchaka', 'Tommy.Carstensen']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue13742'
versions = ['Python 3.5']
Activity
ssapin commentedon Jan 9, 2012
Hi,
The attached patch adds a 'key' optional parameter to the heapq.merge function that behaves as in sorted().
Related discussion: http://mail.python.org/pipermail/python-ideas/2012-January/013295.html
This is my first contribution to CPython.
ssapin commentedon Jan 9, 2012
The attached script benchmarks the basline (current implementation) against 3 new implementations, as suggested on http://mail.python.org/pipermail/python-ideas/2012-January/013296.html
On my machine, the output is:
On this particular input, merge_2 adds 6% of overhead when the key parameter is not used. While merge_3 only adds 1% of overhead, it almost doubles the amount of code. (Which was admittedly not that long to begin with.)
The patch in the previous message is with the merge_2 implementation, which seemed like the best compromise to me.
ssapin commentedon Jan 9, 2012
Oops, the patch to the documentation would also need 'New in 3.3: the key parameter', with the right Sphinx directive. But that depends on whether this change ends up in 3.3 or 3.4.
Does 3.3 still get new features?
merwok commentedon Jan 9, 2012
Yes, 3.3 is still in the early development stage, and new features will be accepted until the first beta (in June, see PEP-398). “.. versionadded:: 3.3 The *key* parameter” will do.
rhettinger commentedon Jan 9, 2012
Simon, please keep the original version fast by creating two code paths:
ssapin commentedon Jan 9, 2012
Raymond, please have a look at merge_3 in benchmark_heapq_merge.py. It is implemented as you say.
Do you think the speed is worth the code duplication?
ssapin commentedon Jan 16, 2012
heapq_merge_key_duplicate.patch is a new patch with two code path. It also updates the function’s docstring (which the previous patch did not). Raymond, do you think the speed is worth the DRY violation?
rhettinger commentedon Feb 7, 2012
I'll look at this in the next couple of weeks. Hang tight :-)
terryjreedy commentedon Feb 9, 2012
FWIW, Guido approves of the idea, msg152969 in bpo-4356
ssapin commentedon Aug 13, 2012
I just remembered about this. I suppose it is too late for 3.3?
merwok commentedon Aug 13, 2012
Yes, 3.3 is already in beta.
rhettinger commentedon Mar 26, 2013
Attaching a rough draft implementation for a fully encapsulated Heap() class that is thread-safe, supports minheaps and maxheaps, and efficiently implements key-functions (called no more than once per key).
mdickinson commentedon Apr 29, 2013
heap2.diff contains only a single line's change. Wrong file attached?
mdickinson commentedon Apr 29, 2013
Ah, I see the new file now (I'd failed to refresh my browser); sorry for the noise.
mdickinson commentedon Apr 29, 2013
Looks pretty good to me.
There's a bonus print call in the diff.
Should the "len(self._data)" call be protected by the lock? I can't immediately think of any reason why that would be necessary (e.g., pushpop nd poppush never change the size of self._data, so there's no risk of getting a bogus length there), but the lack of the lock makes me nervous.
Support for iter() seems a bit out of place to me. What are the use-cases for this? Would it make sense to leave this out (for now)?
serhiy-storchaka commentedon Apr 29, 2013
There is already one heap class in the stdlib: queue.PriorityQueue. Why create a duplicate instead extend queue.PriorityQueue with desired features?
May be name the maxheap parameter as reverse?
python-dev commentedon May 30, 2014
New changeset f5521f5dec4a by Raymond Hettinger in branch 'default':
Issue bpo-13742: Add key and reverse parameters to heapq.merge()
http://hg.python.org/cpython/rev/f5521f5dec4a
TommyCarstensen commentedon Jan 10, 2015
I noticed 3.5 alpha1 is not released until February 1st. Is there any way I can get my hands on this new functionality?
berkerpeksag commentedon Jan 10, 2015
Hi Tommy, the patch is already committed to Python 3.5. See https://docs.python.org/3.5/library/heapq.html#heapq.merge
TommyCarstensen commentedon Jan 10, 2015
Yes, but 3.5 has not been pre-released yet.
terryjreedy commentedon Jan 10, 2015
You can set up mecurial on your machine, make a read-only clone of the cpython repository, and compile it just as do other people, whether core-developers or otherwise. See docs.python.org/devguide for details.