""" CS 101 class example (borrowed from CS 150) Tests timing of sets vs. lists """ import random import time def generate_set(set_size): """Return a set of random integers of the given size""" data = set() while len(data) < set_size: data.add(random.randint(0, set_size*10)) return data def generate_list(list_size): """Return a list of random integers of the given size""" data = [] for i in range(list_size): data.append(random.randint(0, list_size*10)) return data def query_data(data, num_queries, largest): """ Given a set or list 'data', perform 'num_queries' checks to see whether a random integer between 0 and 'largest' is contained in 'data'. Return the total time taken. """ # 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 speed_test(set_size, num_queries): """Print timing for creating and querying of lists and sets""" # 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(num_queries, set_size_min, set_size_max, step_size): """ Print a table of runtimes for querying lists and sets of different sizes. """ print("size\tlist\tset") for set_size in range(set_size_min, set_size_max, step_size): # generate random list list_data = generate_list(set_size) # generate random set set_data = generate_set(set_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" % (set_size, list_elapsed, set_elapsed)) #speed_test(100000, 1000) #speed_data(1000, 10000, 100000, 5000)