# Jay Summet
# CS 1301 Spring 2009
# Placed in the Pubic Domain
#
# 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
    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 = 10   #Try 10, 100, 1000, and 10000
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"