""" CS 101 class example Tests timing of linear vs. binary search """ import random import time 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 linear_test(data, num_queries, largest): """ Given an unsorted 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 linearSearch(random_num, data) >= 0: count += 1 return time.time() - begin def binary_test(data, num_queries, largest): """ Given a sorted list 'data', perform 'num_queries' checks using binary search 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 binarySearch(random_num, data) >= 0: count += 1 return time.time() - begin def linearSearch(target, t): """ Returns index of target in list t or -1 if not found """ n = len(t) for i in range(n): if t[i] == target: return i # return location where found return -1 # target not found def binarySearch(target, t): """ Return location of target in sorted list t or -1 if not found """ lo = 0 hi = len(t)-1 while lo <= hi: mid = lo + (hi-lo)//2 if t[mid] == target: return mid elif t[mid] < target: lo = mid+1 else: # t[mid] > target hi = mid-1 return -1 def speed_test(set_size, num_queries): """Print timing for creating and querying of linear and binary search""" # generate random list begin = time.time() list_data = generate_list(set_size) print("List creation took %f seconds" % (time.time()-begin)) print("--") # time multiple calls to linear search elapsed = linear_test(list_data, num_queries, set_size*10) print("%d Linear searches took %f seconds" % (num_queries, elapsed)) # time multiple calls to binary search list_data.sort() elapsed = binary_test(list_data, num_queries, set_size*10) print("%d Binary searches took %f seconds" % (num_queries, elapsed)) def speed_data(num_queries, list_size_min, list_size_max, step_size): """ Print a table of runtimes for querying lists of different sizes. """ print("size\tlinear\tbinary") for list_size in range(list_size_min, list_size_max, step_size): # generate random list list_data = generate_list(list_size) # time the list querying linear_elapsed = linear_test(list_data, num_queries, list_size*10) # time the list querying binary_elapsed = binary_test(list_data, num_queries, list_size*10) print("%d\t%f\t%f" % (list_size, linear_elapsed, binary_elapsed)) #speed_test(100000, 1000) #speed_data(1000, 10000, 100000, 5000)