Python code coverage for Lib/test/sortperf.py

#	count	content
1	n/a	"""Sort performance test.
2	n/a
3	n/a	See main() for command line syntax.
4	n/a	See tabulate() for output format.
5	n/a
6	n/a	"""
7	n/a
8	n/a	import sys
9	n/a	import time
10	n/a	import random
11	n/a	import marshal
12	n/a	import tempfile
13	n/a	import os
14	n/a
15	n/a	td = tempfile.gettempdir()
16	n/a
17	n/a	def randfloats(n):
18	n/a	"""Return a list of n random floats in [0, 1)."""
19	n/a	# Generating floats is expensive, so this writes them out to a file in
20	n/a	# a temp directory. If the file already exists, it just reads them
21	n/a	# back in and shuffles them a bit.
22	n/a	fn = os.path.join(td, "rr%06d" % n)
23	n/a	try:
24	n/a	fp = open(fn, "rb")
25	n/a	except OSError:
26	n/a	r = random.random
27	n/a	result = [r() for i in range(n)]
28	n/a	try:
29	n/a	try:
30	n/a	fp = open(fn, "wb")
31	n/a	marshal.dump(result, fp)
32	n/a	fp.close()
33	n/a	fp = None
34	n/a	finally:
35	n/a	if fp:
36	n/a	try:
37	n/a	os.unlink(fn)
38	n/a	except OSError:
39	n/a	pass
40	n/a	except OSError as msg:
41	n/a	print("can't write", fn, ":", msg)
42	n/a	else:
43	n/a	result = marshal.load(fp)
44	n/a	fp.close()
45	n/a	# Shuffle it a bit...
46	n/a	for i in range(10):
47	n/a	i = random.randrange(n)
48	n/a	temp = result[:i]
49	n/a	del result[:i]
50	n/a	temp.reverse()
51	n/a	result.extend(temp)
52	n/a	del temp
53	n/a	assert len(result) == n
54	n/a	return result
55	n/a
56	n/a	def flush():
57	n/a	sys.stdout.flush()
58	n/a
59	n/a	def doit(L):
60	n/a	t0 = time.perf_counter()
61	n/a	L.sort()
62	n/a	t1 = time.perf_counter()
63	n/a	print("%6.2f" % (t1-t0), end=' ')
64	n/a	flush()
65	n/a
66	n/a	def tabulate(r):
67	n/a	r"""Tabulate sort speed for lists of various sizes.
68	n/a
69	n/a	The sizes are 2**i for i in r (the argument, a list).
70	n/a
71	n/a	The output displays i, 2i, and the time to sort arrays of 2i
72	n/a	floating point numbers with the following properties:
73	n/a
74	n/a	*sort: random data
75	n/a	\sort: descending data
76	n/a	/sort: ascending data
77	n/a	3sort: ascending, then 3 random exchanges
78	n/a	+sort: ascending, then 10 random at the end
79	n/a	%sort: ascending, then randomly replace 1% of the elements w/ random values
80	n/a	~sort: many duplicates
81	n/a	=sort: all equal
82	n/a	!sort: worst case scenario
83	n/a
84	n/a	"""
85	n/a	cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"])
86	n/a	fmt = ("%2s %7s" + " %6s"*len(cases))
87	n/a	print(fmt % (("i", "2**i") + cases))
88	n/a	for i in r:
89	n/a	n = 1 << i
90	n/a	L = randfloats(n)
91	n/a	print("%2d %7d" % (i, n), end=' ')
92	n/a	flush()
93	n/a	doit(L) # *sort
94	n/a	L.reverse()
95	n/a	doit(L) # \sort
96	n/a	doit(L) # /sort
97	n/a
98	n/a	# Do 3 random exchanges.
99	n/a	for dummy in range(3):
100	n/a	i1 = random.randrange(n)
101	n/a	i2 = random.randrange(n)
102	n/a	L[i1], L[i2] = L[i2], L[i1]
103	n/a	doit(L) # 3sort
104	n/a
105	n/a	# Replace the last 10 with random floats.
106	n/a	if n >= 10:
107	n/a	L[-10:] = [random.random() for dummy in range(10)]
108	n/a	doit(L) # +sort
109	n/a
110	n/a	# Replace 1% of the elements at random.
111	n/a	for dummy in range(n // 100):
112	n/a	L[random.randrange(n)] = random.random()
113	n/a	doit(L) # %sort
114	n/a
115	n/a	# Arrange for lots of duplicates.
116	n/a	if n > 4:
117	n/a	del L[4:]
118	n/a	L = L * (n // 4)
119	n/a	# Force the elements to be distinct objects, else timings can be
120	n/a	# artificially low.
121	n/a	L = list(map(lambda x: --x, L))
122	n/a	doit(L) # ~sort
123	n/a	del L
124	n/a
125	n/a	# All equal. Again, force the elements to be distinct objects.
126	n/a	L = list(map(abs, [-0.5] * n))
127	n/a	doit(L) # =sort
128	n/a	del L
129	n/a
130	n/a	# This one looks like [3, 2, 1, 0, 0, 1, 2, 3]. It was a bad case
131	n/a	# for an older implementation of quicksort, which used the median
132	n/a	# of the first, last and middle elements as the pivot.
133	n/a	half = n // 2
134	n/a	L = list(range(half - 1, -1, -1))
135	n/a	L.extend(range(half))
136	n/a	# Force to float, so that the timings are comparable. This is
137	n/a	# significantly faster if we leave tham as ints.
138	n/a	L = list(map(float, L))
139	n/a	doit(L) # !sort
140	n/a	print()
141	n/a
142	n/a	def main():
143	n/a	"""Main program when invoked as a script.
144	n/a
145	n/a	One argument: tabulate a single row.
146	n/a	Two arguments: tabulate a range (inclusive).
147	n/a	Extra arguments are used to seed the random generator.
148	n/a
149	n/a	"""
150	n/a	# default range (inclusive)
151	n/a	k1 = 15
152	n/a	k2 = 20
153	n/a	if sys.argv[1:]:
154	n/a	# one argument: single point
155	n/a	k1 = k2 = int(sys.argv[1])
156	n/a	if sys.argv[2:]:
157	n/a	# two arguments: specify range
158	n/a	k2 = int(sys.argv[2])
159	n/a	if sys.argv[3:]:
160	n/a	# derive random seed from remaining arguments
161	n/a	x = 1
162	n/a	for a in sys.argv[3:]:
163	n/a	x = 69069 * x + hash(a)
164	n/a	random.seed(x)
165	n/a	r = range(k1, k2+1) # include the end point
166	n/a	tabulate(r)
167	n/a
168	n/a	if __name__ == '__main__':
169	n/a	main()