Skip to content

Add a key parameter (like sorted) to heapq.merge #57951

Closed
Closed
Add a key parameter (like sorted) to heapq.merge#57951
Assignees
rhettinger
Labels
stdlibStandard Library Python modules in the Lib/ directorytype-featureA feature request or enhancement

Description

@ssapin
ssapin
mannequin
opened on Jan 9, 2012
BPO 13742
Nosy @rhettinger, @terryjreedy, @mdickinson, @giampaolo, @merwok, @ericsnowcurrently, @berkerpeksag, @serhiy-storchaka
Files
  • heapq_merge_key.patch: 'hg diff' output against rev ca2a35140e6a
  • benchmark_heapq_merge.py: benchmark several implementations
  • heapq_merge_key_duplicate.patch: 'hg diff' output against rev ca2a35140e6a
  • heap.diff: Rough draft (untested) for a Heap() class
  • heap2.diff: Update the draft Heap() class
  • keymerge.diff: Draft patch without doc updates
  • keymerge2.diff: Add both key=func and reverse=True options
    		•

    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

    1. ssapin commented on Jan 9, 2012

      @ssapin
      ssapinmannequin
      on Jan 9, 2012
      MannequinAuthor

      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.

    2. ssapin
      added
      stdlibStandard Library Python modules in the Lib/ directory
      type-featureA feature request or enhancement
      on Jan 9, 2012

    3. ssapin commented on Jan 9, 2012

      @ssapin
      ssapinmannequin
      on Jan 9, 2012
      MannequinAuthor

      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:

      merge_baseline
per run, min of 3 = 7.527 ms

merge_1
per run, min of 3 = 9.894 ms
131.449 % of baseline

merge_2
per run, min of 3 = 7.948 ms
105.594 % of baseline

merge_3
per run, min of 3 = 7.581 ms
100.716 % of baseline

      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.

    4. ericvsmith
      assigned
      rhettinger
      on Jan 9, 2012

    5. ssapin commented on Jan 9, 2012

      @ssapin
      ssapinmannequin
      on Jan 9, 2012
      MannequinAuthor

      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?

    6. merwok commented on Jan 9, 2012

      @merwok
      merwok
      on Jan 9, 2012
      Member

      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.

    7. rhettinger commented on Jan 9, 2012

      @rhettinger
      rhettinger
      on Jan 9, 2012
      Contributor

      Simon, please keep the original version fast by creating two code paths:

         if key is None:
      original_code
   else:
      new_code using the key_function

    8. ssapin commented on Jan 9, 2012

      @ssapin
      ssapinmannequin
      on Jan 9, 2012
      MannequinAuthor

      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?

    9. ssapin commented on Jan 16, 2012

      @ssapin
      ssapinmannequin
      on Jan 16, 2012
      MannequinAuthor

      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?

    10. rhettinger commented on Feb 7, 2012

      @rhettinger
      rhettinger
      on Feb 7, 2012
      Contributor

      I'll look at this in the next couple of weeks. Hang tight :-)

    11. terryjreedy commented on Feb 9, 2012

      @terryjreedy
      terryjreedy
      on Feb 9, 2012
      Member

      FWIW, Guido approves of the idea, msg152969 in bpo-4356

    12. ssapin commented on Aug 13, 2012

      @ssapin
      ssapinmannequin
      on Aug 13, 2012
      MannequinAuthor

      I just remembered about this. I suppose it is too late for 3.3?

    13. merwok commented on Aug 13, 2012

      @merwok
      merwok
      on Aug 13, 2012
      Member

      Yes, 3.3 is already in beta.

    14. rhettinger commented on Mar 26, 2013

      @rhettinger
      rhettinger
      on Mar 26, 2013
      Contributor

      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).

    15. mdickinson commented on Apr 29, 2013

      @mdickinson
      mdickinson
      on Apr 29, 2013
      Member

      heap2.diff contains only a single line's change. Wrong file attached?

    16. mdickinson commented on Apr 29, 2013

      @mdickinson
      mdickinson
      on Apr 29, 2013
      Member

      Ah, I see the new file now (I'd failed to refresh my browser); sorry for the noise.

    17. mdickinson commented on Apr 29, 2013

      @mdickinson
      mdickinson
      on Apr 29, 2013
      Member

      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)?

    18. serhiy-storchaka commented on Apr 29, 2013

      @serhiy-storchaka
      serhiy-storchaka
      on Apr 29, 2013
      Member

      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?

    19. python-dev commented on May 30, 2014

      @python-dev
      python-devmannequin
      on May 30, 2014
      Mannequin

      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

    20. rhettinger
      closed this as completedon May 30, 2014

    21. TommyCarstensen commented on Jan 10, 2015

      @TommyCarstensen
      TommyCarstensenmannequin
      on Jan 10, 2015
      Mannequin

      I noticed 3.5 alpha1 is not released until February 1st. Is there any way I can get my hands on this new functionality?

    22. berkerpeksag commented on Jan 10, 2015

      @berkerpeksag
      berkerpeksag
      on Jan 10, 2015
      Member

      Hi Tommy, the patch is already committed to Python 3.5. See https://docs.python.org/3.5/library/heapq.html#heapq.merge

    23. TommyCarstensen commented on Jan 10, 2015

      @TommyCarstensen
      TommyCarstensenmannequin
      on Jan 10, 2015
      Mannequin

      Yes, but 3.5 has not been pre-released yet.

    24. terryjreedy commented on Jan 10, 2015

      @terryjreedy
      terryjreedy
      on Jan 10, 2015
      Member

      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.

    25. ezio-melotti
      transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    Labels

    stdlibStandard Library Python modules in the Lib/ directorytype-featureA feature request or enhancement

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions