aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
-rw-r--r--README.md6
-rw-r--r--plot.bat20
-rw-r--r--plot.py75
-rw-r--r--test.py26
4 files changed, 69 insertions, 58 deletions
diff --git a/README.md b/README.md
index e277573..6c9613d 100644
--- a/README.md
+++ b/README.md
@@ -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.
diff --git a/plot.bat b/plot.bat
index 70b1f64..ad7c4e9 100644
--- a/plot.bat
+++ b/plot.bat
@@ -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
diff --git a/plot.py b/plot.py
index 2771467..6163363 100644
--- a/plot.py
+++ b/plot.py
@@ -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)
diff --git a/test.py b/test.py
index b3d9dd3..7acc4bf 100644
--- a/test.py
+++ b/test.py
@@ -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))