#!/usr/bin/python

import random,time

NUM_SAMPLES = 10000

print "set_size,sample_size,method,time";
for sl in [1,10,20,30,40,50,60,70,80,90,100]:
  for ss in [1,10,20,30,40,50,60,70,80,90,100]:
    s = {}
    l = []
    for i in range(0,sl):
        elem = ('%%0%dd'%ss) % i
        s[elem] = True
        l.append(elem)
    sample = []
    for i in range(0,NUM_SAMPLES):
        i = random.randint(0,sl)
        sample.append(('%%0%dd'%ss) % i)

    t1 = time.time()
    for i in range(0,NUM_SAMPLES):
        res = s.has_key(sample[i])
    t2 = time.time()
    for i in range(0,NUM_SAMPLES):
        res = sample[i] in l
    t3 = time.time()
    print "%d,%d,has_key,%d" % (sl,ss,(t2-t1)*1000)
    print "%d,%d,in_list,%d" % (sl,ss,(t3-t2)*1000)