"""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()