sort performance test see main for command line syntax see tabulate for output format 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 jointd rr06d n try fp openfn rb except oserror r random random result r for i in rangen try try fp openfn wb marshal dumpresult fp fp close fp none finally if fp try os unlinkfn except oserror pass except oserror as msg printcan t write fn msg else result marshal loadfp fp close shuffle it a bit for i in range10 i random randrangen temp result i del result i temp reverse result extendtemp del temp assert lenresult n return result def flush sys stdout flush def doitl t0 time perfcounter l sort t1 time perfcounter print6 2f t1t0 end flush def tabulater rtabulate sort speed for lists of various sizes the sizes are 2i for i in r the argument a list the output displays i 2i and the time to sort arrays of 2i floating point numbers with the following properties sort random data sort descending data sort ascending data 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 many duplicates sort all equal sort worst case scenario do 3 random exchanges replace the last 10 with random floats replace 1 of the elements at random arrange for lots of duplicates force the elements to be distinct objects else timings can be artificially low 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 force to float so that the timings are comparable this is significantly faster if we leave them 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 two arguments specify range derive random seed from remaining arguments 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 shuffle it a bit 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 sort random data sort descending data sort ascending data 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 many duplicates sort all equal sort worst case scenario sort sort sort do 3 random exchanges 3sort replace the last 10 with random floats sort replace 1 of the elements at random sort arrange for lots of duplicates force the elements to be distinct objects else timings can be artificially low sort all equal again force the elements to be distinct objects sort 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 force to float so that the timings are comparable this is significantly faster if we leave them as ints sort 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 two arguments specify range derive random seed from remaining arguments include the end point
import sys
import time
import random
import marshal
import tempfile
import os

td = tempfile.gettempdir()

def randfloats(n):
    
    
    
    
    fn = os.path.join(td, "rr%06d" % n)
    try:
        fp = open(fn, "rb")
    except OSError:
        r = random.random
        result = [r() for i in range(n)]
        try:
            try:
                fp = open(fn, "wb")
                marshal.dump(result, fp)
                fp.close()
                fp = None
            finally:
                if fp:
                    try:
                        os.unlink(fn)
                    except OSError:
                        pass
        except OSError as msg:
            print("can't write", fn, ":", msg)
    else:
        result = marshal.load(fp)
        fp.close()
        
        for i in range(10):
            i = random.randrange(n)
            temp = result[:i]
            del result[:i]
            temp.reverse()
            result.extend(temp)
            del temp
    assert len(result) == n
    return result

def flush():
    sys.stdout.flush()

def doit(L):
    t0 = time.perf_counter()
    L.sort()
    t1 = time.perf_counter()
    print("%6.2f" % (t1-t0), end=' ')
    flush()

def tabulate(r):
    r
    cases = tuple([ch + "sort" for ch in r"*\/3+%~=!"])
    fmt = ("%2s %7s" + " %6s"*len(cases))
    print(fmt % (("i", "2**i") + cases))
    for i in r:
        n = 1 << i
        L = randfloats(n)
        print("%2d %7d" % (i, n), end=' ')
        flush()
        doit(L) 
        L.reverse()
        doit(L) 
        doit(L) 

        
        for dummy in range(3):
            i1 = random.randrange(n)
            i2 = random.randrange(n)
            L[i1], L[i2] = L[i2], L[i1]
        doit(L) 

        
        if n >= 10:
            L[-10:] = [random.random() for dummy in range(10)]
        doit(L) 

        
        for dummy in range(n // 100):
            L[random.randrange(n)] = random.random()
        doit(L) 

        
        if n > 4:
            del L[4:]
            L = L * (n // 4)
            
            
            L = list(map(lambda x: --x, L))
        doit(L) 
        del L

        
        L = list(map(abs, [-0.5] * n))
        doit(L) 
        del L

        
        
        
        half = n // 2
        L = list(range(half - 1, -1, -1))
        L.extend(range(half))
        
        
        L = list(map(float, L))
        doit(L) 
        print()

def main():
    
    
    k1 = 15
    k2 = 20
    if sys.argv[1:]:
        
        k1 = k2 = int(sys.argv[1])
        if sys.argv[2:]:
            
            k2 = int(sys.argv[2])
            if sys.argv[3:]:
                
                x = 1
                for a in sys.argv[3:]:
                    x = 69069 * x + hash(a)
                random.seed(x)
    r = range(k1, k2+1)                 
    tabulate(r)

if __name__ == '__main__':
    main()