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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
import math
from itertools import product, accumulate, count, repeat
from functools import reduce
from new_suffix_array import ukkonen
import timeit
import random
def test(func, max_len, max_letters, num_iterations=math.inf):
alphabet = "".join(map(chr, range(ord("a"), ord("a") + max_letters)))
combos = map(lambda x: "".join(x), product(alphabet, repeat=max_len-1))
total_time = 0
longest = "", -1
i = 0
for i, string in enumerate(combos):
print(string, end=": ")
start = timeit.default_timer()
func(string)
stop = timeit.default_timer() - start
print(f"{(stop * 10 ** 3):.6f}ms")
if stop > longest[1]:
longest = string, stop
total_time += stop
if i >= num_iterations:
break
print("**** TEST ENDED ****")
print(f"Total time taken: {(total_time * 10):.6f}s = "
f"{(total_time * 10 ** 6):.3f}μs")
print(f"Longest string was '{longest[0]}' taking {(longest[1] * 10 ** 6):.3f}μs")
if i > 0:
print(f"Average time taken: {(total_time / i * 10):.6f}s = "
f"{(total_time / i * 10 ** 6):.3f}μs")
return total_time / i
# test(ukkonen, 50, 6)
# if __name__ == "__main__":
# for length in range(2, 10):
# print(f"==== {length=} ====")
# before = test(ukkonen, length, 6)
# after = test(ukkonen, length*2, 6)
# print(f"From {length} -> {length*2}: Ratio = {after/before}")
def random_string(length, variance=6):
return "".join(map(chr, [random.randrange(ord("A"), ord("A") + variance) for _ in range(length)]))
def do_and_get_averages(func, length, num_times=100):
times = []
# the_range = range(ord("A"), ord("A")+26+26+6)
# letters = map(chr, the_range)
for string in [random_string(length) for _ in range(num_times)]:
average = 0
for i in range(5):
# print(string, end=": ")
start = timeit.default_timer()
func(string)
stop = timeit.default_timer() - start
average += stop
# print(f"{(stop * 10 ** 3):.6f}ms")
average /= 5
times.append(average)
return times
# for i in range(50, 100):
# first = sum(do_and_get_averages(ukkonen, i, 100))/100
# second = sum(do_and_get_averages(ukkonen, i*2, 100))/100
# print(i, first, second, second/first)
def random_test(func, length, interval=10000):
i = 0
while True:
func(random_string(length, 6))
i += 1
if i % interval == 0:
print(i)
random_test(ukkonen, 100)
# times = []
# # the_range = range(ord("A"), ord("A")+26+26+6)
# # letters = map(chr, the_range)
# for string in [random_string(20) for _ in range(100)]:
# average = 0
# for i in range(20):
# # print(string, end=": ")
# start = timeit.default_timer()
# ukkonen(string)
# stop = timeit.default_timer() - start
# average += stop
# # print(f"{(stop * 10 ** 3):.6f}ms")
# average /= 5
# times.append(average)
# print(times)
# for i in range(1, len(the_range)//2):
# print(f"{i}:\t{times[i-1]}\t{times[(i-1)*2]}\t{times[(i-1)*2]/times[i-1]}")
|
