diff options
| -rw-r--r-- | algorithms/__init__.py | 0 | ||||
| -rw-r--r-- | algorithms/algorithm.py | 25 | ||||
| -rw-r--r-- | algorithms/impl/__init__.py | 29 | ||||
| -rw-r--r-- | algorithms/impl/bubble_sort.py (renamed from bubble_sort.py) | 6 | ||||
| -rw-r--r-- | algorithms/impl/heapsort.py (renamed from heapsort.py) | 15 | ||||
| -rw-r--r-- | algorithms/impl/insertion_sort.py (renamed from insertion_sort.py) | 5 | ||||
| -rw-r--r-- | algorithms/impl/merge_sort.py (renamed from merge_sort.py) | 5 | ||||
| -rw-r--r-- | algorithms/impl/quicksort.py (renamed from quicksort.py) | 9 | ||||
| -rw-r--r-- | algorithms/impl/selection_sort.py (renamed from selection_sort.py) | 5 | ||||
| -rw-r--r-- | algorithms/registry.py | 17 | ||||
| -rw-r--r-- | plot.py | 184 | ||||
| -rw-r--r-- | test.py | 53 |
12 files changed, 227 insertions, 126 deletions
diff --git a/algorithms/__init__.py b/algorithms/__init__.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/algorithms/__init__.py diff --git a/algorithms/algorithm.py b/algorithms/algorithm.py new file mode 100644 index 0000000..322a51f --- /dev/null +++ b/algorithms/algorithm.py @@ -0,0 +1,25 @@ +# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +class Algorithm: + def __init__(self, codename, display_name, f): + self._codename = codename + self._display_name = display_name + self._f = f + + def get_codename(self): + return self._codename + + def get_display_name(self): + return self._display_name + + def get_function(self): + return self._f + + def __str__(self): + return self.get_display_name() + +class SortingAlgorithm(Algorithm): + def __init__(self, codename, display_name, f): + super().__init__(codename, display_name, f) diff --git a/algorithms/impl/__init__.py b/algorithms/impl/__init__.py new file mode 100644 index 0000000..29cd51c --- /dev/null +++ b/algorithms/impl/__init__.py @@ -0,0 +1,29 @@ +# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +_ALL_ALGORITHMS = {} + +def _refresh_algorithms(): + _ALGORITHMS_NAME = '_ALGORITHMS' + global _ALL_ALGORITHMS + _ALL_ALGORITHMS = {} + + from algorithms.algorithm import Algorithm + + from importlib import import_module + import os.path + from pkgutil import iter_modules + + for _, module_name, is_pkg in iter_modules([os.path.dirname(__file__)]): + if is_pkg: + continue + module = import_module('.' + module_name, __package__) + if hasattr(module, _ALGORITHMS_NAME): + module_algorithms = getattr(module, _ALGORITHMS_NAME) + for algorithm in module_algorithms: + assert isinstance(algorithm, Algorithm) + assert algorithm.get_codename() not in _ALL_ALGORITHMS + _ALL_ALGORITHMS[algorithm.get_codename()] = algorithm + +_refresh_algorithms() diff --git a/bubble_sort.py b/algorithms/impl/bubble_sort.py index 8309201..2abfc43 100644 --- a/bubble_sort.py +++ b/algorithms/impl/bubble_sort.py @@ -31,3 +31,9 @@ if __name__ == '__main__': xs = list(map(int, sys.argv[1:])) print(bubble_sort(list(xs))) print(bubble_sort_optimized(list(xs))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('bubble_sort', 'Bubble sort', bubble_sort), + SortingAlgorithm('bubble_sort_optimized', 'Bubble sort (optimized)', bubble_sort_optimized), + ] diff --git a/heapsort.py b/algorithms/impl/heapsort.py index 3f44e51..db3b6bd 100644 --- a/heapsort.py +++ b/algorithms/impl/heapsort.py @@ -5,11 +5,11 @@ # Disclaimer: implemented in the most literate way. def heapsort(xs): - heapify(xs) + _heapify(xs) first, last = 0, len(xs) - 1 for end in range(last, first, -1): xs[end], xs[first] = xs[first], xs[end] - siftdown(xs, first, end - 1) + _siftdown(xs, first, end - 1) return xs # In a heap stored in a zero-based array, @@ -26,13 +26,13 @@ def _get_left_child(node): def _get_right_child(node): return node * 2 + 2 -def heapify(xs): +def _heapify(xs): last = len(xs) - 1 first_parent, last_parent = 0, _get_parent(last) for parent in range(last_parent, first_parent - 1, -1): - siftdown(xs, parent, last) + _siftdown(xs, parent, last) -def siftdown(xs, start, end): +def _siftdown(xs, start, end): root = start while True: # We swap if there is at least one child @@ -52,3 +52,8 @@ def siftdown(xs, start, end): if __name__ == '__main__': import sys print(heapsort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('heapsort', 'Heapsort', heapsort), + ] diff --git a/insertion_sort.py b/algorithms/impl/insertion_sort.py index 9e0912d..f671712 100644 --- a/insertion_sort.py +++ b/algorithms/impl/insertion_sort.py @@ -13,3 +13,8 @@ def insertion_sort(xs): if __name__ == '__main__': import sys print(insertion_sort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('insertion_sort', 'Insertion sort', insertion_sort), + ] diff --git a/merge_sort.py b/algorithms/impl/merge_sort.py index 6d5403d..9fa96ec 100644 --- a/merge_sort.py +++ b/algorithms/impl/merge_sort.py @@ -27,3 +27,8 @@ def merge_sort(xs): if __name__ == '__main__': import sys print(merge_sort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('merge_sort', 'Merge sort', merge_sort), + ] diff --git a/quicksort.py b/algorithms/impl/quicksort.py index b8ecc18..32100b0 100644 --- a/quicksort.py +++ b/algorithms/impl/quicksort.py @@ -63,3 +63,12 @@ if __name__ == '__main__': print(quicksort_middle(list(xs))) print(quicksort_last(list(xs))) print(quicksort_random(list(xs))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('quicksort_first', 'Quicksort (first element as pivot)', quicksort_first), + SortingAlgorithm('quicksort_second', 'Quicksort (second element as pivot)', quicksort_second), + SortingAlgorithm('quicksort_middle', 'Quicksort (middle element as pivot)', quicksort_middle), + SortingAlgorithm('quicksort_last', 'Quicksort (last element as pivot)', quicksort_last), + SortingAlgorithm('quicksort_random', 'Quicksort (random element as pivot)', quicksort_random), + ] diff --git a/selection_sort.py b/algorithms/impl/selection_sort.py index c466bea..d48c058 100644 --- a/selection_sort.py +++ b/algorithms/impl/selection_sort.py @@ -15,3 +15,8 @@ def selection_sort(xs): if __name__ == '__main__': import sys print(selection_sort(list(map(int, sys.argv[1:])))) +else: + from algorithms.algorithm import SortingAlgorithm + _ALGORITHMS = [ + SortingAlgorithm('selection', 'Selection sort', selection_sort), + ] diff --git a/algorithms/registry.py b/algorithms/registry.py new file mode 100644 index 0000000..8f0469d --- /dev/null +++ b/algorithms/registry.py @@ -0,0 +1,17 @@ +# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +import algorithms.impl + +def refresh_algorithms(): + algorithms.impl._refresh_algorithms() + +def get_codenames(): + return algorithms.impl._ALL_ALGORITHMS.keys() + +def iter_algorithms(): + return iter(algorithms.impl._ALL_ALGORITHMS.values()) + +def get(codename): + return algorithms.impl._ALL_ALGORITHMS[codename] @@ -12,23 +12,59 @@ class InputKind(Enum): def __str__(self): return self.value -class SortingAlgorithm(Enum): - BUBBLE = 'bubble' - BUBBLE_OPTIMIZED = 'bubble_optimized' - HEAP = 'heap' - INSERTION = 'insertion' - MERGE = 'merge' - QUICK_FIRST = 'quick_first' - QUICK_SECOND = 'quick_second' - QUICK_MIDDLE = 'quick_middle' - QUICK_LAST = 'quick_last' - QUICK_RANDOM = 'quick_random' - SELECTION = 'selection' +def get_timestamp(): + return clock() - def __str__(self): - return self.value +def init_clock(): + get_timestamp() + +def gen_input(kind, n): + if kind is InputKind.SORTED: + return list(range(n)) + elif kind is InputKind.REVERSED: + return sorted(range(n), reverse=True) + elif kind is InputKind.RANDOMIZED: + from random import sample + return sample(range(n), n) + else: + raise NotImplementedError( + 'invalid initial input state \'{}\''.format(kind)) + +def measure_running_time(algorithm, kind, xs_len, repetitions): + xs = gen_input(kind, xs_len) + xss = [list(xs) for _ in range(repetitions)] + algorithm = algorithm.get_function() + gc.disable() + started_at = get_timestamp() + for i in range(repetitions): + algorithm(xss[i]) + finished_at = get_timestamp() + gc.enable() + return finished_at - started_at + +def _decorate_plot(algorithm, repetitions, kind, plt): + plt.grid() + plt.xlabel('Input length') + plt.ylabel('Running time (sec)') + plt.title('{}, {} repetition(s), {} input'.format( + algorithm.get_display_name(), repetitions, kind)) + +def plot_algorithm(algorithm, repetitions, kind, min_len, max_len, output_path=None): + import matplotlib.pyplot as plt + _decorate_plot(algorithm, repetitions, kind, plt) + xs_lengths = range(min_len, max_len + 1) + running_time = [] + for xs_len in xs_lengths: + running_time.append(measure_running_time(algorithm, kind, xs_len, repetitions)) + plt.plot(xs_lengths, running_time) + if output_path is None: + plt.show() + else: + plt.savefig(output_path) + +if __name__ == '__main__': + import algorithms.registry -def _get_context(): def natural_number(s): n = int(s) if n < 0: @@ -44,13 +80,12 @@ def _get_context(): return InputKind(s) except ValueError: raise argparse.ArgumentError() - def sorting_algorithm(s): - try: - return SortingAlgorithm(s) - except ValueError: - raise argparse.ArgumentError() + import argparse parser = argparse.ArgumentParser() + parser.add_argument('--algorithm', '-l', required=True, + choices=algorithms.registry.get_codenames(), + help='specify sorting algorithm to use') parser.add_argument('--repetitions', '-r', type=positive_number, default=1, help='set number of sorting repetitions') @@ -58,113 +93,20 @@ def _get_context(): choices=tuple(x for x in InputKind), type=input_kind, default=InputKind.RANDOMIZED, help='choose initial input state') - parser.add_argument('--algorithm', '-l', required=True, - choices=tuple(x for x in SortingAlgorithm), - type=sorting_algorithm, - help='select sorting algorithm to use') parser.add_argument('--min', '-a', type=natural_number, - required=True, dest='min_input_length', + required=True, dest='min_len', help='set min input length') parser.add_argument('--max', '-b', type=natural_number, - required=True, dest='max_input_length', + required=True, dest='max_len', help='set max input length') - parser.add_argument('--output', '-o', dest='plot_path', + parser.add_argument('--output', '-o', dest='output_path', help='set plot output path') args = parser.parse_args() - if args.max_input_length < args.min_input_length: + if args.max_len < args.min_len: parser.error('max input length cannot be less than min input length') - return args - -def get_timestamp(): - return clock() - -def init_clock(): - get_timestamp() -def gen_input(args, n): - if args.input is InputKind.SORTED: - return list(range(n)) - elif args.input is InputKind.REVERSED: - return sorted(range(n), reverse=True) - elif args.input is InputKind.RANDOMIZED: - from random import sample - return sample(range(n), n) - else: - raise NotImplementedError( - 'invalid initial input state \'{}\''.format(args.input)) - -def measure_running_time(ctx, algorithm, input_length): - xs = gen_input(ctx, input_length) - assert algorithm(list(xs)) == sorted(xs) - input_copies = [list(xs) for i in range(ctx.repetitions)] - gc.disable() - starting_time = get_timestamp() - for i in range(ctx.repetitions): - algorithm(input_copies[i]) - running_time = get_timestamp() - starting_time - gc.enable() - return running_time - -def _decorate_plot(ctx, plt): - plt.grid() - plt.xlabel('Input length') - plt.ylabel('Running time (sec)') - plt.title('{} sort, {} repetition(s), {} input'.format( - ctx.algorithm, ctx.repetitions, ctx.input)) - -def plot_algorithm(ctx, algorithm): - import matplotlib.pyplot as plt - _decorate_plot(ctx, plt) - input_length = range(ctx.min_input_length, - ctx.max_input_length + 1) - running_time = [] - for n in input_length: - running_time.append(measure_running_time(ctx, algorithm, n)) - plt.plot(input_length, running_time) - if ctx.plot_path is not None: - plt.savefig(ctx.plot_path) - else: - plt.show() - -def plot(ctx): - if ctx.algorithm is SortingAlgorithm.BUBBLE: - from bubble_sort import bubble_sort - plot_algorithm(ctx, bubble_sort) - elif ctx.algorithm is SortingAlgorithm.BUBBLE_OPTIMIZED: - from bubble_sort import bubble_sort_optimized - plot_algorithm(ctx, bubble_sort_optimized) - elif ctx.algorithm is SortingAlgorithm.HEAP: - from heapsort import heapsort - plot_algorithm(ctx, heapsort) - elif ctx.algorithm is SortingAlgorithm.INSERTION: - from insertion_sort import insertion_sort - plot_algorithm(ctx, insertion_sort) - elif ctx.algorithm is SortingAlgorithm.MERGE: - from merge_sort import merge_sort - plot_algorithm(ctx, merge_sort) - elif ctx.algorithm is SortingAlgorithm.QUICK_FIRST: - from quicksort import quicksort_first - plot_algorithm(ctx, quicksort_first) - elif ctx.algorithm is SortingAlgorithm.QUICK_SECOND: - from quicksort import quicksort_second - plot_algorithm(ctx, quicksort_second) - elif ctx.algorithm is SortingAlgorithm.QUICK_MIDDLE: - from quicksort import quicksort_middle - plot_algorithm(ctx, quicksort_middle) - elif ctx.algorithm is SortingAlgorithm.QUICK_LAST: - from quicksort import quicksort_last - plot_algorithm(ctx, quicksort_last) - elif ctx.algorithm is SortingAlgorithm.QUICK_RANDOM: - from quicksort import quicksort_random - plot_algorithm(ctx, quicksort_random) - elif ctx.algorithm is SortingAlgorithm.SELECTION: - from selection_sort import selection_sort - plot_algorithm(ctx, selection_sort) - else: - raise NotImplementedError( - 'invalid sorting algorithm \'{}\''.format(ctx.algorithm)) - -if __name__ == '__main__': - ctx = _get_context() init_clock() - plot(ctx) + plot_algorithm(algorithms.registry.get(args.algorithm), + args.repetitions, args.input, + args.min_len, args.max_len, + args.output_path) @@ -0,0 +1,53 @@ +# Copyright 2016 Egor Tensin <Egor.Tensin@gmail.com> +# This file is licensed under the terms of the MIT License. +# See LICENSE.txt for details. + +from enum import Enum + +class InputKind(Enum): + SORTED, RANDOMIZED, REVERSED = 'sorted', 'randomized', 'reversed' + + def __str__(self): + return self.value + +def gen_input(kind, n): + if kind is InputKind.SORTED: + return list(range(n)) + elif kind is InputKind.REVERSED: + return sorted(range(n), reverse=True) + elif kind is InputKind.RANDOMIZED: + from random import sample + return sample(range(n), n) + else: + raise NotImplementedError( + 'invalid initial input state \'{}\''.format(kind)) + +if __name__ == '__main__': + import algorithms.registry + + def natural_number(s): + n = int(s) + if n < 0: + raise argparse.ArgumentTypeError('cannot be negative') + return n + def input_kind(s): + try: + return InputKind(s) + except ValueError: + raise argparse.ArgumentError() + + import argparse + parser = argparse.ArgumentParser() + parser.add_argument('--algorithm', '-l', required=True, + choices=algorithms.registry.get_codenames(), + help='specify algorithm codename') + parser.add_argument('--input', '-i', + choices=tuple(x for x in InputKind), + type=input_kind, default=InputKind.RANDOMIZED, + help='set initial input state') + parser.add_argument('--length', '-n', + type=natural_number, default=100, + help='set input length') + args = parser.parse_args() + xs = gen_input(args.input, args.length) + print(algorithms.registry.get(args.algorithm).get_function()(xs)) |