import random
import time

def speed_test(set_size, num_queries):
    
    # generate random list
    begin = time.time()
    list_data = generate_list(set_size)
    print "List creation took %f seconds" % (time.time()-begin)
    
    # generate random set
    begin = time.time()
    set_data = generate_set(set_size)
    print "Set creation took %f seconds" % (time.time()-begin)
    
    print "--"
    
    # time the list querying
    elapsed = query_data(list_data, num_queries, set_size*10)
    print "List querying took %f seconds" % elapsed

    # time the list querying
    elapsed = query_data(set_data, num_queries, set_size*10)
    print "Set querying took %f seconds" % elapsed
    
def speed_data(set_size, query_min, query_max, step_size):
    # generate random list
    list_data = generate_list(set_size)
    
    # generate random set
    set_data = generate_set(set_size)
    
    for num_queries in range(query_min,query_max,step_size):
        # time the list querying
        list_elapsed = query_data(list_data, num_queries, set_size*10)

        # time the list querying
        set_elapsed = query_data(set_data, num_queries, set_size*10)
        
        print "%d\t%f\t%f" % (num_queries, list_elapsed, set_elapsed)
        
def query_data(data, num_queries, largest):
    
    # we'll count them for fun, but won't do anything with the count
    count = 0 
    
    begin = time.time();
    
    for i in range(num_queries):
        # just check to see if a random number is in there
        random_num = random.randint(0, largest)
        
        if random_num in data:
            count += 1
            
    return time.time() - begin
    
        
def generate_set(set_size):
    data = set()
        
    while len(data) < set_size:
        data.add(random.randint(0, set_size*10))
    
    return data

def generate_list(set_size):
    data = []
    
    for i in range(set_size):
        data.append(random.randint(0, set_size*10));
    
    return data

#speed_data(10000, 1000, 10000, 500)