-
Notifications
You must be signed in to change notification settings - Fork 0
/
benchmarker.py
83 lines (65 loc) · 3.55 KB
/
benchmarker.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import timeit
from tabulate import tabulate
from data.dictionary_utils import get_benchmarking_dictionary
# noinspection PyUnresolvedReferences
from spelling_bee_solvers import preprocess_get_bit_to_word_dict, preprocess_get_prefix_tree, \
preprocess_get_radix_tree, get_bee_solutions_naive, get_bee_solutions_bitwise, get_bee_solutions_prefix_tree, \
get_bee_solutions_radix_tree, preprocess_get_nested_prefix_tree, get_bee_solutions_nested_prefix_tree
# NYT Spelling Bee Puzzle from 2019/06/08 which had the most official solutions
benchmark_center = 'o'
benchmark_others = 'ctpnme'
benchmarking_word_list = get_benchmarking_dictionary()
bit_to_word_dict = preprocess_get_bit_to_word_dict(benchmarking_word_list)
prefix_tree = preprocess_get_prefix_tree(benchmarking_word_list)
nested_prefix_tree = preprocess_get_nested_prefix_tree('', benchmarking_word_list, {})
radix_tree = preprocess_get_radix_tree(benchmarking_word_list, {})
naive_solution_stmt = """
get_bee_solutions_naive(benchmark_center, benchmark_others, benchmarking_word_list)
"""
bitwise_solution_stmt = """
get_bee_solutions_bitwise(benchmark_center, benchmark_others, bit_to_word_dict)
"""
prefix_tree_solution_stmt = """
get_bee_solutions_prefix_tree(benchmark_center, benchmark_others, prefix_tree)
"""
nested_prefix_tree_solution_stmt = """
get_bee_solutions_nested_prefix_tree(benchmark_center, benchmark_others, nested_prefix_tree)
"""
radix_tree_solution_stmt = """
get_bee_solutions_radix_tree(benchmark_center, benchmark_others, radix_tree)
"""
iterations = 10000
repetitions = 5 # default
naive_results = timeit.repeat(stmt=naive_solution_stmt, number=iterations, repeat=repetitions, globals=globals())
naive_min = min([r / iterations for r in naive_results])
bitwise_results = timeit.repeat(stmt=bitwise_solution_stmt, number=iterations, repeat=repetitions, globals=globals())
bitwise_min = min([r / iterations for r in bitwise_results])
prefix_tree_results = timeit.repeat(stmt=prefix_tree_solution_stmt, number=iterations, repeat=repetitions,
globals=globals())
prefix_tree_min = min([r / iterations for r in prefix_tree_results])
nested_prefix_tree_results = timeit.repeat(stmt=nested_prefix_tree_solution_stmt, number=iterations, repeat=repetitions,
globals=globals())
nested_prefix_tree_min = min([r / iterations for r in nested_prefix_tree_results])
radix_tree_results = timeit.repeat(stmt=radix_tree_solution_stmt, number=iterations, repeat=repetitions,
globals=globals())
radix_tree_min = min([r / iterations for r in radix_tree_results])
print(f"Iterations:\t\t{iterations}")
print(f"Repetitions:\t{repetitions}")
print()
print(tabulate([['Naive', naive_min, naive_min / naive_min],
['Bitwise', bitwise_min, naive_min / bitwise_min],
['Prefix Tree', prefix_tree_min, naive_min / prefix_tree_min],
['Nested Prefix Tree', nested_prefix_tree_min, naive_min / nested_prefix_tree_min],
['Radix Tree', radix_tree_min, naive_min / radix_tree_min]],
headers=['Strategy', 'Min Time (s)', 'Speedup']))
"""
Iterations: 10000
Repetitions: 5
Strategy Min Time (s) Speedup
------------------ -------------- ---------
Naive 0.0530078 1
Bitwise 0.0129828 4.08294
Prefix Tree 0.000655576 80.8569
Nested Prefix Tree 0.000531249 99.7797
Radix Tree 0.000426973 124.148
"""