[Python-checkins] r53243 - in python/branches/release25-maint: Lib/heapq.py Lib/test/test_heapq.py Misc/NEWS

Thu Jan 4 18:53:19 CET 2007

Author: raymond.hettinger
Date: Thu Jan 4 18:53:16 2007
New Revision: 53243
Modified:
 python/branches/release25-maint/Lib/heapq.py
 python/branches/release25-maint/Lib/test/test_heapq.py
 python/branches/release25-maint/Misc/NEWS
Log:
Fix stability of heapq's nlargest() and nsmallest().
Modified: python/branches/release25-maint/Lib/heapq.py
==============================================================================

--- python/branches/release25-maint/Lib/heapq.py	(original)
+++ python/branches/release25-maint/Lib/heapq.py	Thu Jan 4 18:53:16 2007
@@ -130,7 +130,7 @@
 'nsmallest']
 
 from itertools import islice, repeat, count, imap, izip, tee
-from operator import itemgetter
+from operator import itemgetter, neg
 import bisect
 
 def heappush(heap, item):
@@ -315,8 +315,6 @@
 
 Equivalent to: sorted(iterable, key=key)[:n]
 """
- if key is None:
- return _nsmallest(n, iterable)
 in1, in2 = tee(iterable)
 it = izip(imap(key, in1), count(), in2) # decorate
 result = _nsmallest(n, it)
@@ -328,10 +326,8 @@
 
 Equivalent to: sorted(iterable, key=key, reverse=True)[:n]
 """
- if key is None:
- return _nlargest(n, iterable)
 in1, in2 = tee(iterable)
- it = izip(imap(key, in1), count(), in2) # decorate
+ it = izip(imap(key, in1), imap(neg, count()), in2) # decorate
 result = _nlargest(n, it)
 return map(itemgetter(2), result) # undecorate
 
Modified: python/branches/release25-maint/Lib/test/test_heapq.py
==============================================================================
--- python/branches/release25-maint/Lib/test/test_heapq.py	(original)
+++ python/branches/release25-maint/Lib/test/test_heapq.py	Thu Jan 4 18:53:16 2007
@@ -104,20 +104,20 @@
 self.assertEqual(heap_sorted, sorted(data))
 
 def test_nsmallest(self):
- data = [random.randrange(2000) for i in range(1000)]
- f = lambda x: x * 547 % 2000
- for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
- self.assertEqual(nsmallest(n, data), sorted(data)[:n])
- self.assertEqual(nsmallest(n, data, key=f),
- sorted(data, key=f)[:n])
+ data = [(random.randrange(2000), i) for i in range(1000)]
+ for f in (None, lambda x: x[0] * 547 % 2000):
+ for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
+ self.assertEqual(nsmallest(n, data), sorted(data)[:n])
+ self.assertEqual(nsmallest(n, data, key=f),
+ sorted(data, key=f)[:n])
 
 def test_nlargest(self):
- data = [random.randrange(2000) for i in range(1000)]
- f = lambda x: x * 547 % 2000
- for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
- self.assertEqual(nlargest(n, data), sorted(data, reverse=True)[:n])
- self.assertEqual(nlargest(n, data, key=f),
- sorted(data, key=f, reverse=True)[:n])
+ data = [(random.randrange(2000), i) for i in range(1000)]
+ for f in (None, lambda x: x[0] * 547 % 2000):
+ for n in (0, 1, 2, 10, 100, 400, 999, 1000, 1100):
+ self.assertEqual(nlargest(n, data), sorted(data, reverse=True)[:n])
+ self.assertEqual(nlargest(n, data, key=f),
+ sorted(data, key=f, reverse=True)[:n])
 
 
 #==============================================================================
Modified: python/branches/release25-maint/Misc/NEWS
==============================================================================
--- python/branches/release25-maint/Misc/NEWS	(original)
+++ python/branches/release25-maint/Misc/NEWS	Thu Jan 4 18:53:16 2007
@@ -125,6 +125,8 @@
 Library
 -------
 
+- Fix sort stability in heapq.nlargest() and nsmallest().
+
 - Patch #1504073: Fix tarfile.open() for mode "r" with a fileobj argument.
 
 - Patch #1262036: Prevent TarFiles from being added to themselves under
