diff options
| -rw-r--r-- | README.md | 6 | ||||
| -rw-r--r-- | plot.bat | 20 | ||||
| -rw-r--r-- | plot.py | 75 | ||||
| -rw-r--r-- | test.py | 26 |
4 files changed, 69 insertions, 58 deletions
@@ -65,9 +65,9 @@ below. **matplotlib** | 1.5.1 | Each of the implemented algorithms was provided with three input sequences: -* a list of *n* consecutive numbers sorted in ascending order ("sorted" input), -* ... in descending order ("reversed" input), -* ... in random order ("randomized" input). +* a list of *n* consecutive numbers sorted in ascending order, +* ... in descending order, +* ... in random order. You can generate the plots using `plot.py`. Consult the output of `plot.py -h` to learn how to use the script. @@ -4,7 +4,7 @@ @setlocal enabledelayedexpansion -@set DEFAULT_REPETITIONS=100 +@set DEFAULT_ITERATIONS=100 @set DEFAULT_MIN=0 @set DEFAULT_MAX=200 @@ -12,9 +12,9 @@ @set algorithm=%1 @if not E%2 == E ( - set repetitions=%2 + set iterations=%2 ) else ( - set repetitions=%DEFAULT_REPETITIONS% + set iterations=%DEFAULT_ITERATIONS% ) @if not E%3 == E ( set min=%3 @@ -27,18 +27,18 @@ set max=%DEFAULT_MAX% ) -plot.py -l "%algorithm%" -a "%min%" -b "%max%" -r "%repetitions%" ^ - -i sorted -o "%algorithm%_%repetitions%_sorted_%min%_%max%.png" ^ +plot.py -l "%algorithm%" -a "%min%" -b "%max%" -r "%iterations%" ^ + -i ascending -o "%algorithm%_%iterations%_ascending_%min%_%max%.png" ^ || exit /b !errorlevel! -plot.py -l "%algorithm%" -a "%min%" -b "%max%" -r "%repetitions%" ^ - -i randomized -o "%algorithm%_%repetitions%_randomized_%min%_%max%.png" ^ +plot.py -l "%algorithm%" -a "%min%" -b "%max%" -r "%iterations%" ^ + -i random -o "%algorithm%_%iterations%_random_%min%_%max%.png" ^ || exit /b !errorlevel! -plot.py -l "%algorithm%" -a "%min%" -b "%max%" -r "%repetitions%" ^ - -i reversed -o "%algorithm%_%repetitions%_reversed_%min%_%max%.png" ^ +plot.py -l "%algorithm%" -a "%min%" -b "%max%" -r "%iterations%" ^ + -i descending -o "%algorithm%_%iterations%_descending_%min%_%max%.png" ^ || exit /b !errorlevel! @exit /b :print_usage: -@echo Usage: %0 ALGORITHM [REPETITIONS=%DEFAULT_REPETITIONS% [MIN=%DEFAULT_MIN% [MAX=%DEFAULT_MAX%]]] +@echo Usage: %0 ALGORITHM [ITERATIONS=%DEFAULT_ITERATIONS% [MIN=%DEFAULT_MIN% [MAX=%DEFAULT_MAX%]]] @exit /b 1 @@ -4,63 +4,74 @@ from enum import Enum import gc +import pylab from time import clock -class InputKind(Enum): - SORTED, RANDOMIZED, REVERSED = 'sorted', 'randomized', 'reversed' +class OrderType(Enum): + ASCENDING, RANDOM, DESCENDING = 'ascending', 'random', 'descending' def __str__(self): return self.value + def get_case(self): + if self is OrderType.ASCENDING: + return 'best' + elif self is OrderType.DESCENDING: + return 'worst' + elif self is OrderType.RANDOM: + return 'average' + else: + raise NotImplementedError( + 'unknown "case" for input ordering: \'{}\''.format(self)) + def get_timestamp(): return clock() def init_clock(): get_timestamp() -def gen_input(kind, n): - if kind is InputKind.SORTED: +def gen_input(order, n): + if order is OrderType.ASCENDING: return list(range(n)) - elif kind is InputKind.REVERSED: + elif order is OrderType.DESCENDING: return sorted(range(n), reverse=True) - elif kind is InputKind.RANDOMIZED: + elif order is OrderType.RANDOM: from random import sample return sample(range(n), n) else: raise NotImplementedError( - 'invalid initial input state \'{}\''.format(kind)) + 'invalid input ordering: \'{}\''.format(order)) -def measure_running_time(algorithm, kind, xs_len, repetitions): - xs = gen_input(kind, xs_len) - xss = [list(xs) for _ in range(repetitions)] +def measure_running_time(algorithm, order, xs_len, iterations): + xs = gen_input(order, xs_len) + xss = [list(xs) for _ in range(iterations)] algorithm = algorithm.get_function() gc.disable() started_at = get_timestamp() - for i in range(repetitions): + for i in range(iterations): 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 _decorate_plot(algorithm, iterations, order): + pylab.grid() + pylab.xlabel("Input length") + pylab.ylabel('Running time (sec), {} iteration(s)'.format(iterations)) + pylab.title("{}, {} case".format( + algorithm.get_display_name(), order.get_case())) -def plot_algorithm(algorithm, repetitions, kind, min_len, max_len, output_path=None): - import matplotlib.pyplot as plt - _decorate_plot(algorithm, repetitions, kind, plt) +def plot_algorithm(algorithm, iterations, order, min_len, max_len, output_path=None): + _decorate_plot(algorithm, iterations, order) 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) + running_time.append(measure_running_time(algorithm, order, xs_len, iterations)) + pylab.plot(xs_lengths, running_time) if output_path is None: - plt.show() + pylab.show() else: - plt.savefig(output_path) + pylab.savefig(output_path) if __name__ == '__main__': import algorithms.registry @@ -77,7 +88,7 @@ if __name__ == '__main__': return n def input_kind(s): try: - return InputKind(s) + return OrderType(s) except ValueError: raise argparse.ArgumentError() @@ -86,13 +97,13 @@ if __name__ == '__main__': parser.add_argument('--algorithm', '-l', required=True, choices=algorithms.registry.get_codenames(), help='specify sorting algorithm to use') - parser.add_argument('--repetitions', '-r', + parser.add_argument('--iterations', '-r', type=positive_number, default=1, - help='set number of sorting repetitions') - parser.add_argument('--input', '-i', - choices=tuple(x for x in InputKind), - type=input_kind, default=InputKind.RANDOMIZED, - help='choose initial input state') + help='set number of algorithm iterations') + parser.add_argument('--order', '-i', + choices=tuple(x for x in OrderType), + type=input_kind, default=OrderType.RANDOM, + help='specify input order') parser.add_argument('--min', '-a', type=natural_number, required=True, dest='min_len', help='set min input length') @@ -107,6 +118,6 @@ if __name__ == '__main__': init_clock() plot_algorithm(algorithms.registry.get(args.algorithm), - args.repetitions, args.input, + args.iterations, args.order, args.min_len, args.max_len, args.output_path) @@ -4,23 +4,23 @@ from enum import Enum -class InputKind(Enum): - SORTED, RANDOMIZED, REVERSED = 'sorted', 'randomized', 'reversed' +class OrderType(Enum): + ASCENDING, RANDOM, DESCENDING = 'ascending', 'random', 'descending' def __str__(self): return self.value def gen_input(kind, n): - if kind is InputKind.SORTED: + if kind is OrderType.ASCENDING: return list(range(n)) - elif kind is InputKind.REVERSED: + elif kind is OrderType.DESCENDING: return sorted(range(n), reverse=True) - elif kind is InputKind.RANDOMIZED: + elif kind is OrderType.RANDOM: from random import sample return sample(range(n), n) else: raise NotImplementedError( - 'invalid initial input state \'{}\''.format(kind)) + 'invalid input ordering: \'{}\''.format(kind)) if __name__ == '__main__': import algorithms.registry @@ -30,9 +30,9 @@ if __name__ == '__main__': if n < 0: raise argparse.ArgumentTypeError('cannot be negative') return n - def input_kind(s): + def order(s): try: - return InputKind(s) + return OrderType(s) except ValueError: raise argparse.ArgumentError() @@ -41,13 +41,13 @@ if __name__ == '__main__': 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('--order', '-i', + choices=tuple(x for x in OrderType), + type=order, default=OrderType.RANDOM, + help='specify input order') 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) + xs = gen_input(args.order, args.length) print(algorithms.registry.get(args.algorithm).get_function()(xs)) |