Back to index

python3.2  3.2.2
Functions | Variables
test.sortperf Namespace Reference

Functions

def randfloats
def flush
def doit
def tabulate
def main

Variables

tuple td = tempfile.gettempdir()

Detailed Description

Sort performance test.

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

Function Documentation

def test.sortperf.doit (   L)

Definition at line 59 of file sortperf.py.

00059 
00060 def doit(L):
00061     t0 = time.clock()
00062     L.sort()
00063     t1 = time.clock()
00064     print("%6.2f" % (t1-t0), end=' ')
00065     flush()

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 56 of file sortperf.py.

00056 
00057 def flush():
00058     sys.stdout.flush()

Here is the caller graph for this function:

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.

Definition at line 142 of file sortperf.py.

00142 
00143 def main():
00144     """Main program when invoked as a script.
00145 
00146     One argument: tabulate a single row.
00147     Two arguments: tabulate a range (inclusive).
00148     Extra arguments are used to seed the random generator.
00149 
00150     """
00151     # default range (inclusive)
00152     k1 = 15
00153     k2 = 20
00154     if sys.argv[1:]:
00155         # one argument: single point
00156         k1 = k2 = int(sys.argv[1])
00157         if sys.argv[2:]:
00158             # two arguments: specify range
00159             k2 = int(sys.argv[2])
00160             if sys.argv[3:]:
00161                 # derive random seed from remaining arguments
00162                 x = 1
00163                 for a in sys.argv[3:]:
00164                     x = 69069 * x + hash(a)
00165                 random.seed(x)
00166     r = range(k1, k2+1)                 # include the end point
00167     tabulate(r)

Here is the call graph for this function:

Return a list of n random floats in [0, 1).

Definition at line 17 of file sortperf.py.

00017 
00018 def randfloats(n):
00019     """Return a list of n random floats in [0, 1)."""
00020     # Generating floats is expensive, so this writes them out to a file in
00021     # a temp directory.  If the file already exists, it just reads them
00022     # back in and shuffles them a bit.
00023     fn = os.path.join(td, "rr%06d" % n)
00024     try:
00025         fp = open(fn, "rb")
00026     except IOError:
00027         r = random.random
00028         result = [r() for i in range(n)]
00029         try:
00030             try:
00031                 fp = open(fn, "wb")
00032                 marshal.dump(result, fp)
00033                 fp.close()
00034                 fp = None
00035             finally:
00036                 if fp:
00037                     try:
00038                         os.unlink(fn)
00039                     except os.error:
00040                         pass
00041         except IOError as msg:
00042             print("can't write", fn, ":", msg)
00043     else:
00044         result = marshal.load(fp)
00045         fp.close()
00046         # Shuffle it a bit...
00047         for i in range(10):
00048             i = random.randrange(n)
00049             temp = result[:i]
00050             del result[:i]
00051             temp.reverse()
00052             result.extend(temp)
00053             del temp
00054     assert len(result) == n
00055     return result

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 66 of file sortperf.py.

00066 
00067 def tabulate(r):
00068     """Tabulate sort speed for lists of various sizes.
00069 
00070     The sizes are 2**i for i in r (the argument, a list).
00071 
00072     The output displays i, 2**i, and the time to sort arrays of 2**i
00073     floating point numbers with the following properties:
00074 
00075     *sort: random data
00076     \sort: descending data
00077     /sort: ascending data
00078     3sort: ascending, then 3 random exchanges
00079     +sort: ascending, then 10 random at the end
00080     %sort: ascending, then randomly replace 1% of the elements w/ random values
00081     ~sort: many duplicates
00082     =sort: all equal
00083     !sort: worst case scenario
00084 
00085     """
00086     cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"])
00087     fmt = ("%2s %7s" + " %6s"*len(cases))
00088     print(fmt % (("i", "2**i") + cases))
00089     for i in r:
00090         n = 1 << i
00091         L = randfloats(n)
00092         print("%2d %7d" % (i, n), end=' ')
00093         flush()
00094         doit(L) # *sort
00095         L.reverse()
00096         doit(L) # \sort
00097         doit(L) # /sort
00098 
00099         # Do 3 random exchanges.
00100         for dummy in range(3):
00101             i1 = random.randrange(n)
00102             i2 = random.randrange(n)
00103             L[i1], L[i2] = L[i2], L[i1]
00104         doit(L) # 3sort
00105 
00106         # Replace the last 10 with random floats.
00107         if n >= 10:
00108             L[-10:] = [random.random() for dummy in range(10)]
00109         doit(L) # +sort
00110 
00111         # Replace 1% of the elements at random.
00112         for dummy in range(n // 100):
00113             L[random.randrange(n)] = random.random()
00114         doit(L) # %sort
00115 
00116         # Arrange for lots of duplicates.
00117         if n > 4:
00118             del L[4:]
00119             L = L * (n // 4)
00120             # Force the elements to be distinct objects, else timings can be
00121             # artificially low.
00122             L = list(map(lambda x: --x, L))
00123         doit(L) # ~sort
00124         del L
00125 
00126         # All equal.  Again, force the elements to be distinct objects.
00127         L = list(map(abs, [-0.5] * n))
00128         doit(L) # =sort
00129         del L
00130 
00131         # This one looks like [3, 2, 1, 0, 0, 1, 2, 3].  It was a bad case
00132         # for an older implementation of quicksort, which used the median
00133         # of the first, last and middle elements as the pivot.
00134         half = n // 2
00135         L = list(range(half - 1, -1, -1))
00136         L.extend(range(half))
00137         # Force to float, so that the timings are comparable.  This is
00138         # significantly faster if we leave tham as ints.
00139         L = list(map(float, L))
00140         doit(L) # !sort
00141         print()

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

Definition at line 15 of file sortperf.py.