import timeit
import matplotlib.pyplot as plt


lengths = [2 ** i for i in xrange(15)]

list_time = []
dict_time = []
for l in lengths:
    list_time.append(timeit.timeit('%i in d' % (l/2), 'd=range(%i)' % l))
    dict_time.append(timeit.timeit('%i in d' % (l/2),
                                   'd=dict.fromkeys(range(%i))' % l))
    print l, list_time[-1], dict_time[-1]

plt.figure(figsize=(8,4))
plt.loglog(lengths, dict_time, label='dict')
plt.loglog(lengths, list_time, label='list')
plt.title('List vs Dict Lookup Time')
plt.xlabel('Num of entries')
plt.ylabel('Executing 10,000 times (s)')
plt.legend()
plt.savefig('list_vs_dict.pdf')

repeat_dict_time = []
for l in lengths:
    repeat_dict_time.append(timeit.repeat('%i in d' % (l/2),
                                          'd=dict.fromkeys(range(%i))' % l,
                                          repeat=10))
plt.figure(figsize=(8,4))
plt.loglog(lengths, [min(i) for i in repeat_dict_time], label='dict')
plt.title('Dict Lookup Time')
plt.xlabel('Num of entries in dict')
plt.ylabel('Best of 10 executing 10,000 times (s)')
plt.legend()
plt.savefig('dict_lookup.pdf')