| """Sort performance test. |
| |
| See main() for command line syntax. |
| See tabulate() for output format. |
| |
| """ |
| |
| import sys |
| import time |
| import random |
| import marshal |
| import tempfile |
| import os |
| |
| td = tempfile.gettempdir() |
| |
| def randfloats(n): |
| """Return a list of n random floats in [0, 1).""" |
| # Generating floats is expensive, so this writes them out to a file in |
| # a temp directory. If the file already exists, it just reads them |
| # back in and shuffles them a bit. |
| fn = os.path.join(td, "rr%06d" % n) |
| try: |
| fp = open(fn, "rb") |
| except IOError: |
| r = random.random |
| result = [r() for i in xrange(n)] |
| try: |
| try: |
| fp = open(fn, "wb") |
| marshal.dump(result, fp) |
| fp.close() |
| fp = None |
| finally: |
| if fp: |
| try: |
| os.unlink(fn) |
| except os.error: |
| pass |
| except IOError, msg: |
| print "can't write", fn, ":", msg |
| else: |
| result = marshal.load(fp) |
| fp.close() |
| # Shuffle it a bit... |
| for i in range(10): |
| i = random.randrange(n) |
| temp = result[:i] |
| del result[:i] |
| temp.reverse() |
| result.extend(temp) |
| del temp |
| assert len(result) == n |
| return result |
| |
| def flush(): |
| sys.stdout.flush() |
| |
| def doit(L): |
| t0 = time.clock() |
| L.sort() |
| t1 = time.clock() |
| print "%6.2f" % (t1-t0), |
| flush() |
| |
| def tabulate(r): |
| """Tabulate sort speed for lists of various sizes. |
| |
| The sizes are 2**i for i in r (the argument, a list). |
| |
| The output displays i, 2**i, and the time to sort arrays of 2**i |
| floating point numbers with the following properties: |
| |
| *sort: random data |
| \sort: descending data |
| /sort: ascending data |
| 3sort: ascending, then 3 random exchanges |
| +sort: ascending, then 10 random at the end |
| %sort: ascending, then randomly replace 1% of the elements w/ random values |
| ~sort: many duplicates |
| =sort: all equal |
| !sort: worst case scenario |
| |
| """ |
| cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"]) |
| fmt = ("%2s %7s" + " %6s"*len(cases)) |
| print fmt % (("i", "2**i") + cases) |
| for i in r: |
| n = 1 << i |
| L = randfloats(n) |
| print "%2d %7d" % (i, n), |
| flush() |
| doit(L) # *sort |
| L.reverse() |
| doit(L) # \sort |
| doit(L) # /sort |
| |
| # Do 3 random exchanges. |
| for dummy in range(3): |
| i1 = random.randrange(n) |
| i2 = random.randrange(n) |
| L[i1], L[i2] = L[i2], L[i1] |
| doit(L) # 3sort |
| |
| # Replace the last 10 with random floats. |
| if n >= 10: |
| L[-10:] = [random.random() for dummy in range(10)] |
| doit(L) # +sort |
| |
| # Replace 1% of the elements at random. |
| for dummy in xrange(n // 100): |
| L[random.randrange(n)] = random.random() |
| doit(L) # %sort |
| |
| # Arrange for lots of duplicates. |
| if n > 4: |
| del L[4:] |
| L = L * (n // 4) |
| # Force the elements to be distinct objects, else timings can be |
| # artificially low. |
| L = map(lambda x: --x, L) |
| doit(L) # ~sort |
| del L |
| |
| # All equal. Again, force the elements to be distinct objects. |
| L = map(abs, [-0.5] * n) |
| doit(L) # =sort |
| del L |
| |
| # This one looks like [3, 2, 1, 0, 0, 1, 2, 3]. It was a bad case |
| # for an older implementation of quicksort, which used the median |
| # of the first, last and middle elements as the pivot. |
| half = n // 2 |
| L = range(half - 1, -1, -1) |
| L.extend(range(half)) |
| # Force to float, so that the timings are comparable. This is |
| # significantly faster if we leave tham as ints. |
| L = map(float, L) |
| doit(L) # !sort |
| print |
| |
| def main(): |
| """Main program when invoked as a script. |
| |
| One argument: tabulate a single row. |
| Two arguments: tabulate a range (inclusive). |
| Extra arguments are used to seed the random generator. |
| |
| """ |
| # default range (inclusive) |
| k1 = 15 |
| k2 = 20 |
| if sys.argv[1:]: |
| # one argument: single point |
| k1 = k2 = int(sys.argv[1]) |
| if sys.argv[2:]: |
| # two arguments: specify range |
| k2 = int(sys.argv[2]) |
| if sys.argv[3:]: |
| # derive random seed from remaining arguments |
| x = 1 |
| for a in sys.argv[3:]: |
| x = 69069 * x + hash(a) |
| random.seed(x) |
| r = range(k1, k2+1) # include the end point |
| tabulate(r) |
| |
| if __name__ == '__main__': |
| main() |