"""Sort performance test.
See main() for command line syntax.
See tabulate() for output format.
td
= tempfile
.gettempdir()
"""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
)
result
= [r() for i
in xrange(n
)]
print "can't write", fn
, ":", msg
result
= marshal
.load(fp
)
"""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:
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: worst case scenario
cases
= tuple([ch
+ "sort" for ch
in r
"*\/3+%~=!"])
fmt
= ("%2s %7s" + " %6s"*len(cases
))
print fmt
% (("i", "2**i") + cases
)
print "%2d %7d" % (i
, n
),
L
[i1
], L
[i2
] = L
[i2
], L
[i1
]
# Replace the last 10 with random floats.
L
[-10:] = [random
.random() for dummy
in range(10)]
# Replace 1% of the elements at random.
for dummy
in xrange(n
// 100):
L
[random
.randrange(n
)] = random
.random()
# Arrange for lots of duplicates.
# Force the elements to be distinct objects, else timings can be
L
= map(lambda x
: --x
, L
)
# All equal. Again, force the elements to be distinct objects.
# 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.
L
= range(half
- 1, -1, -1)
# Force to float, so that the timings are comparable. This is
# significantly faster if we leave tham as ints.
"""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)
# one argument: single point
k1
= k2
= int(sys
.argv
[1])
# two arguments: specify range
# derive random seed from remaining arguments
r
= range(k1
, k2
+1) # include the end point
if __name__
== '__main__':