import time
from random import randint, choice
import sys
allElems = {}
class Node:
def __init__(self, v_):
self.v = v_
self.next = None
self.dummy_data = [randint(0,100)
for _ in xrange(randint(50,100))]
allElems[self.v] = self
if self.v > 0:
self.dummy_links = [allElems[randint(0, self.v-1)] for _ in xrange(10)]
else:
self.dummy_links = [self]
def set_next(self, l):
self.next = l
def follow(node):
acc = []
count = 0
cur = node
assert node.v is not None
assert cur is not None
while count < 50000:
# return a value; generate some garbage
acc.append((cur.v, [choice("abcdefghijklmnopqrstuvwxyz") for x in xrange(100)]))
# if we have reached the end, chose a random link
cur = choice(cur.dummy_links) if cur.next is None else cur.next
count += 1
return acc
def build(num_elems):
start = time.time()
print "start build"
root = Node(0)
cur = root
for x in xrange(1, num_elems):
e = Node(x)
cur.next = e
cur = e
print "end build %f" % (time.time() - start)
return root
num_timings = 100
if __name__ == "__main__":
num_elems = int(sys.argv[1])
build(num_elems)
total = 0
timings = [0.0] * num_timings # run times for the last num_timings runs
i = 0
beginning = time.time()
while time.time() - beginning < 600:
start = time.time()
elem = allElems[randint(0, num_elems - 1)]
assert(elem is not None)
lst = follow(elem)
total += choice(lst)[0] # use the return value for something
end = time.time()
elapsed = end-start
timings[i % num_timings] = elapsed
if (i > num_timings):
slow_time = 2 * sum(timings)/num_timings # slow defined as > 2*avg run time
if (elapsed > slow_time):
print "that took a long time elapsed: %f slow_threshold: %f 90th_quantile_runtime: %f" % \
(elapsed, slow_time, sorted(timings)[int(num_timings*.9)])
i += 1
print total