# 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, 2**i, and the time to sort arrays of 2**i |

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() |