Last active
October 13, 2015 19:47
-
-
Save NoahTheDuke/44db24fb62f750f70d7e to your computer and use it in GitHub Desktop.
Testing the speed of various implementations of Strand Sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import timeit | |
from random import shuffle, randrange | |
from statistics import mean | |
from functools import partial | |
from collections import deque | |
def merge_original_1(left, right): | |
i = 0 | |
j = 0 | |
merged_list = [] | |
while i < len(left) and j < len(right): | |
if left[i] > right[j]: | |
merged_list.append(right[j]) | |
j += 1 | |
else: | |
merged_list.append(left[i]) | |
i += 1 | |
merged_list += left[i:] | |
merged_list += right[j:] | |
return merged_list | |
def strand_sort_original_3(unsorted): | |
if len(unsorted) < 2: | |
return unsorted | |
result = [] | |
while unsorted: | |
sublist = [unsorted.pop()] | |
leftovers = [] | |
last = sublist[-1] | |
for item in unsorted: | |
if item >= last: | |
sublist.append(item) | |
last = item | |
else: | |
leftovers.append(item) | |
result = merge_original_1(result, sublist) | |
unsorted = leftovers | |
return result | |
def strand_sort_original_4(unsorted): | |
if len(unsorted) < 2: | |
return unsorted | |
result = [] | |
while unsorted: | |
sublist = [unsorted.pop(0)] | |
leftovers = [] | |
last = sublist[0] | |
sublist_append = sublist.append | |
leftovers_append = leftovers.append | |
for item in unsorted: | |
if item >= last: | |
sublist_append(item) | |
last = item | |
else: | |
leftovers_append(item) | |
result = merge_original_1(result, sublist) | |
unsorted = leftovers | |
return result | |
def strand_sort_gengisteve_2(unsorted): | |
if len(unsorted) < 2: | |
return unsorted | |
result = [] | |
while unsorted: | |
sublist = [unsorted.pop()] | |
last = sublist[0] | |
sub_append = sublist.append | |
leftovers = deque() | |
left_append = leftovers.append | |
for item in unsorted: | |
if item >= last: | |
sub_append(item) | |
last = item | |
else: | |
left_append(item) | |
result = merge_gengisteve(result, sublist) | |
unsorted = leftovers | |
return result | |
def merge_gengisteve(left, right): | |
merged_list = [] | |
merged_list_append = merged_list.append | |
it_left = iter(left) | |
it_right = iter(right) | |
left = next(it_left, None) | |
right = next(it_right, None) | |
while left is not None and right is not None: | |
if left > right: | |
merged_list_append(right) | |
right = next(it_right, None) | |
else: | |
merged_list_append(left) | |
left = next(it_left, None) | |
if left: | |
merged_list_append(left) | |
merged_list.extend(i for i in it_left) | |
else: | |
merged_list_append(right) | |
merged_list.extend(i for i in it_right) | |
return merged_list | |
def strand_sort_deque(unsorted): | |
if len(unsorted) < 2: | |
return unsorted | |
result = [] | |
while unsorted: | |
sublist = [unsorted.popleft()] | |
last = sublist[0] | |
sub_append = sublist.append | |
leftovers = deque() | |
left_append = leftovers.append | |
for item in unsorted: | |
if item >= last: | |
sub_append(item) | |
last = item | |
else: | |
left_append(item) | |
result = merge_deque(result, sublist) | |
unsorted = leftovers | |
return result | |
def merge_deque(left, right): | |
merged_list = [] | |
merged_list_append = merged_list.append | |
it_left = iter(left) | |
it_right = iter(right) | |
left = next(it_left, None) | |
right = next(it_right, None) | |
while left is not None and right is not None: | |
if left > right: | |
merged_list_append(right) | |
right = next(it_right, None) | |
else: | |
merged_list_append(left) | |
left = next(it_left, None) | |
if left: | |
merged_list_append(left) | |
merged_list.extend(i for i in it_left) | |
else: | |
merged_list_append(right) | |
merged_list.extend(i for i in it_right) | |
return merged_list | |
temp = [ | |
[randrange(0, 1000) for _ in range(10)], | |
[randrange(0, 1000) for _ in range(100)], | |
[randrange(0, 1000) for _ in range(1000)], | |
[randrange(0, 1000) for _ in range(10000)], | |
[randrange(0, 1000) for _ in range(100000)], | |
] | |
t = temp[4][:] | |
temp2 = [ | |
sorted(t)[:], | |
[x for x in sorted(t)[::-1]][:], | |
t[:], | |
] | |
def main(): | |
reps = 2 | |
num = 2 | |
tests = [ | |
'strand_sort_original_3', | |
'strand_sort_original_4', | |
'strand_sort_deque', | |
'strand_sort_gengisteve_2', | |
] | |
ls_words = { | |
0: "already sorted", | |
1: "reverse sorted", | |
2: "random order" | |
} | |
for l in range(len(temp2)): | |
print("\n On a list of {} {} items:\tMean\t\t\tMin\t\t\tMax".format(len(temp2[l]), ls_words[l])) | |
for name in tests: | |
if name == 'strand_sort_deque': | |
test = '{}(deque(temp2[{}][:]))'.format(name, l) | |
else: | |
test = '{}(temp2[{}][:])'.format(name, l) | |
setup = 'from __main__ import {}, temp2; from collections import deque'.format(name) | |
t = timeit.Timer(test, setup) | |
runs = t.repeat(reps, num) | |
print(' {}: {}{}\t{}\t{}'.format( | |
name, | |
'\t\t' if name == 'strand_sort_deque' else '\t', | |
mean(runs), | |
min(runs), | |
max(runs), | |
)) | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment