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 random
  11 import marshal
  12 import tempfile
  13 import os
  14
  15 td = tempfile.gettempdir()
  16
  17 def randfloats(n):
  18     """Return a list of n random floats in [0, 1)."""
  19     # Generating floats is expensive, so this writes them out to a file in
  20     # a temp directory.  If the file already exists, it just reads them
  21     # back in and shuffles them a bit.
  22     fn = os.path.join(td, "rr%06d" % n)
  23     try:
  24         fp = open(fn, "rb")
  25     except IOError:
  26         r = random.random
  27         result = [r() for i in xrange(n)]
  28         try:
  29             try:
  30                 fp = open(fn, "wb")
  31                 marshal.dump(result, fp)
  32                 fp.close()
  33                 fp = None
  34             finally:
  35                 if fp:
  36                     try:
  37                         os.unlink(fn)
  38                     except os.error:
  39                         pass
  40         except IOError, msg:
  41             print "can't write", fn, ":", msg
  42     else:
  43         result = marshal.load(fp)
  44         fp.close()
  45         # Shuffle it a bit...
  46         for i in range(10):
  47             i = random.randrange(n)
  48             temp = result[:i]
  49             del result[:i]
  50             temp.reverse()
  51             result.extend(temp)
  52             del temp
  53     assert len(result) == n
  54     return result
  55
  56 def flush():
  57     sys.stdout.flush()
  58
  59 def doit(L):
  60     t0 = time.clock()
  61     L.sort()
  62     t1 = time.clock()
  63     print "%6.2f" % (t1-t0),
  64     flush()
  65
  66 def tabulate(r):
  67     """Tabulate sort speed for lists of various sizes.
  68
  69     The sizes are 2**i for i in r (the argument, a list).
  70
  71     The output displays i, 2**i, and the time to sort arrays of 2**i
  72     floating point numbers with the following properties:
  73
  74     *sort: random data
  75     \sort: descending data
  76     /sort: ascending data
  77     3sort: ascending, then 3 random exchanges
  78     +sort: ascending, then 10 random at the end
  79     %sort: ascending, then randomly replace 1% of the elements w/ random values
  80     ~sort: many duplicates
  81     =sort: all equal
  82     !sort: worst case scenario
  83
  84     """
  85     cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"])
  86     fmt = ("%2s %7s" + " %6s"*len(cases))
  87     print fmt % (("i", "2**i") + cases)
  88     for i in r:
  89         n = 1 << i
  90         L = randfloats(n)
  91         print "%2d %7d" % (i, n),
  92         flush()
  93         doit(L) # *sort
  94         L.reverse()
  95         doit(L) # \sort
  96         doit(L) # /sort
  97
  98         # Do 3 random exchanges.
  99         for dummy in range(3):
 100             i1 = random.randrange(n)
 101             i2 = random.randrange(n)
 102             L[i1], L[i2] = L[i2], L[i1]
 103         doit(L) # 3sort
 104
 105         # Replace the last 10 with random floats.
 106         if n >= 10:
 107             L[-10:] = [random.random() for dummy in range(10)]
 108         doit(L) # +sort
 109
 110         # Replace 1% of the elements at random.
 111         for dummy in xrange(n // 100):
 112             L[random.randrange(n)] = random.random()
 113         doit(L) # %sort
 114
 115         # Arrange for lots of duplicates.
 116         if n > 4:
 117             del L[4:]
 118             L = L * (n // 4)
 119             # Force the elements to be distinct objects, else timings can be
 120             # artificially low.
 121             L = map(lambda x: --x, L)
 122         doit(L) # ~sort
 123         del L
 124
 125         # All equal.  Again, force the elements to be distinct objects.
 126         L = map(abs, [-0.5] * n)
 127         doit(L) # =sort
 128         del L
 129
 130         # This one looks like [3, 2, 1, 0, 0, 1, 2, 3].  It was a bad case
 131         # for an older implementation of quicksort, which used the median
 132         # of the first, last and middle elements as the pivot.
 133         half = n // 2
 134         L = range(half - 1, -1, -1)
 135         L.extend(range(half))
 136         # Force to float, so that the timings are comparable.  This is
 137         # significantly faster if we leave tham as ints.
 138         L = map(float, L)
 139         doit(L) # !sort
 140         print
 141
 142 def main():
 143     """Main program when invoked as a script.
 144
 145     One argument: tabulate a single row.
 146     Two arguments: tabulate a range (inclusive).
 147     Extra arguments are used to seed the random generator.
 148
 149     """
 150     # default range (inclusive)
 151     k1 = 15
 152     k2 = 20
 153     if sys.argv[1:]:
 154         # one argument: single point
 155         k1 = k2 = int(sys.argv[1])
 156         if sys.argv[2:]:
 157             # two arguments: specify range
 158             k2 = int(sys.argv[2])
 159             if sys.argv[3:]:
 160                 # derive random seed from remaining arguments
 161                 x = 1
 162                 for a in sys.argv[3:]:
 163                     x = 69069 * x + hash(a)
 164                 random.seed(x)
 165     r = range(k1, k2+1)                 # include the end point
 166     tabulate(r)
 167
 168 if __name__ == '__main__':
 169     main()