Lib/test/sortperf.py

   1 """Sort performance test.
   2
   3 See main() for command line syntax.
   4 See tabulate() for output format.
   5
   6 """
   7
   8 import sys
   9 import time
  10 import whrandom
  11 import marshal
  12 import tempfile
  13 import operator
  14 import os
  15
  16 td = tempfile.gettempdir()
  17
  18 def randrange(n):
  19     """Return a random shuffle of range(n)."""
  20     fn = os.path.join(td, "rr%06d" % n)
  21     try:
  22         fp = open(fn, "rb")
  23     except IOError:
  24         result = []
  25         for i in range(n):
  26             result.append(whrandom.random())
  27         try:
  28             try:
  29                 fp = open(fn, "wb")
  30                 marshal.dump(result, fp)
  31                 fp.close()
  32                 fp = None
  33             finally:
  34                 if fp:
  35                     try:
  36                         os.unlink(fn)
  37                     except os.error:
  38                         pass
  39         except IOError, msg:
  40             print "can't write", fn, ":", msg
  41     else:
  42         result = marshal.load(fp)
  43         fp.close()
  44         ##assert len(result) == n
  45         # Shuffle it a bit...
  46         for i in range(10):
  47             i = whrandom.randint(0, n-1)
  48             temp = result[:i]
  49             del result[:i]
  50             temp.reverse()
  51             result[len(result):] = temp
  52             del temp
  53     return result
  54
  55 def fl():
  56     sys.stdout.flush()
  57
  58 def doit(L):
  59     t0 = time.clock()
  60     L.sort()
  61     t1 = time.clock()
  62     print "%6.2f" % (t1-t0),
  63     fl()
  64
  65 def tabulate(r):
  66     """Tabulate sort speed for lists of various sizes.
  67
  68     The sizes are 2**i for i in r (the argument, a list).
  69
  70     The output displays i, 2**i, and the time to sort arrays of 2**i
  71     floating point numbers with the following properties:
  72
  73     *sort: random data
  74     \sort: descending data
  75     /sort: ascending data
  76     ~sort: many duplicates
  77     -sort: all equal
  78     !sort: worst case scenario
  79
  80     """
  81     cases = ("*sort", "\\sort", "/sort", "~sort", "-sort", "!sort")
  82     fmt = ("%2s %6s" + " %6s"*len(cases))
  83     print fmt % (("i", "2**i") + cases)
  84     for i in r:
  85         n = 1<<i
  86         L = randrange(n)
  87         ##assert len(L) == n
  88         print "%2d %6d" % (i, n),
  89         fl()
  90         doit(L) # *sort
  91         L.reverse()
  92         doit(L) # \sort
  93         doit(L) # /sort
  94         if n > 4:
  95             del L[4:]
  96             L = L*(n/4)
  97             L = map(lambda x: --x, L)
  98         doit(L) # ~sort
  99         del L
 100         L = map(abs, [-0.5]*n)
 101         doit(L) # -sort
 102         L = range(n/2-1, -1, -1)
 103         L[len(L):] = range(n/2)
 104         doit(L) # !sort
 105         print
 106
 107 def main():
 108     """Main program when invoked as a script.
 109
 110     One argument: tabulate a single row.
 111     Two arguments: tabulate a range (inclusive).
 112     Extra arguments are used to seed the random generator.
 113
 114     """
 115     # default range (inclusive)
 116     k1 = 15
 117     k2 = 19
 118     if sys.argv[1:]:
 119         # one argument: single point
 120         k1 = k2 = int(sys.argv[1])
 121         if sys.argv[2:]:
 122             # two arguments: specify range
 123             k2 = int(sys.argv[2])
 124             if sys.argv[3:]:
 125                 # derive random seed from remaining arguments
 126                 x, y, z = 0, 0, 0
 127                 for a in sys.argv[3:]:
 128                     h = hash(a)
 129                     h, d = divmod(h, 256)
 130                     h = h & 0xffffff
 131                     x = (x^h^d) & 255
 132                     h = h>>8
 133                     y = (y^h^d) & 255
 134                     h = h>>8
 135                     z = (z^h^d) & 255
 136                 whrandom.seed(x, y, z)
 137     r = range(k1, k2+1)                 # include the end point
 138     tabulate(r)
 139
 140 if __name__ == '__main__':
 141     main()