Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 1 | """Sort performance test. |
| 2 | |
| 3 | See main() for command line syntax. |
| 4 | See tabulate() for output format. |
| 5 | |
| 6 | """ |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 7 | |
| 8 | import sys |
| 9 | import time |
Andrew M. Kuchling | a974561 | 2002-04-10 14:54:39 +0000 | [diff] [blame] | 10 | import random |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 11 | import marshal |
| 12 | import tempfile |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 13 | import os |
| 14 | |
| 15 | td = tempfile.gettempdir() |
| 16 | |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 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. |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 22 | fn = os.path.join(td, "rr%06d" % n) |
| 23 | try: |
| 24 | fp = open(fn, "rb") |
| 25 | except IOError: |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 26 | r = random.random |
| 27 | result = [r() for i in xrange(n)] |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 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() |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 45 | # Shuffle it a bit... |
| 46 | for i in range(10): |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 47 | i = random.randrange(n) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 48 | temp = result[:i] |
| 49 | del result[:i] |
| 50 | temp.reverse() |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 51 | result.extend(temp) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 52 | del temp |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 53 | assert len(result) == n |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 54 | return result |
| 55 | |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 56 | def flush(): |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 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), |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 64 | flush() |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 65 | |
| 66 | def tabulate(r): |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 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 |
Tim Peters | 0a30e64 | 2002-07-20 04:21:51 +0000 | [diff] [blame^] | 77 | 3sort: ascending data but with 3 random exchanges |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 78 | ~sort: many duplicates |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 79 | =sort: all equal |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 80 | !sort: worst case scenario |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 81 | |
| 82 | """ |
Tim Peters | 0a30e64 | 2002-07-20 04:21:51 +0000 | [diff] [blame^] | 83 | cases = ("*sort", "\\sort", "/sort", "3sort", "~sort", "=sort", "!sort") |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 84 | fmt = ("%2s %7s" + " %6s"*len(cases)) |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 85 | print fmt % (("i", "2**i") + cases) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 86 | for i in r: |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 87 | n = 1 << i |
| 88 | L = randfloats(n) |
| 89 | print "%2d %7d" % (i, n), |
| 90 | flush() |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 91 | doit(L) # *sort |
| 92 | L.reverse() |
| 93 | doit(L) # \sort |
| 94 | doit(L) # /sort |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 95 | |
Tim Peters | 0a30e64 | 2002-07-20 04:21:51 +0000 | [diff] [blame^] | 96 | # Do 3 random exchanges. |
| 97 | for dummy in range(3): |
| 98 | i1 = random.randrange(n) |
| 99 | i2 = random.randrange(n) |
| 100 | L[i1], L[i2] = L[i2], L[i1] |
| 101 | doit(L) # 3sort |
| 102 | |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 103 | # Arrange for lots of duplicates. |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 104 | if n > 4: |
Guido van Rossum | b298a30 | 1998-05-12 13:21:31 +0000 | [diff] [blame] | 105 | del L[4:] |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 106 | L = L * (n // 4) |
| 107 | # Force the elements to be distinct objects, else timings can be |
| 108 | # artificially low. |
Guido van Rossum | b298a30 | 1998-05-12 13:21:31 +0000 | [diff] [blame] | 109 | L = map(lambda x: --x, L) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 110 | doit(L) # ~sort |
Guido van Rossum | b298a30 | 1998-05-12 13:21:31 +0000 | [diff] [blame] | 111 | del L |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 112 | |
| 113 | # All equal. Again, force the elements to be distinct objects. |
| 114 | L = map(abs, [-0.5] * n) |
| 115 | doit(L) # =sort |
| 116 | del L |
| 117 | |
| 118 | # This one looks like [3, 2, 1, 0, 0, 1, 2, 3]. It was a bad case |
| 119 | # for an older implementation of quicksort, which used the median |
| 120 | # of the first, last and middle elements as the pivot. It's still |
| 121 | # a worse-than-average case for samplesort, but on the order of a |
| 122 | # measly 5% worse, not a quadratic-time disaster as it was with |
| 123 | # quicksort. |
| 124 | half = n // 2 |
| 125 | L = range(half - 1, -1, -1) |
| 126 | L.extend(range(half)) |
| 127 | # Force to float, so that the timings are comparable. This is |
| 128 | # significantly faster if we leave tham as ints. |
| 129 | L = map(float, L) |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 130 | doit(L) # !sort |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 131 | print |
| 132 | |
| 133 | def main(): |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 134 | """Main program when invoked as a script. |
| 135 | |
| 136 | One argument: tabulate a single row. |
| 137 | Two arguments: tabulate a range (inclusive). |
| 138 | Extra arguments are used to seed the random generator. |
| 139 | |
| 140 | """ |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 141 | # default range (inclusive) |
| 142 | k1 = 15 |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 143 | k2 = 20 |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 144 | if sys.argv[1:]: |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 145 | # one argument: single point |
Eric S. Raymond | fc170b1 | 2001-02-09 11:51:27 +0000 | [diff] [blame] | 146 | k1 = k2 = int(sys.argv[1]) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 147 | if sys.argv[2:]: |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 148 | # two arguments: specify range |
Eric S. Raymond | fc170b1 | 2001-02-09 11:51:27 +0000 | [diff] [blame] | 149 | k2 = int(sys.argv[2]) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 150 | if sys.argv[3:]: |
| 151 | # derive random seed from remaining arguments |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 152 | x = 1 |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 153 | for a in sys.argv[3:]: |
Tim Peters | 8b6ec79 | 2002-07-18 15:53:32 +0000 | [diff] [blame] | 154 | x = 69069 * x + hash(a) |
| 155 | random.seed(x) |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 156 | r = range(k1, k2+1) # include the end point |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 157 | tabulate(r) |
| 158 | |
| 159 | if __name__ == '__main__': |
| 160 | main() |