[Python-checkins] python/dist/src/Lib/test sortperf.py,1.10,1.11

tim_one@users.sourceforge.net tim_one@users.sourceforge.net
Thu, 01 Aug 2002 22:46:11 -0700


Update of /cvsroot/python/python/dist/src/Lib/test
In directory usw-pr-cvs1:/tmp/cvs-serv28185/python/Lib/test

Modified Files:
	sortperf.py 
Log Message:
New test %sort.  This takes a sorted list, picks 1% of the list positions
at random, and replaces the elements at those positions with new random
values.  I was pleasantly surprised by how fast this goes!  It's hard to
conceive of an algorithm that could special-case for this effectively.
Plus it's exactly what happens if a burst of gamma rays corrupts your
sorted database on disk <wink>.

 i    2**i  *sort  ...  %sort
15   32768   0.18  ...   0.03
16   65536   0.24  ...   0.04
17  131072   0.53  ...   0.08
18  262144   1.17  ...   0.16
19  524288   2.56  ...   0.35
20 1048576   5.54  ...   0.77


Index: sortperf.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/test/sortperf.py,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** sortperf.py	21 Jul 2002 17:37:03 -0000	1.10
--- sortperf.py	2 Aug 2002 05:46:09 -0000	1.11
***************
*** 77,80 ****
--- 77,81 ----
      3sort: ascending, then 3 random exchanges
      +sort: ascending, then 10 random at the end
+     %sort: ascending, then randomly replace 1% of the elements w/ random values
      ~sort: many duplicates
      =sort: all equal
***************
*** 82,86 ****
  
      """
!     cases = tuple([ch + "sort" for ch in r"*\/3+~=!"])
      fmt = ("%2s %7s" + " %6s"*len(cases))
      print fmt % (("i", "2**i") + cases)
--- 83,87 ----
  
      """
!     cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"])
      fmt = ("%2s %7s" + " %6s"*len(cases))
      print fmt % (("i", "2**i") + cases)
***************
*** 106,109 ****
--- 107,115 ----
              L[-10:] = [random.random() for dummy in range(10)]
          doit(L) # +sort
+ 
+         # Replace 1% of the elements at random.
+         for dummy in xrange(n // 100):
+             L[random.randrange(n)] = random.random()
+         doit(L) # %sort
  
          # Arrange for lots of duplicates.