0001 """Sort performance test. 0002 0003 See main() for command line syntax. 0004 See tabulate() for output format. 0005 0006 """ 0007 0008 import sys 0009 import time 0010 import random 0011 import marshal 0012 import tempfile 0013 import os 0014 0015 td = tempfile.gettempdir() 0016 0017 def randfloats(n): 0018 """Return a list of n random floats in [0, 1).""" 0019 # Generating floats is expensive, so this writes them out to a file in 0020 # a temp directory. If the file already exists, it just reads them 0021 # back in and shuffles them a bit. 0022 fn = os.path.join(td, "rr%06d" % n) 0023 try: 0024 fp = open(fn, "rb") 0025 except IOError: 0026 r = random.random 0027 result = [r() for i in xrange(n)] 0028 try: 0029 try: 0030 fp = open(fn, "wb") 0031 marshal.dump(result, fp) 0032 fp.close() 0033 fp = None 0034 finally: 0035 if fp: 0036 try: 0037 os.unlink(fn) 0038 except os.error: 0039 pass 0040 except IOError, msg: 0041 print "can't write", fn, ":", msg 0042 else: 0043 result = marshal.load(fp) 0044 fp.close() 0045 # Shuffle it a bit... 0046 for i in range(10): 0047 i = random.randrange(n) 0048 temp = result[:i] 0049 del result[:i] 0050 temp.reverse() 0051 result.extend(temp) 0052 del temp 0053 assert len(result) == n 0054 return result 0055 0056 def flush(): 0057 sys.stdout.flush() 0058 0059 def doit(L): 0060 t0 = time.clock() 0061 L.sort() 0062 t1 = time.clock() 0063 print "%6.2f" % (t1-t0), 0064 flush() 0065 0066 def tabulate(r): 0067 """Tabulate sort speed for lists of various sizes. 0068 0069 The sizes are 2**i for i in r (the argument, a list). 0070 0071 The output displays i, 2**i, and the time to sort arrays of 2**i 0072 floating point numbers with the following properties: 0073 0074 *sort: random data 0075 \sort: descending data 0076 /sort: ascending data 0077 3sort: ascending, then 3 random exchanges 0078 +sort: ascending, then 10 random at the end 0079 %sort: ascending, then randomly replace 1% of the elements w/ random values 0080 ~sort: many duplicates 0081 =sort: all equal 0082 !sort: worst case scenario 0083 0084 """ 0085 cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"]) 0086 fmt = ("%2s %7s" + " %6s"*len(cases)) 0087 print fmt % (("i", "2**i") + cases) 0088 for i in r: 0089 n = 1 << i 0090 L = randfloats(n) 0091 print "%2d %7d" % (i, n), 0092 flush() 0093 doit(L) # *sort 0094 L.reverse() 0095 doit(L) # \sort 0096 doit(L) # /sort 0097 0098 # Do 3 random exchanges. 0099 for dummy in range(3): 0100 i1 = random.randrange(n) 0101 i2 = random.randrange(n) 0102 L[i1], L[i2] = L[i2], L[i1] 0103 doit(L) # 3sort 0104 0105 # Replace the last 10 with random floats. 0106 if n >= 10: 0107 L[-10:] = [random.random() for dummy in range(10)] 0108 doit(L) # +sort 0109 0110 # Replace 1% of the elements at random. 0111 for dummy in xrange(n // 100): 0112 L[random.randrange(n)] = random.random() 0113 doit(L) # %sort 0114 0115 # Arrange for lots of duplicates. 0116 if n > 4: 0117 del L[4:] 0118 L = L * (n // 4) 0119 # Force the elements to be distinct objects, else timings can be 0120 # artificially low. 0121 L = map(lambda x: --x, L) 0122 doit(L) # ~sort 0123 del L 0124 0125 # All equal. Again, force the elements to be distinct objects. 0126 L = map(abs, [-0.5] * n) 0127 doit(L) # =sort 0128 del L 0129 0130 # This one looks like [3, 2, 1, 0, 0, 1, 2, 3]. It was a bad case 0131 # for an older implementation of quicksort, which used the median 0132 # of the first, last and middle elements as the pivot. 0133 half = n // 2 0134 L = range(half - 1, -1, -1) 0135 L.extend(range(half)) 0136 # Force to float, so that the timings are comparable. This is 0137 # significantly faster if we leave tham as ints. 0138 L = map(float, L) 0139 doit(L) # !sort 0140 print 0141 0142 def main(): 0143 """Main program when invoked as a script. 0144 0145 One argument: tabulate a single row. 0146 Two arguments: tabulate a range (inclusive). 0147 Extra arguments are used to seed the random generator. 0148 0149 """ 0150 # default range (inclusive) 0151 k1 = 15 0152 k2 = 20 0153 if sys.argv[1:]: 0154 # one argument: single point 0155 k1 = k2 = int(sys.argv[1]) 0156 if sys.argv[2:]: 0157 # two arguments: specify range 0158 k2 = int(sys.argv[2]) 0159 if sys.argv[3:]: 0160 # derive random seed from remaining arguments 0161 x = 1 0162 for a in sys.argv[3:]: 0163 x = 69069 * x + hash(a) 0164 random.seed(x) 0165 r = range(k1, k2+1) # include the end point 0166 tabulate(r) 0167 0168 if __name__ == '__main__': 0169 main() 0170
Generated by PyXR 0.9.4