# hashtables in Python
from functools import reduce # needed for python 3
from math import sqrt
from time import time

durationSum = 0.0
durationMeas = []
for n in range(10,0,-1):
    startTime = time()
    ht = {}
    # use xrange as the generator (2.6), python 3 range is default
    [ht.setdefault(i,float(n+i)) for i in xrange(10000000,0,-1)]
    duration = time() - startTime
    durationSum = durationSum + duration
    durationMeas.append(duration)
    print n
# find adjustment
startTime = time()
[float(3+i) for i in xrange(10000000,0,-1)]
adjustment = time() - startTime
# report on timing
meanT = durationSum / 10.0
stdv = sqrt(reduce(lambda x, y: x + (y-meanT)*(y-meanT), durationMeas, 0.0) / 10.0)
print("insert timing (ordered) in seconds: mean %.3f, adj-mean %.3f, stdv %.3f" % (meanT,meanT-adjustment,stdv))
# lookup timing
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), ht.get(lfsr,0)+x), xrange(0,10000000), (lfsr1,0.0))
lookupDuration = time() - startTime
# find adjustment
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), x), xrange(0,10000000), (lfsr1,0.0))
adjustment = time() - startTime
# report on timing
print("lookup timing (mostly misses) in seconds: %.3f, adj %.3f\n" % (lookupDuration, lookupDuration-adjustment))

# unordered insert
durationSum = 0.0
durationMeas = []
for n in range(10,0,-1):
    startTime = time()
    ht = {}
    lfsr0 = 1
    lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
    reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001),ht.setdefault(lfsr,float(n+i))), xrange(10000000,0,-1), (lfsr1,0.0))
    duration = time() - startTime
    durationSum = durationSum + duration
    durationMeas.append(duration)
    print n
# find adjustment
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), x), xrange(0,10000000), (lfsr1,0.0))
adjustment = time() - startTime
# report on timing
meanT = durationSum / 10.0
stdv = sqrt(reduce(lambda x, y: x + (y-meanT)*(y-meanT), durationMeas, 0.0) / 10.0)
print("insert timing (unordered) in seconds: mean %.3f, adj-mean %.3f, stdv %.3f" % (meanT,meanT-adjustment,stdv))
# lookup timing
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), ht.get(lfsr,0)+x), xrange(0,10000000), (lfsr1,0.0))
lookupDuration = time() - startTime
# find adjustment
startTime = time()
lfsr0 = 1
lfsr1 = (lfsr0 >> 1) ^ (0 - (lfsr0 & 1) & 0xd0000001)
reduce(lambda (lfsr,x),i: ((lfsr >> 1) ^ (0 - (lfsr & 1) & 0xd0000001), x), xrange(0,10000000), (lfsr1,0.0))
adjustment = time() - startTime
# report on timing
print("lookup timing (no misses) in seconds: %.3f, adj %.3f\n" % (lookupDuration, lookupDuration-adjustment))