[Python-checkins] cpython: Issue #18962: Optimize the single iterator case for heapq.merge()

Wed Sep 11 08:16:00 CEST 2013

http://hg.python.org/cpython/rev/0e70bf1f32a3
changeset: 85656:0e70bf1f32a3
user: Raymond Hettinger <python at rcn.com>
date: Wed Sep 11 01:15:40 2013 -0500
summary:
 Issue #18962: Optimize the single iterator case for heapq.merge()
Suggested by Wouter Bolsterlee.
files:
 Lib/heapq.py | 14 +++++++++-----
 Misc/ACKS | 1 +
 2 files changed, 10 insertions(+), 5 deletions(-)

diff --git a/Lib/heapq.py b/Lib/heapq.py
--- a/Lib/heapq.py
+++ b/Lib/heapq.py
@@ -358,6 +358,7 @@
 
 '''
 _heappop, _heapreplace, _StopIteration = heappop, heapreplace, StopIteration
+ _len = len
 
 h = []
 h_append = h.append
@@ -369,17 +370,20 @@
 pass
 heapify(h)
 
- while 1:
+ while _len(h) > 1:
 try:
- while 1:
- v, itnum, next = s = h[0] # raises IndexError when h is empty
+ while True:
+ v, itnum, next = s = h[0]
 yield v
 s[0] = next() # raises StopIteration when exhausted
 _heapreplace(h, s) # restore heap condition
 except _StopIteration:
 _heappop(h) # remove empty iterator
- except IndexError:
- return
+ if h:
+ # fast case when only a single iterator remains
+ v, itnum, next = h[0]
+ yield v
+ yield from next.__self__
 
 # Extend the implementations of nsmallest and nlargest to use a key= argument
 _nsmallest = nsmallest
diff --git a/Misc/ACKS b/Misc/ACKS
--- a/Misc/ACKS
+++ b/Misc/ACKS
@@ -135,6 +135,7 @@
 Matthew Boedicker
 Robin Boerdijk
 David Bolen
+Wouter Bolsterlee
 Gawain Bolton
 Forest Bond
 Gregory Bond
-- 
Repository URL: http://hg.python.org/cpython
