# Jay Summet # CS 1301 fall 2013 # Placed in the Pubic Domain # # Python 3 Example code to demonstrate the differing time it takes # to search for something in a list, a sorted list or a dictionary # of different sizes from random import * from time import time #Generates a random list of numbers: def randList(N): rList = [] for x in range(N): rList = rList + [ randrange(0,N*2) ] return rList #Generates a list and a dictionary of random number/letter pairs. def genRandomData(rList): ourList = [] ourDict = {} #for each random number, generate a random (character) value for num in rList: rValue = chr( randrange(32,97) ) ourTuple = (num,rValue) ourList.append( ourTuple) ourDict[num] = rValue #Return the tuple containing both the list and dictionary. return( (ourList, ourDict) ) def findValueList(alist, number): #Check each number in the list, if it's the one we are looking for #return the associated value for item in alist: if item[0] == number: return item[1] #If we don't find it, return -1 instead. return(-1) #Binary search... def findValueSortedList(alist, number): #If the list is empty, we return -1. if len(alist) < 1: return(-1) #We assume the list is sorted. Check the middle number first. middleIndex = len(alist) // 2 #Integer division! item = alist[middleIndex] if item[0] == number: return( item[1]) #If it's in 1st half of the list, search only the front. elif item[0] > number: return findValueSortedList( alist[:middleIndex], number) #If it's in the 2nd half of the list, search only the back. elif item[0] < number: return findValueSortedList( alist[middleIndex+1 : ], number) def findValueDict(aDict, number): #If the number is in the dictionary, return it's associated value #otherwise, return -1 return aDict.get(number, -1) # Code that generates random data, and then searches through it # recording the amount of time it took. num = 10000 #Try 10, 100, 1000, and 10,000 numToFind = 10000 rNums = randList(num) rList,rDict = genRandomData(rNums) findNums = randList(numToFind) print("Finding", numToFind, "numbers in the list of length", num) startTime = time() for i in findNums: findValueList(rList,i) endTime = time() print("Finished in", endTime-startTime, "seconds") rSortedList = rList[:] rSortedList.sort() print("Finding", numToFind, "numbers in the sorted list of length", num) startTime = time() for i in findNums: findValueSortedList(rList,i) endTime = time() print( "Finished in", endTime-startTime, "seconds") print("Finding", numToFind, "numbers in the dictionary with :", num, "numbers") startTime = time() for i in findNums: findValueDict(rDict,i) endTime = time() print ("Finished in", endTime-startTime, "seconds")