import timeit
import gc
def best_case_input(n: int) -> list:
return [1 for i in range(n)]
def worst_case_input(n: int) -> list:
return [i for i in range(n)]
def distinct1(l: list) -> list:
d = []
for x in l:
if x not in d:
d.append(x)
return d
def distinct2(l: list) -> list:
d = set()
for x in l:
if x not in d:
d.add(x)
return d
def time(fn, arg):
gc.disable()
start = timeit.default_timer()
fn(arg)
end = timeit.default_timer()
gc.enable()
return end - start
def graph(name: str, sizes: list, times: list):
import matplotlib.pyplot as plt
plt.figure()
plt.scatter(sizes, times)
plt.savefig(name + ".png")
plt.close()
def generate_graphs():
sizes = [100, 500, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000]
# best case graphs
inputs = [best_case_input(size) for size in sizes]
results1 = [time(distinct1, arg) for arg in inputs]
results2 = [time(distinct2, arg) for arg in inputs]
graph("best1", sizes, results1)
graph("best2", sizes, results2)
# worst case graphs
inputs = [worst_case_input(size) for size in sizes]
results1 = [time(distinct1, arg) for arg in inputs]
results2 = [time(distinct2, arg) for arg in inputs]
graph("worst1", sizes, results1)
graph("worst2", sizes, results2)
if __name__ == '__main__':
generate_graphs()