Lib/test/sortperf.py

"""Sort performance test.

See main() for command line syntax.
See tabulate() for output format.

"""

import sys
import time
import whrandom
import marshal
import tempfile
import operator
import os

td = tempfile.gettempdir()

def randrange(n):
    """Return a random shuffle of range(n)."""
    fn = os.path.join(td, "rr%06d" % n)
    try:
        fp = open(fn, "rb")
    except IOError:
        result = []
        for i in range(n):
            result.append(whrandom.random())
        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()
        ##assert len(result) == n
        # Shuffle it a bit...
        for i in range(10):
            i = whrandom.randint(0, n-1)
            temp = result[:i]
            del result[:i]
            temp.reverse()
            result[len(result):] = temp
            del temp
    return result

def fl():
    sys.stdout.flush()

def doit(L):
    t0 = time.clock()
    L.sort()
    t1 = time.clock()
    print "%6.2f" % (t1-t0),
    fl()

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
    ~sort: many duplicates
    -sort: all equal
    !sort: worst case scenario

    """
    cases = ("*sort", "\\sort", "/sort", "~sort", "-sort", "!sort")
    fmt = ("%2s %6s" + " %6s"*len(cases))
    print fmt % (("i", "2**i") + cases)
    for i in r:
        n = 1<<i
        L = randrange(n)
        ##assert len(L) == n
        print "%2d %6d" % (i, n),
        fl()
        doit(L) # *sort
        L.reverse()
        doit(L) # \sort
        doit(L) # /sort
        if n > 4:
            del L[4:]
            L = L*(n/4)
            L = map(lambda x: --x, L)
        doit(L) # ~sort
        del L
        L = map(abs, [-0.5]*n)
        doit(L) # -sort
        L = range(n/2-1, -1, -1)
        L[len(L):] = range(n/2)
        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 = 19
    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, y, z = 0, 0, 0
                for a in sys.argv[3:]:
                    h = hash(a)
                    h, d = divmod(h, 256)
                    h = h & 0xffffff
                    x = (x^h^d) & 255
                    h = h>>8
                    y = (y^h^d) & 255
                    h = h>>8
                    z = (z^h^d) & 255
                whrandom.seed(x, y, z)
    r = range(k1, k2+1)                 # include the end point
    tabulate(r)

if __name__ == '__main__':
    main()