diff options
| -rw-r--r-- | algorithms/algorithm.py | 5 | ||||
| -rw-r--r-- | algorithms/impl/__init__.py | 2 | ||||
| -rw-r--r-- | algorithms/impl/bubble_sort.py | 6 | ||||
| -rw-r--r-- | algorithms/impl/heapsort.py | 11 | ||||
| -rw-r--r-- | algorithms/impl/insertion_sort.py | 5 | ||||
| -rw-r--r-- | algorithms/impl/median.py | 6 | ||||
| -rw-r--r-- | algorithms/impl/merge_sort.py | 6 | ||||
| -rw-r--r-- | algorithms/impl/quicksort.py | 17 | ||||
| -rw-r--r-- | algorithms/impl/selection_sort.py | 5 | ||||
| -rw-r--r-- | algorithms/input_kind.py | 11 | ||||
| -rw-r--r-- | algorithms/params.py | 14 | ||||
| -rw-r--r-- | algorithms/plotter.py | 1 | ||||
| -rw-r--r-- | algorithms/registry.py | 3 | ||||
| -rw-r--r-- | algorithms/timer.py | 2 | ||||
| -rw-r--r-- | plot.py | 12 |
15 files changed, 92 insertions, 14 deletions
diff --git a/algorithms/algorithm.py b/algorithms/algorithm.py index 74817de..66f8724 100644 --- a/algorithms/algorithm.py +++ b/algorithms/algorithm.py @@ -5,6 +5,7 @@ from . import input_kind + class Algorithm: def __init__(self, codename, display_name, f): self.codename = codename @@ -16,9 +17,7 @@ class Algorithm: #raise NotImplementedError('input generation is not defined for a generic algorithm') return input_kind.gen_input_for_sorting(n, case) -class SortingAlgorithm(Algorithm): - def __init__(self, codename, display_name, f): - super().__init__(codename, display_name, f) +class SortingAlgorithm(Algorithm): def gen_input(self, n, case=input_kind.InputKind.AVERAGE): return input_kind.gen_input_for_sorting(n, case) diff --git a/algorithms/impl/__init__.py b/algorithms/impl/__init__.py index 579b091..84bd702 100644 --- a/algorithms/impl/__init__.py +++ b/algorithms/impl/__init__.py @@ -9,8 +9,10 @@ from pkgutil import iter_modules from .. import algorithm + _ALGORITHMS_NAME = '_ALGORITHMS' + def refresh_algorithms(): all_algorithms = {} diff --git a/algorithms/impl/bubble_sort.py b/algorithms/impl/bubble_sort.py index 95fb661..0ea66bb 100644 --- a/algorithms/impl/bubble_sort.py +++ b/algorithms/impl/bubble_sort.py @@ -7,6 +7,7 @@ import sys from ..algorithm import SortingAlgorithm + def bubble_sort(xs): while True: swapped = False @@ -18,6 +19,7 @@ def bubble_sort(xs): break return xs + def bubble_sort_optimized(xs): n = len(xs) while True: @@ -31,20 +33,24 @@ def bubble_sort_optimized(xs): break return xs + _ALGORITHMS = [ SortingAlgorithm('bubble_sort', 'Bubble sort', bubble_sort), SortingAlgorithm('bubble_sort_optimized', 'Bubble sort (optimized)', bubble_sort_optimized), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(bubble_sort(list(xs))) print(bubble_sort_optimized(list(xs))) + if __name__ == '__main__': main() diff --git a/algorithms/impl/heapsort.py b/algorithms/impl/heapsort.py index bf9f464..81bea20 100644 --- a/algorithms/impl/heapsort.py +++ b/algorithms/impl/heapsort.py @@ -9,6 +9,7 @@ from ..algorithm import SortingAlgorithm # Disclaimer: implemented in the most literate way. + def heapsort(xs): _heapify(xs) first, last = 0, len(xs) - 1 @@ -17,26 +18,32 @@ def heapsort(xs): _siftdown(xs, first, end - 1) return xs + # In a heap stored in a zero-based array, # left_child = node * 2 + 1 # right_child = node * 2 + 2 # parent = (node - 1) // 2 + def _get_parent(node): return (node - 1) // 2 + def _get_left_child(node): return node * 2 + 1 + def _get_right_child(node): return node * 2 + 2 + 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) + def _siftdown(xs, start, end): root = start while True: @@ -54,18 +61,22 @@ def _siftdown(xs, start, end): else: break + _ALGORITHMS = [ SortingAlgorithm('heapsort', 'Heapsort', heapsort), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(heapsort(list(xs))) + if __name__ == '__main__': main() diff --git a/algorithms/impl/insertion_sort.py b/algorithms/impl/insertion_sort.py index 1abbf84..13f16a0 100644 --- a/algorithms/impl/insertion_sort.py +++ b/algorithms/impl/insertion_sort.py @@ -7,6 +7,7 @@ import sys from ..algorithm import SortingAlgorithm + def insertion_sort(xs): for i in range(1, len(xs)): j = i @@ -15,18 +16,22 @@ def insertion_sort(xs): j -= 1 return xs + _ALGORITHMS = [ SortingAlgorithm('insertion_sort', 'Insertion sort', insertion_sort), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(insertion_sort(list(xs))) + if __name__ == '__main__': main() diff --git a/algorithms/impl/median.py b/algorithms/impl/median.py index b48e511..a754cdb 100644 --- a/algorithms/impl/median.py +++ b/algorithms/impl/median.py @@ -9,6 +9,7 @@ import sys from ..algorithm import Algorithm from .quicksort import quicksort_random + def calc_median_heaps(xs): cur_median = 0.0 min_heap, max_heap = [], [] @@ -33,6 +34,7 @@ def calc_median_heaps(xs): cur_median = min_heap[0] return cur_median + def calc_median_sorting(xs): if not xs: return 0.0 @@ -42,20 +44,24 @@ def calc_median_sorting(xs): else: return xs[len(xs) // 2 - 1] / 2 + xs[len(xs) // 2] / 2 + _ALGORITHMS = [ Algorithm('median_sorting', 'Median value (using explicit sorting)', calc_median_sorting), Algorithm('median_heaps', 'Median value (using heaps)', calc_median_heaps), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(calc_median_sorting(list(xs))) print(calc_median_heaps(list(xs))) + if __name__ == '__main__': main() diff --git a/algorithms/impl/merge_sort.py b/algorithms/impl/merge_sort.py index 2b96d21..fecdf78 100644 --- a/algorithms/impl/merge_sort.py +++ b/algorithms/impl/merge_sort.py @@ -7,6 +7,7 @@ import sys from ..algorithm import SortingAlgorithm + def merge(left, right): result = [] l, r = 0, 0 @@ -23,24 +24,29 @@ def merge(left, right): result.extend(right[r:]) return result + def merge_sort(xs): if len(xs) < 2: return xs mid = len(xs) // 2 return merge(merge_sort(xs[:mid]), merge_sort(xs[mid:])) + _ALGORITHMS = [ SortingAlgorithm('merge_sort', 'Merge sort', merge_sort), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(merge_sort(list(xs))) + if __name__ == '__main__': main() diff --git a/algorithms/impl/quicksort.py b/algorithms/impl/quicksort.py index 1e835c4..dd0c92b 100644 --- a/algorithms/impl/quicksort.py +++ b/algorithms/impl/quicksort.py @@ -8,8 +8,10 @@ import sys from ..algorithm import SortingAlgorithm + seed() + def _partition(xs, beg, end, select_pivot): pivot = select_pivot(xs, beg, end) xs[pivot], xs[end] = xs[end], xs[pivot] @@ -20,47 +22,59 @@ def _partition(xs, beg, end, select_pivot): xs[beg], xs[end] = xs[end], xs[beg] return beg + def _quicksort(xs, beg, end, select_pivot): if beg < end: pivot = _partition(xs, beg, end, select_pivot) _quicksort(xs, beg, pivot - 1, select_pivot) _quicksort(xs, pivot + 1, end, select_pivot) + def _select_first(xs, beg, end): return beg + def _select_second(xs, beg, end): return beg + 1 + def _select_middle(xs, beg, end): return (beg + end) // 2 + def _select_last(xs, beg, end): return end + def _select_random(xs, beg, end): return randrange(beg, end + 1) + def quicksort_first(xs): _quicksort(xs, 0, len(xs) - 1, _select_first) return xs + def quicksort_second(xs): _quicksort(xs, 0, len(xs) - 1, _select_second) return xs + def quicksort_middle(xs): _quicksort(xs, 0, len(xs) - 1, _select_middle) return xs + def quicksort_last(xs): _quicksort(xs, 0, len(xs) - 1, _select_last) return xs + def quicksort_random(xs): _quicksort(xs, 0, len(xs) - 1, _select_random) return xs + _ALGORITHMS = [ SortingAlgorithm('quicksort_first', 'Quicksort (first element as pivot)', quicksort_first), SortingAlgorithm('quicksort_second', 'Quicksort (second element as pivot)', quicksort_second), @@ -69,11 +83,13 @@ _ALGORITHMS = [ SortingAlgorithm('quicksort_random', 'Quicksort (random element as pivot)', quicksort_random), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(quicksort_first(list(xs))) @@ -82,5 +98,6 @@ def main(args=None): print(quicksort_last(list(xs))) print(quicksort_random(list(xs))) + if __name__ == '__main__': main() diff --git a/algorithms/impl/selection_sort.py b/algorithms/impl/selection_sort.py index ad4a420..e9a5a09 100644 --- a/algorithms/impl/selection_sort.py +++ b/algorithms/impl/selection_sort.py @@ -7,6 +7,7 @@ import sys from ..algorithm import SortingAlgorithm + def selection_sort(xs): for i in range(len(xs) - 1): min_i = i @@ -17,18 +18,22 @@ def selection_sort(xs): xs[i], xs[min_i] = xs[min_i], xs[i] return xs + _ALGORITHMS = [ SortingAlgorithm('selection_sort', 'Selection sort', selection_sort), ] + def _parse_args(args=None): if args is None: args = sys.argv[1:] return list(map(int, args)) + def main(args=None): xs = _parse_args(args) print(selection_sort(list(xs))) + if __name__ == '__main__': main() diff --git a/algorithms/input_kind.py b/algorithms/input_kind.py index 998f1d6..08e1c9e 100644 --- a/algorithms/input_kind.py +++ b/algorithms/input_kind.py @@ -7,25 +7,28 @@ from array import array from enum import Enum from random import seed, sample + seed() + class InputKind(Enum): BEST, AVERAGE, WORST = 'best', 'average', 'worst' def __str__(self): return self.value + def _gen_input_from(xs): return array('l', xs) + def gen_input_for_sorting(n, case=InputKind.AVERAGE): if n < 0: raise ValueError('input length cannot be less than zero') if case is InputKind.BEST: return _gen_input_from(range(n)) - elif case is InputKind.AVERAGE: + if case is InputKind.AVERAGE: return _gen_input_from(sample(range(n), n)) - elif case is InputKind.WORST: + if case is InputKind.WORST: return _gen_input_from(range(n - 1, -1, -1)) - else: - raise NotImplementedError('invalid input kind: ' + str(case)) + raise NotImplementedError('invalid input kind: ' + str(case)) diff --git a/algorithms/params.py b/algorithms/params.py index edd1361..787cfd1 100644 --- a/algorithms/params.py +++ b/algorithms/params.py @@ -11,6 +11,7 @@ from .plotter import PlotBuilder from . import registry from .timer import Timer + class TimeUnits(Enum): SECONDS = 'seconds' MILLISECONDS = 'milliseconds' @@ -19,16 +20,16 @@ class TimeUnits(Enum): def get_factor(self): if self is TimeUnits.SECONDS: return 1. - elif self is TimeUnits.MILLISECONDS: + if self is TimeUnits.MILLISECONDS: return 1000. - elif self is TimeUnits.MICROSECONDS: + if self is TimeUnits.MICROSECONDS: return 1000000. - else: - raise NotImplementedError('invalid time units: ' + str(self)) + raise NotImplementedError('invalid time units: ' + str(self)) def __str__(self): return self.value + class AlgorithmParameters: def __init__(self, algorithm, min_len, max_len, input_kind=InputKind.AVERAGE, iterations=1): @@ -121,10 +122,9 @@ class AlgorithmParameters: max_y = max(ys) if max_y > 0.1: return TimeUnits.SECONDS - elif max_y > 0.0001: + if max_y > 0.0001: return TimeUnits.MILLISECONDS - else: - return TimeUnits.MICROSECONDS + return TimeUnits.MICROSECONDS def plot_running_time(self, output_path=None): xs, ys = self.measure_running_time() diff --git a/algorithms/plotter.py b/algorithms/plotter.py index 8086850..47d2929 100644 --- a/algorithms/plotter.py +++ b/algorithms/plotter.py @@ -5,6 +5,7 @@ import matplotlib.pyplot as plt + class PlotBuilder: @staticmethod def set_xlabel(s): diff --git a/algorithms/registry.py b/algorithms/registry.py index 787fe49..3bc6495 100644 --- a/algorithms/registry.py +++ b/algorithms/registry.py @@ -5,10 +5,13 @@ from . import impl + _ALL_ALGORITHMS = impl.refresh_algorithms() + def get_codenames(): return _ALL_ALGORITHMS.keys() + def get(codename): return _ALL_ALGORITHMS[codename] diff --git a/algorithms/timer.py b/algorithms/timer.py index bd5d044..c567a3f 100644 --- a/algorithms/timer.py +++ b/algorithms/timer.py @@ -6,9 +6,11 @@ import gc import time + def get_timestamp(): return time.perf_counter() + class Timer: def __init__(self, dest, iterations=1): self._dest = dest @@ -10,11 +10,13 @@ from algorithms.input_kind import InputKind from algorithms.params import AlgorithmParameters import algorithms.registry as registry + _DEFAULT_ITERATIONS = 100 _DEFAULT_INPUT_KIND = InputKind.AVERAGE _DEFAULT_MIN_LENGTH = 0 _DEFAULT_MAX_LENGTH = 200 + def plot_algorithm(algorithm, input_kind=_DEFAULT_INPUT_KIND, min_len=_DEFAULT_MIN_LENGTH, max_len=_DEFAULT_MAX_LENGTH, @@ -29,6 +31,7 @@ def plot_algorithm(algorithm, input_kind=_DEFAULT_INPUT_KIND, iterations=iterations) params.plot_running_time(output_path) + def _parse_non_negative_integer(s): try: n = int(s) @@ -38,6 +41,7 @@ def _parse_non_negative_integer(s): raise argparse.ArgumentTypeError('must be a non-negative integer') return n + def _parse_positive_integer(s): try: n = int(s) @@ -47,28 +51,34 @@ def _parse_positive_integer(s): raise argparse.ArgumentTypeError('must be a positive integer') return n + def _parse_input_kind(s): try: return InputKind(s) except ValueError: raise argparse.ArgumentTypeError('invalid input kind: ' + str(s)) + def _format_algorithm(codename): return '* {}: {}'.format(codename, registry.get(codename).display_name) + def _format_available_algorithms(): descr = 'available algorithms (in the CODENAME: DISPLAY_NAME format):\n' return descr + '\n'.join(map( _format_algorithm, sorted(registry.get_codenames()))) + def _format_description(): return _format_available_algorithms() + def _create_argument_parser(): return argparse.ArgumentParser( description=_format_description(), formatter_class=argparse.RawDescriptionHelpFormatter) + def _parse_args(args=None): if args is None: args = sys.argv[1:] @@ -98,8 +108,10 @@ def _parse_args(args=None): return parser.parse_args(args) + def main(args=None): plot_algorithm(**vars(_parse_args(args))) + if __name__ == '__main__': main() |