#!/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()