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 |
| 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): |
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 |
| 78 | |
| 79 | """ |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 80 | fmt = ("%2s %6s" + " %6s"*5) |
| 81 | print fmt % ("i", "2**i", "*sort", "\\sort", "/sort", "~sort", "-sort") |
| 82 | for i in r: |
| 83 | n = 1<<i |
| 84 | L = randrange(n) |
| 85 | ##assert len(L) == n |
| 86 | print "%2d %6d" % (i, n), |
| 87 | fl() |
| 88 | doit(L) # *sort |
| 89 | L.reverse() |
| 90 | doit(L) # \sort |
| 91 | doit(L) # /sort |
| 92 | if n > 4: |
Guido van Rossum | b298a30 | 1998-05-12 13:21:31 +0000 | [diff] [blame^] | 93 | del L[4:] |
| 94 | L = L*(n/4) |
| 95 | L = map(lambda x: --x, L) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 96 | doit(L) # ~sort |
Guido van Rossum | b298a30 | 1998-05-12 13:21:31 +0000 | [diff] [blame^] | 97 | del L |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 98 | L = map(abs, [-0.5]*n) |
| 99 | doit(L) # -sort |
| 100 | print |
| 101 | |
| 102 | def main(): |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 103 | """Main program when invoked as a script. |
| 104 | |
| 105 | One argument: tabulate a single row. |
| 106 | Two arguments: tabulate a range (inclusive). |
| 107 | Extra arguments are used to seed the random generator. |
| 108 | |
| 109 | """ |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 110 | import string |
| 111 | # default range (inclusive) |
| 112 | k1 = 15 |
| 113 | k2 = 19 |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 114 | if sys.argv[1:]: |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 115 | # one argument: single point |
| 116 | k1 = k2 = string.atoi(sys.argv[1]) |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 117 | if sys.argv[2:]: |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 118 | # two arguments: specify range |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 119 | k2 = string.atoi(sys.argv[2]) |
| 120 | if sys.argv[3:]: |
| 121 | # derive random seed from remaining arguments |
| 122 | x, y, z = 0, 0, 0 |
| 123 | for a in sys.argv[3:]: |
| 124 | h = hash(a) |
| 125 | h, d = divmod(h, 256) |
| 126 | h = h & 0xffffff |
| 127 | x = (x^h^d) & 255 |
| 128 | h = h>>8 |
| 129 | y = (y^h^d) & 255 |
| 130 | h = h>>8 |
| 131 | z = (z^h^d) & 255 |
| 132 | whrandom.seed(x, y, z) |
Guido van Rossum | 03e35c5 | 1998-05-10 18:27:29 +0000 | [diff] [blame] | 133 | r = range(k1, k2+1) # include the end point |
Guido van Rossum | ea176b6 | 1998-05-10 18:20:05 +0000 | [diff] [blame] | 134 | tabulate(r) |
| 135 | |
| 136 | if __name__ == '__main__': |
| 137 | main() |