[Python-checkins] python/nondist/sandbox/statistics statistics.py, 1.5, 1.6 test_statistics.py, 1.1, 1.2

Tue Feb 17 08:00:19 EST 2004

Update of /cvsroot/python/python/nondist/sandbox/statistics
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv14804
Modified Files:
	statistics.py test_statistics.py 
Log Message:
Have select() use randomization to overcome degenerate cases.
Index: statistics.py
===================================================================
RCS file: /cvsroot/python/python/nondist/sandbox/statistics/statistics.py,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** statistics.py	17 Feb 2004 12:17:41 -0000	1.5
--- statistics.py	17 Feb 2004 13:00:16 -0000	1.6
***************
*** 25,28 ****
--- 25,29 ----
 import heapq
 import bisect
+ import random
 
 __all__ = ['mean', 'median', 'nlargest', 'nsmallest',
***************
*** 90,98 ****
 """
 try:
 while True:
- under, notunder = [], []
- ua, nua = under.append, notunder.append
 it = iter(data)
 pivot = it.next()
 for elem in it:
 if elem < pivot:
--- 91,100 ----
 """
 try:
+ shuffled = False
 while True:
 it = iter(data)
 pivot = it.next()
+ under, notunder = [], []
+ ua, nua = under.append, notunder.append
 for elem in it:
 if elem < pivot:
***************
*** 107,110 ****
--- 109,115 ----
 data = notunder
 n -= len(under) + 1
+ if not shuffled and len(data)>8 and min(len(under), len(notunder)) == 0:
+ random.shuffle(data)
+ shuffled = True
 except StopIteration:
 raise ValueError('not enough elements for the given rank')
Index: test_statistics.py
===================================================================
RCS file: /cvsroot/python/python/nondist/sandbox/statistics/test_statistics.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** test_statistics.py	15 Feb 2004 06:03:57 -0000	1.1
--- test_statistics.py	17 Feb 2004 13:00:16 -0000	1.2
***************
*** 58,61 ****
--- 58,74 ----
 self.assertEqual(select(a, nth), nth)
 
+ # Try with sorted data
+ a = range(n)
+ for i in xrange(100):
+ nth = random.randrange(n)
+ self.assertEqual(select(a, nth), nth)
+ 
+ # Try with reverse sorted data
+ a = range(n)
+ a.reverse()
+ for i in xrange(100):
+ nth = random.randrange(n)
+ self.assertEqual(select(a, nth), nth)
+ 
 def test_nlargest(self):
 n = 10