diff options
| -rw-r--r-- | .github/workflows/ci.yml | 17 | ||||
| -rw-r--r-- | algorithms/algorithm.py | 2 | ||||
| -rw-r--r-- | algorithms/impl/__init__.py | 1 | ||||
| -rw-r--r-- | algorithms/impl/bubble_sort.py | 4 | ||||
| -rw-r--r-- | algorithms/impl/median.py | 4 | ||||
| -rw-r--r-- | algorithms/impl/quicksort.py | 21 | ||||
| -rw-r--r-- | algorithms/input_kind.py | 1 | ||||
| -rw-r--r-- | algorithms/params.py | 14 | ||||
| -rw-r--r-- | algorithms/registry.py | 1 | ||||
| -rwxr-xr-x | algorithms/scripts/plot.py | 91 | ||||
| -rwxr-xr-x | algorithms/scripts/test.py | 45 |
11 files changed, 132 insertions, 69 deletions
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml index f93fd1d..018d321 100644 --- a/.github/workflows/ci.yml +++ b/.github/workflows/ci.yml @@ -5,6 +5,23 @@ on: workflow_dispatch: jobs: + lint: + runs-on: ubuntu-latest + name: Linting + steps: + - name: Checkout + uses: actions/checkout@v6 + - name: Set up Python + uses: actions/setup-python@v6 + with: + python-version: '3.x' + - name: Run black + uses: psf/black@stable + with: + # > Please note that the --check flag is required so that the + # > workflow fails if Black finds files that need to be formatted. + options: --check --verbose --skip-string-normalization + test: strategy: matrix: diff --git a/algorithms/algorithm.py b/algorithms/algorithm.py index 66f8724..55d4929 100644 --- a/algorithms/algorithm.py +++ b/algorithms/algorithm.py @@ -14,7 +14,7 @@ class Algorithm: @staticmethod def gen_input(n, case=input_kind.InputKind.AVERAGE): - #raise NotImplementedError('input generation is not defined for a generic algorithm') + # raise NotImplementedError('input generation is not defined for a generic algorithm') return input_kind.gen_input_for_sorting(n, case) diff --git a/algorithms/impl/__init__.py b/algorithms/impl/__init__.py index 84bd702..f2d5aaf 100644 --- a/algorithms/impl/__init__.py +++ b/algorithms/impl/__init__.py @@ -9,7 +9,6 @@ from pkgutil import iter_modules from .. import algorithm - _ALGORITHMS_NAME = '_ALGORITHMS' diff --git a/algorithms/impl/bubble_sort.py b/algorithms/impl/bubble_sort.py index 0ea66bb..14f5386 100644 --- a/algorithms/impl/bubble_sort.py +++ b/algorithms/impl/bubble_sort.py @@ -36,7 +36,9 @@ def bubble_sort_optimized(xs): _ALGORITHMS = [ SortingAlgorithm('bubble_sort', 'Bubble sort', bubble_sort), - SortingAlgorithm('bubble_sort_optimized', 'Bubble sort (optimized)', bubble_sort_optimized), + SortingAlgorithm( + 'bubble_sort_optimized', 'Bubble sort (optimized)', bubble_sort_optimized + ), ] diff --git a/algorithms/impl/median.py b/algorithms/impl/median.py index a754cdb..7b75219 100644 --- a/algorithms/impl/median.py +++ b/algorithms/impl/median.py @@ -46,7 +46,9 @@ def calc_median_sorting(xs): _ALGORITHMS = [ - Algorithm('median_sorting', 'Median value (using explicit sorting)', calc_median_sorting), + Algorithm( + 'median_sorting', 'Median value (using explicit sorting)', calc_median_sorting + ), Algorithm('median_heaps', 'Median value (using heaps)', calc_median_heaps), ] diff --git a/algorithms/impl/quicksort.py b/algorithms/impl/quicksort.py index dd0c92b..9274c21 100644 --- a/algorithms/impl/quicksort.py +++ b/algorithms/impl/quicksort.py @@ -8,7 +8,6 @@ import sys from ..algorithm import SortingAlgorithm - seed() @@ -76,11 +75,21 @@ def quicksort_random(xs): _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), + 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/algorithms/input_kind.py b/algorithms/input_kind.py index 08e1c9e..53938b0 100644 --- a/algorithms/input_kind.py +++ b/algorithms/input_kind.py @@ -7,7 +7,6 @@ from array import array from enum import Enum from random import seed, sample - seed() diff --git a/algorithms/params.py b/algorithms/params.py index 486cb0e..d1122c4 100644 --- a/algorithms/params.py +++ b/algorithms/params.py @@ -19,11 +19,11 @@ class TimeUnits(Enum): def get_factor(self): if self is TimeUnits.SECONDS: - return 1. + return 1.0 if self is TimeUnits.MILLISECONDS: - return 1000. + return 1000.0 if self is TimeUnits.MICROSECONDS: - return 1000000. + return 1000000.0 raise NotImplementedError('invalid time units: ' + str(self)) def __str__(self): @@ -31,8 +31,9 @@ class TimeUnits(Enum): class AlgorithmParameters: - def __init__(self, algorithm, min_len, max_len, - input_kind=InputKind.AVERAGE, iterations=1): + def __init__( + self, algorithm, min_len, max_len, input_kind=InputKind.AVERAGE, iterations=1 + ): if isinstance(algorithm, str): algorithm = registry.get(algorithm) @@ -111,8 +112,7 @@ class AlgorithmParameters: return 'Running time ({})'.format(units) def _format_plot_title(self): - return '{}, {} case'.format( - self.algorithm.display_name, self.input_kind) + return '{}, {} case'.format(self.algorithm.display_name, self.input_kind) def _format_plot_suptitle(self): return self.algorithm.display_name diff --git a/algorithms/registry.py b/algorithms/registry.py index 3bc6495..aa07052 100644 --- a/algorithms/registry.py +++ b/algorithms/registry.py @@ -5,7 +5,6 @@ from . import impl - _ALL_ALGORITHMS = impl.refresh_algorithms() diff --git a/algorithms/scripts/plot.py b/algorithms/scripts/plot.py index bb441e1..5eb8b16 100755 --- a/algorithms/scripts/plot.py +++ b/algorithms/scripts/plot.py @@ -12,25 +12,27 @@ from ..input_kind import InputKind from ..params import AlgorithmParameters from .. import 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, - iterations=_DEFAULT_ITERATIONS, - output_path=None): +def plot_algorithm( + algorithm, + input_kind=_DEFAULT_INPUT_KIND, + min_len=_DEFAULT_MIN_LENGTH, + max_len=_DEFAULT_MAX_LENGTH, + iterations=_DEFAULT_ITERATIONS, + output_path=None, +): if isinstance(algorithm, str): algorithm = registry.get(algorithm) - params = AlgorithmParameters(algorithm, min_len, max_len, - input_kind=input_kind, - iterations=iterations) + params = AlgorithmParameters( + algorithm, min_len, max_len, input_kind=input_kind, iterations=iterations + ) params.plot_running_time(output_path) @@ -67,8 +69,7 @@ def _format_algorithm(codename): 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()))) + return descr + '\n'.join(map(_format_algorithm, sorted(registry.get_codenames()))) def _format_description(): @@ -78,7 +79,8 @@ def _format_description(): def _create_argument_parser(): return argparse.ArgumentParser( description=_format_description(), - formatter_class=argparse.RawDescriptionHelpFormatter) + formatter_class=argparse.RawDescriptionHelpFormatter, + ) def _parse_args(args=None): @@ -86,27 +88,50 @@ def _parse_args(args=None): args = sys.argv[1:] parser = _create_argument_parser() - parser.add_argument('algorithm', metavar='CODENAME', - choices=registry.get_codenames(), - help='algorithm codename') - parser.add_argument('--iterations', '-r', metavar='N', - type=_parse_positive_integer, - default=_DEFAULT_ITERATIONS, - help='set number of algorithm iterations') - parser.add_argument('--input', '-i', dest='input_kind', - choices=InputKind, - type=_parse_input_kind, default=_DEFAULT_INPUT_KIND, - help='specify input kind') - parser.add_argument('--min', '-a', metavar='N', dest='min_len', - type=_parse_non_negative_integer, - default=_DEFAULT_MIN_LENGTH, - help='set min input length') - parser.add_argument('--max', '-b', metavar='N', dest='max_len', - type=_parse_non_negative_integer, - default=_DEFAULT_MAX_LENGTH, - help='set max input length') - parser.add_argument('--output', '-o', metavar='PATH', dest='output_path', - help='set plot file path') + parser.add_argument( + 'algorithm', + metavar='CODENAME', + choices=registry.get_codenames(), + help='algorithm codename', + ) + parser.add_argument( + '--iterations', + '-r', + metavar='N', + type=_parse_positive_integer, + default=_DEFAULT_ITERATIONS, + help='set number of algorithm iterations', + ) + parser.add_argument( + '--input', + '-i', + dest='input_kind', + choices=InputKind, + type=_parse_input_kind, + default=_DEFAULT_INPUT_KIND, + help='specify input kind', + ) + parser.add_argument( + '--min', + '-a', + metavar='N', + dest='min_len', + type=_parse_non_negative_integer, + default=_DEFAULT_MIN_LENGTH, + help='set min input length', + ) + parser.add_argument( + '--max', + '-b', + metavar='N', + dest='max_len', + type=_parse_non_negative_integer, + default=_DEFAULT_MAX_LENGTH, + help='set max input length', + ) + parser.add_argument( + '--output', '-o', metavar='PATH', dest='output_path', help='set plot file path' + ) return parser.parse_args(args) diff --git a/algorithms/scripts/test.py b/algorithms/scripts/test.py index ba7bf0a..42b1be8 100755 --- a/algorithms/scripts/test.py +++ b/algorithms/scripts/test.py @@ -10,8 +10,7 @@ import argparse import sys from ..input_kind import InputKind -import ..registry as registry - +from .. import registry _DEFAULT_INPUT_KIND = InputKind.AVERAGE _DEFAULT_LENGTH = 100 @@ -50,8 +49,7 @@ def _format_algorithm(codename): 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()))) + return descr + '\n'.join(map(_format_algorithm, sorted(registry.get_codenames()))) def _format_description(): @@ -61,7 +59,8 @@ def _format_description(): def _create_argument_parser(): return argparse.ArgumentParser( description=_format_description(), - formatter_class=argparse.RawDescriptionHelpFormatter) + formatter_class=argparse.RawDescriptionHelpFormatter, + ) def _parse_args(args=None): @@ -69,18 +68,30 @@ def _parse_args(args=None): args = sys.argv[1:] parser = _create_argument_parser() - parser.add_argument('algorithm', metavar='CODENAME', - choices=registry.get_codenames(), - help='algorithm codename') - parser.add_argument('--input', '-i', dest='input_kind', - choices=InputKind, - type=_parse_input_kind, - default=_DEFAULT_INPUT_KIND, - help='specify input kind') - parser.add_argument('--length', '-l', '-n', metavar='N', - type=_parse_non_negative_integer, - default=_DEFAULT_LENGTH, - help='set input length') + parser.add_argument( + 'algorithm', + metavar='CODENAME', + choices=registry.get_codenames(), + help='algorithm codename', + ) + parser.add_argument( + '--input', + '-i', + dest='input_kind', + choices=InputKind, + type=_parse_input_kind, + default=_DEFAULT_INPUT_KIND, + help='specify input kind', + ) + parser.add_argument( + '--length', + '-l', + '-n', + metavar='N', + type=_parse_non_negative_integer, + default=_DEFAULT_LENGTH, + help='set input length', + ) return parser.parse_args(args) |