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

[rhettinger at users.sourceforge.net]

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