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

tim_one@users.sourceforge.net tim_one@users.sourceforge.net
Sun, 21 Jul 2002 10:37:05 -0700


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

Modified Files:
	sortperf.py 
Log Message:
New test "+sort", tacking 10 random floats on to the end of a sorted
array.  Our samplesort special-cases the snot out of this, running about
12x faster than *sort.  The experimental mergesort runs it about 8x
faster than *sort without special-casing, but should really do better
than that (when merging runs of different lengths, right now it only
does something clever about finding where the second run begins in
the first and where the first run ends in the second, and that's more
of a temp-memory optimization).


Index: sortperf.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/test/sortperf.py,v
retrieving revision 1.9
retrieving revision 1.10
diff -C2 -d -r1.9 -r1.10
*** sortperf.py	20 Jul 2002 04:21:51 -0000	1.9
--- sortperf.py	21 Jul 2002 17:37:03 -0000	1.10
***************
*** 75,79 ****
      \sort: descending data
      /sort: ascending data
!     3sort: ascending data but with 3 random exchanges
      ~sort: many duplicates
      =sort: all equal
--- 75,80 ----
      \sort: descending data
      /sort: ascending data
!     3sort: ascending, then 3 random exchanges
!     +sort: ascending, then 10 random at the end
      ~sort: many duplicates
      =sort: all equal
***************
*** 81,85 ****
  
      """
!     cases = ("*sort", "\\sort", "/sort", "3sort", "~sort", "=sort", "!sort")
      fmt = ("%2s %7s" + " %6s"*len(cases))
      print fmt % (("i", "2**i") + cases)
--- 82,86 ----
  
      """
!     cases = tuple([ch + "sort" for ch in r"*\/3+~=!"])
      fmt = ("%2s %7s" + " %6s"*len(cases))
      print fmt % (("i", "2**i") + cases)
***************
*** 101,104 ****
--- 102,110 ----
          doit(L) # 3sort
  
+         # Replace the last 10 with random floats.
+         if n >= 10:
+             L[-10:] = [random.random() for dummy in range(10)]
+         doit(L) # +sort
+ 
          # Arrange for lots of duplicates.
          if n > 4:
***************
*** 118,125 ****
          # This one looks like [3, 2, 1, 0, 0, 1, 2, 3].  It was a bad case
          # for an older implementation of quicksort, which used the median
!         # of the first, last and middle elements as the pivot.  It's still
!         # a worse-than-average case for samplesort, but on the order of a
!         # measly 5% worse, not a quadratic-time disaster as it was with
!         # quicksort.
          half = n // 2
          L = range(half - 1, -1, -1)
--- 124,128 ----
          # This one looks like [3, 2, 1, 0, 0, 1, 2, 3].  It was a bad case
          # for an older implementation of quicksort, which used the median
!         # of the first, last and middle elements as the pivot.
          half = n // 2
          L = range(half - 1, -1, -1)