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 |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 10 | import whrandom |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 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): |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 26 | result.append(whrandom.random()) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 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): |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 47 | i = whrandom.randint(0, n-1) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 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): |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 78 | !sort: worst case scenario |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 79 | |
| 80 | """ |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 81 | cases = ("*sort", "\\sort", "/sort", "~sort", "-sort", "!sort") |
| 82 | fmt = ("%2s %6s" + " %6s"*len(cases)) |
| 83 | print fmt % (("i", "2**i") + cases) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 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: |
Guido van Rossum | b298a30 | 1998-05-12 13:21:31 +0000 | [diff] [blame] | 95 | del L[4:] |
| 96 | L = L*(n/4) |
| 97 | L = map(lambda x: --x, L) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 98 | doit(L) # ~sort |
Guido van Rossum | b298a30 | 1998-05-12 13:21:31 +0000 | [diff] [blame] | 99 | del L |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 100 | L = map(abs, [-0.5]*n) |
| 101 | doit(L) # -sort |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 102 | L = range(n/2-1, -1, -1) |
| 103 | L[len(L):] = range(n/2) |
| 104 | doit(L) # !sort |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 105 | print |
| 106 | |
| 107 | def main(): |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 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 | """ |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 115 | # default range (inclusive) |
| 116 | k1 = 15 |
| 117 | k2 = 19 |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 118 | if sys.argv[1:]: |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 119 | # one argument: single point |
Eric S. Raymond | fc170b1 | 2001-02-09 11:51:27 +0000 | [diff] [blame] | 120 | k1 = k2 = int(sys.argv[1]) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 121 | if sys.argv[2:]: |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 122 | # two arguments: specify range |
Eric S. Raymond | fc170b1 | 2001-02-09 11:51:27 +0000 | [diff] [blame] | 123 | k2 = int(sys.argv[2]) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 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 |
Guido van Rossum | 16653cb | 1998-05-26 15:05:12 +0000 | [diff] [blame] | 136 | whrandom.seed(x, y, z) |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 137 | r = range(k1, k2+1) # include the end point |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 138 | tabulate(r) |
| 139 | |
| 140 | if __name__ == '__main__': |
| 141 | main() |