ยปCore Development>Code coverage>Lib/test/sortperf.py

Python code coverage for Lib/test/sortperf.py

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