#!/usr/local/cpython-3.3/bin/python """Run some performance tests on a variety of sorting algorithms.""" # import os import sys import time import random # import functools import funnelsort_py as funnelsort # import funnelsort as funnelsort import quicksort_py as quicksort # import quicksort as quicksort import insertionsort_py as insertionsort # import insertionsort as insertionsort import binarysort_py as binarysort # import binarysort as binarysort import bubblesort_py as bubblesort # import bubblesort as bubblesort import shellsort_py as shellsort # import shellsort as shellsort import mergesort_py as mergesort # import mergesort as mergesort import timsort_reimp_py as timsort_reimp # import timsort_reimp as timsort_reimp import radixsort_py as radixsort # import radixsort as radixsort sys.setrecursionlimit(100000) ORIGINAL = None def comparison_function(left, right): """Compare left and right.""" if left < right: return -1 elif left > right: return 1 else: return 0 class Test(object): # pylint: disable=R0903 # R0903: We're a container; we don't need a lot of public methods """Hold information about an individual test.""" def __init__(self, kind, generate, proportion): """Initialize.""" self.kind = kind self.generate = generate self.proportion = proportion class Slow_comparisons(object): # pylint: disable=R0903 # R0903: We don't need a lot of public methods """Perform a comparison, and make it artificially expensive by sleeping a tiny bit on each one.""" def __init__(self, value): """Initialize.""" self.value = value def __cmp__(self, other): """Compare the Python 2.x way.""" time.sleep(0.0000003) # print type(self), type(other) # sys.stdout.flush() return comparison_function(self.value, other.value) def slow_generate(count): """Produce a list of objects with artificially expensive comparisons.""" return [Slow_comparisons(x) for x in range(count)] def brief_generate(count): """Return a brief list with numbers 0..count-1.""" return list(range(count)) def append(filename, size, duration): """Append a statistic to a file.""" with open(filename, 'a') as file_: file_.write('%d %f\n' % (size, duration)) def shuffle(lst): """Rearrange a (possibly sorted) list into random order.""" # This is how I was taught to do it in school, but https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle # len_lst = len(lst) # for index in range(len_lst): # random_index = int(random.random() * len_lst) # lst[index], lst[random_index] = lst[random_index], lst[index] random.shuffle(lst) def is_sorted(test_list, original_list): """Return True if a list is sorted, by comparing it to the original list.""" if test_list == original_list: return True else: return False def radixsort_cython_fn(list_): """Radix sort consistency wrapper.""" radixsort.radix_sort(list_) def timsort_cext_fn(list_): """Build-in timsort consistency wrapper.""" list_.sort() def timsort_cython_fn(list_): """Timsort reimplementation consistency wrapper.""" timsort_reimp.timsort(list_) def mergesort_cython_fn(list_): """Mergesort consistency wrapper.""" mergesort.mergesort(list_) def funnelsort_cython_fn(list_): """Funnelsort consistency wrapper.""" funnelsort.funnelsort(list_) # def stable_quicksort_cython_fn(list_): # """Stable quicksort consistency wrapper.""" # quicksort.quicksort(list_, stable=True) def quicksort_cython_fn(list_): """Unstable quicksort consistency wrapper.""" quicksort.quicksort(list_) def shellsort_cython_fn(list_): """Shellsort consistency wrapper.""" shellsort.shellsort(list_) def insertionsort_cython_fn(list_): """Sort with Insertion Sort - consistency wrapper.""" insertionsort.insertionsort(list_, 0, len(list_) - 1) def binarysort_cython_fn(list_): """Sort with Binary Sort - consistency wrapper.""" binarysort.binarysort(list_, 0, len(list_) - 1) def bubblesort_cython_fn(list_): """Bubblesort consistency wrapper.""" bubblesort.bubblesort(list_, 0, len(list_) - 1) def cheat_o_of_n_fn(list_): """Just do something linear (O(n)) for the sake of comparison.""" list_[:] = ORIGINAL for dummy in ORIGINAL: dummy *= 2 def main(): # pylint: disable=W0603 # W0603: We kinda want a global here, so we don't have to change a bunch of function signatures """Compare sorts via a graph - or rather, produce raw data for graphing.""" global ORIGINAL tests = [ \ # Test('slow', slow_generate, 1), \ Test('brief', brief_generate, 2), \ ] for test in tests: maximum_exponent = 26 for exponent in range(maximum_exponent): size = 2**exponent # ('stable_quicksort_cython', stable_quicksort_cython_fn, maximum_exponent), \ tuples = [ ('bubblesort', bubblesort_cython_fn, maximum_exponent * 9 // 16), ('insertionsort', insertionsort_cython_fn, maximum_exponent * 10 // 16), ('binarysort', binarysort_cython_fn, maximum_exponent * 10 // 16), ('shellsort', shellsort_cython_fn, maximum_exponent), ('quicksort', quicksort_cython_fn, maximum_exponent), ('funnelsort', funnelsort_cython_fn, maximum_exponent), ('mergesort', mergesort_cython_fn, maximum_exponent), ('timsort_cext', timsort_cext_fn, maximum_exponent), ('timsort', timsort_cython_fn, maximum_exponent), ('radixsort', radixsort_cython_fn, maximum_exponent), ('cheat_O(n)', cheat_o_of_n_fn, maximum_exponent), ] for algorithm_description, algorithm_code, max_exponent in tuples: algorithm_description = '%s_%s' % (test.kind, algorithm_description) if exponent > max_exponent: continue sys.stdout.write('%30s 2**%0d ' % (algorithm_description, exponent)) sys.stdout.write('ge') sys.stdout.flush() ints = test.generate(size) # for x in range(size): # ints.append(Slow_comparisons(x)) # print 'size is,', size, 'ints is', ints sys.stdout.write('t ') sys.stdout.write('shuff') sys.stdout.flush() shuffle(ints) sys.stdout.write('le ') sys.stdout.flush() sys.stdout.write('so') sys.stdout.flush() ORIGINAL = test.generate(size) time0 = time.time() algorithm_code(ints) time1 = time.time() diff_time = time1 - time0 if is_sorted(ints, test.generate(size)): print('rt %s' % diff_time) else: print('rt %s failed' % diff_time) print('%s %s' % (ints, test.generate(size))) sys.exit(1) append('%s.dat' % algorithm_description, size, diff_time) main()