|
| 1 | +"""Sort performance test.""" |
| 2 | + |
| 3 | +import sys |
| 4 | +import time |
| 5 | +import whrandom |
| 6 | +import marshal |
| 7 | +import tempfile |
| 8 | +import operator |
| 9 | +import os |
| 10 | + |
| 11 | +td = tempfile.gettempdir() |
| 12 | + |
| 13 | +def randrange(n): |
| 14 | + """Return a random shuffle of range(n).""" |
| 15 | + fn = os.path.join(td, "rr%06d" % n) |
| 16 | + try: |
| 17 | + fp = open(fn, "rb") |
| 18 | + except IOError: |
| 19 | + result = [] |
| 20 | + for i in range(n): |
| 21 | + result.append(whrandom.random()) |
| 22 | + try: |
| 23 | + try: |
| 24 | + fp = open(fn, "wb") |
| 25 | + marshal.dump(result, fp) |
| 26 | + fp.close() |
| 27 | + fp = None |
| 28 | + finally: |
| 29 | + if fp: |
| 30 | + try: |
| 31 | + os.unlink(fn) |
| 32 | + except os.error: |
| 33 | + pass |
| 34 | + except IOError, msg: |
| 35 | + print "can't write", fn, ":", msg |
| 36 | + else: |
| 37 | + result = marshal.load(fp) |
| 38 | + fp.close() |
| 39 | + ##assert len(result) == n |
| 40 | + # Shuffle it a bit... |
| 41 | + for i in range(10): |
| 42 | + i = whrandom.randint(0, n-1) |
| 43 | + temp = result[:i] |
| 44 | + del result[:i] |
| 45 | + temp.reverse() |
| 46 | + result[len(result):] = temp |
| 47 | + del temp |
| 48 | + return result |
| 49 | + |
| 50 | +def fl(): |
| 51 | + sys.stdout.flush() |
| 52 | + |
| 53 | +def doit(L): |
| 54 | + t0 = time.clock() |
| 55 | + L.sort() |
| 56 | + t1 = time.clock() |
| 57 | + print "%6.2f" % (t1-t0), |
| 58 | + fl() |
| 59 | + |
| 60 | +def tabulate(r): |
| 61 | + fmt = ("%2s %6s" + " %6s"*5) |
| 62 | + print fmt % ("i", "2**i", "*sort", "\\sort", "/sort", "~sort", "-sort") |
| 63 | + for i in r: |
| 64 | + n = 1<<i |
| 65 | + L = randrange(n) |
| 66 | + ##assert len(L) == n |
| 67 | + print "%2d %6d" % (i, n), |
| 68 | + fl() |
| 69 | + doit(L) # *sort |
| 70 | + L.reverse() |
| 71 | + doit(L) # \sort |
| 72 | + doit(L) # /sort |
| 73 | + if n > 4: |
| 74 | + L = map(operator.neg, map(operator.neg, L[:4]*(n/4))) |
| 75 | + doit(L) # ~sort |
| 76 | + L = map(abs, [-0.5]*n) |
| 77 | + doit(L) # -sort |
| 78 | + print |
| 79 | + |
| 80 | +def main(): |
| 81 | + import string |
| 82 | + # default range (inclusive) |
| 83 | + k1 = 15 |
| 84 | + k2 = 19 |
| 85 | + # one argument: single point |
| 86 | + # two arguments: specify range |
| 87 | + if sys.argv[1:]: |
| 88 | + k1 = string.atoi(sys.argv[1]) |
| 89 | + k2 = k1 |
| 90 | + if sys.argv[2:]: |
| 91 | + k2 = string.atoi(sys.argv[2]) |
| 92 | + if sys.argv[3:]: |
| 93 | + # derive random seed from remaining arguments |
| 94 | + x, y, z = 0, 0, 0 |
| 95 | + for a in sys.argv[3:]: |
| 96 | + h = hash(a) |
| 97 | + h, d = divmod(h, 256) |
| 98 | + h = h & 0xffffff |
| 99 | + x = (x^h^d) & 255 |
| 100 | + h = h>>8 |
| 101 | + y = (y^h^d) & 255 |
| 102 | + h = h>>8 |
| 103 | + z = (z^h^d) & 255 |
| 104 | + whrandom.seed(x, y, z) |
| 105 | + r = range(k1, k2+1) |
| 106 | + tabulate(r) |
| 107 | + |
| 108 | +if __name__ == '__main__': |
| 109 | + main() |
0 commit comments