1 files changed, 169 insertions, 0 deletions
diff --git a/lib/python2.7/test/sortperf.py b/lib/python2.7/test/sortperf.py
new file mode 100644
index 0000000..cc83ee4
--- /dev/null
+++ b/lib/python2.7/test/sortperf.py
@@ -0,0 +1,169 @@
+"""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()