Ass 2: Maybe possibly Ukkonen's could be working probably

1 files changed, 94 insertions, 10 deletions

diff --git a/ass2/q2/gen_cases.py b/ass2/q2/gen_cases.py
index f61222b..82d165e 100644
--- a/ass2/q2/gen_cases.py
+++ b/ass2/q2/gen_cases.py
@@ -1,15 +1,99 @@
-from itertools import product
+import math
+from itertools import product, accumulate, count, repeat
+from functools import reduce
 from new_suffix_array import ukkonen
+import timeit
+import random
 
-MAX_LEN = 5
-NUM_LETTERS = 6
 
+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
 
-alphabet = "".join(map(chr, range(ord("a"), ord("a") + NUM_LETTERS)))
-combos = map(lambda x: "".join(x)+"$", product(alphabet, repeat=MAX_LEN))
 
-for i in range(100):
-    try:
-        ukkonen(next(combos))
-    except StopIteration:
-        print("**** TEST ENDED ****")
\ No newline at end of file
+# 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]}")