[Python-checkins] r43513 - in python/branches/release24-maint: Lib/random.py Lib/test/test_random.py Misc/NEWS

Sat Apr 1 02:41:11 CEST 2006

Author: tim.peters
Date: Sat Apr 1 02:41:10 2006
New Revision: 43513
Modified:
 python/branches/release24-maint/Lib/random.py
 python/branches/release24-maint/Lib/test/test_random.py
 python/branches/release24-maint/Misc/NEWS
Log:
Merge rev 43511 from the trunk.
Another crack at bug #1460340: make random.sample(dict)
work, this time by ugly brute force.
Modified: python/branches/release24-maint/Lib/random.py
==============================================================================

--- python/branches/release24-maint/Lib/random.py	(original)
+++ python/branches/release24-maint/Lib/random.py	Sat Apr 1 02:41:10 2006
@@ -285,6 +285,15 @@
 large population: sample(xrange(10000000), 60)
 """
 
+ # XXX Although the documentation says `population` is "a sequence",
+ # XXX attempts are made to cater to any iterable with a __len__
+ # XXX method. This has had mixed success. Examples from both
+ # XXX sides: sets work fine, and should become officially supported;
+ # XXX dicts are much harder, and have failed in various subtle
+ # XXX ways across attempts. Support for mapping types should probably
+ # XXX be dropped (and users should pass mapping.keys() or .values()
+ # XXX explicitly).
+
 # Sampling without replacement entails tracking either potential
 # selections (the pool) in a list or previous selections in a
 # dictionary.
@@ -302,7 +311,9 @@
 random = self.random
 _int = int
 result = [None] * k
- if n < 6 * k: # if n len list takes less space than a k len dict
+ if n < 6 * k or hasattr(population, "keys"):
+ # An n-length list is smaller than a k-length set, or this is a
+ # mapping type so the other algorithm wouldn't work.
 pool = list(population)
 for i in xrange(k): # invariant: non-selected at [0,n-i)
 j = _int(random() * (n-i))
@@ -316,10 +327,10 @@
 while j in selected:
 j = _int(random() * n)
 result[i] = selected[j] = population[j]
- except (TypeError, KeyError): # handle sets and dictionaries
+ except (TypeError, KeyError): # handle (at least) sets
 if isinstance(population, list):
 raise
- return self.sample(list(population), k)
+ return self.sample(tuple(population), k)
 return result
 
 ## -------------------- real-valued distributions -------------------
Modified: python/branches/release24-maint/Lib/test/test_random.py
==============================================================================
--- python/branches/release24-maint/Lib/test/test_random.py	(original)
+++ python/branches/release24-maint/Lib/test/test_random.py	Sat Apr 1 02:41:10 2006
@@ -93,12 +93,28 @@
 self.gen.sample(set(range(20)), 2)
 self.gen.sample(range(20), 2)
 self.gen.sample(xrange(20), 2)
- self.gen.sample(dict.fromkeys('abcdefghijklmnopqrst'), 2)
 self.gen.sample(str('abcdefghijklmnopqrst'), 2)
 self.gen.sample(tuple('abcdefghijklmnopqrst'), 2)
+
+ def test_sample_on_dicts(self):
+ self.gen.sample(dict.fromkeys('abcdefghijklmnopqrst'), 2)
+
 # SF bug #1460340 -- random.sample can raise KeyError
 a = dict.fromkeys(range(10)+range(10,100,2)+range(100,110))
- self.gen.sample(a,3)
+ self.gen.sample(a, 3)
+
+ # A followup to bug #1460340: sampling from a dict could return
+ # a subset of its keys or of its values, depending on the size of
+ # the subset requested.
+ N = 30
+ d = dict((i, complex(i, i)) for i in xrange(N))
+ for k in xrange(N+1):
+ samp = self.gen.sample(d, k)
+ # Verify that we got ints back (keys); the values are complex.
+ for x in samp:
+ self.assert_(type(x) is int)
+ samp.sort()
+ self.assertEqual(samp, range(N))
 
 def test_gauss(self):
 # Ensure that the seed() method initializes all the hidden state. In
Modified: python/branches/release24-maint/Misc/NEWS
==============================================================================
--- python/branches/release24-maint/Misc/NEWS	(original)
+++ python/branches/release24-maint/Misc/NEWS	Sat Apr 1 02:41:10 2006
@@ -4,6 +4,20 @@
 
 (editors: check NEWS.help for information about editing NEWS using ReST.)
 
+What's New in Python 2.4.4c1?
+=============================
+
+*Release date: DD-MMM-2006*
+
+Library
+-------
+
+- Bug #1460340: ``random.sample(dict)`` failed in various ways. Dicts
+ aren't officially supported here, and trying to use them will probably
+ raise an exception some day. But dicts have been allowed, and "mostly
+ worked", so support for them won't go away without warning.
+
+
 What's New in Python 2.4.3?
 ===========================
 
@@ -14,10 +28,10 @@
 
 - A few reference leaks were squished.
 
-- A threading issue that caused random segfaults on some platforms from 
+- A threading issue that caused random segfaults on some platforms from
 the testsuite was fixed in test_capi.
 
-- Reverted fix for Bug #1379994: Builtin unicode_escape and 
+- Reverted fix for Bug #1379994: Builtin unicode_escape and
 raw_unicode_escape codec now encodes backslash correctly.
 This caused another issue for unicode repr strings being double-escaped
 (SF Bug #1459029). Correct fix will be in 2.5, but is too risky for 2.4.3.
