May-02-2020, 11:39 AM
(This post was last modified: May-02-2020, 11:39 AM by chris_drak.)
You are right. Now with comments.
import string
import random
import time
random.seed(1059442)
global max_load_factor
max_load_factor = 0.6
#--------------------------------
def primeGreaterThan2(num):
while True: #Look for next prime number
if num % 2 == 1:
isPrime = True
for x in range(3,int(num**0.5),2):
if num % x == 0:
isPrime = False
break
if isPrime:
return num
num += 1
N = primeGreaterThan2(1000)
#-------------------------------------
#N=1000
arr = [ None for _ in range(N)] #Make list of None elements
#This is the Hash Table
#-------------------------------------
def CreatNewItem():
days = ["Mon", "Tue", "Wed" , "Thu" , "Fri", "Sat"]
letters = ['W','X','Z','Y']
sl = ['1','2','3','4','5','6','7','8','9','0','1','2','3','4','5','6']
for x in letters:
while True:
p = random.randint(0,15) #choose a random seat
if sl[p].isdigit(): #Check if this seat is
sl[p] = x #Replace number with letter
break
s = ''.join(sl) #Make list s1 into a string s
d = random.randint(0,5) #Choose a random day form list days
day = days[d]
money = random.randint(10,100) #Choose a random nymber for maney
a = [s,day,money] #Combine all those elements into a list
return a
#--------------------------------------
def Ηash(key, tablesize):
sum = 0
for pos in range(len(key)):
sum = sum + ord(key[pos])*10**pos #Make a hash code
h = sum % tablesize
return h
#--------------------------------------
def rehash(oldhash , tablesize):
rh = ( oldhash + 1 ) % tablesize #Make a rehash code in case of collision, linear probing
return rh
#----------------------------------------
def put (arr,a,N,lenght,collisions):
if float(lenght)/float(N) >= max_load_factor:
(arr,N,collisions) = Resize(arr,N,lenght,collisions) #Check load factor and call Resize if needed
key = a[0] #Name a[0](card) key
i = Ηash(key,N) #Call Hash to make a hash code
j =0
while (True):
if arr[i] is None: #Check if seat arr[i] is None
arr[i] = a #Replace that seat with element a
lenght = lenght + 1 #Increase lenght by 1
break
elif arr[i][0] == key: #If the elemnt a has the same key with seat arr[i]
arr[i][2] = arr[i][2] + a[2] #Add money(a[2])
arr[i][1] = arr[i][1] + a[1] #Add day (a[1])
break
else:
if j == 0 : #Check if this is the 1st collision of this element
collisions = collisions +1
j = 1
i = rehash(i,N) #Call rehash to make a new hash code
return (lenght,N,arr,collisions )
#----------------------------------------
def Resize(arr,N,lenght,collisions):
N = primeGreaterThan2(2*N) #Find the next bigger prime number
#N=2*N #Double N
collisions = 0 #Set collision to zero
lenght = 0 #Set lenght to zero
arr2 = [ None for _ in range(N)] #Make a new list of None elements Thats the bouble size hash table
for p in arr: #Put elements of arr(old hash table) in the arr2(new hash table)
if p is not None:
(lenght,N,arr2,collisions)=put(arr2,p,N,lenght,collisions)
return (arr2,N,collisions) #Return new hash table
#----------------------------------------
def Find_max_money(arr,N):
max_money = 0 #Maximum amount of money
for i in range(0,N): #For all the elements in arr(hash tsble)
if arr[i] == None: #If elements is None continue
continue
elif arr[i][2] > max_money: #If money(arr[i][2]) is bigger than Maximum amount of money
max_money = arr[i][2] #Change Maximum amount of money
key = arr[i][0] #Keep the key/card
return (key,max_money)
#----------------------------------------
def Find_most_visits(arr,N):
max_len = 0 #Maximum lenght of string with days
for i in range(0,N): #For all the elements in arr(hash tsble)
if arr[i] == None: #If elements is None continue
continue
elif len(arr[i][1]) > max_len: #If days(arr[i][1]) is bigger than Maximum lenght of string with days
max_len = len(arr[i][1]) #Change Maximum lenght of string with days
key = arr[i][0] #Keep the key/card
visits = int(max_len/3) #Divide by 3 to find the number of days
return (key,visits)
#-----------------------------------------
def Find_most_visited_day(arr,N):
days = ["Mon", "Tue", "Wed" , "Thu" , "Fri", "Sat"] #List of Days
visits = [0,0,0,0,0,0] #List of visits for each day
max_v = 0 #Maximum visits
d = 0 #Position of Day
for i in range(0,len(days)): #For all the days
for j in range(0,N): #For all the elements in arr(hash tsble)
if arr[j] == None: #If elements is None continue
continue
else:
v = arr[j][1].count(days[i]) #Count the visits of each day
visits[i] = visits[i] + v #Add it in the appropriate seat of visits list
for i in range(0,len(visits)): #For all the elements in visits
if visits[i] > max_v: #If visits[i] is bigger than Maximum visits
max_v = visits[i] #Change Maximum visits
d = i #Keep position on day
mday = days[d] #Keep day
return(mday,max_v)
#-----------------------------------------
def find_item(arr,N,key):
hashed_key = Ηash(key,N) #Find the hash code for that key
if arr[hashed_key] is None: #If arr[hashed_key] is None raise error
raise KeyError
if arr[hashed_key][0] != key: #If arr[hashed_key][0] isn't the one we looking for
original_key = hashed_key #Keep that possition
while arr[hashed_key][0] != key: #Look until we find what we want
hashed_key = rehash(hashed_key,N) #Find the new hash code
if arr[hashed_key] is None: #If arr[hashed_key] is None raise error
raise KeyError
if hashed_key == original_key: #If new hsh code is the same with the old raise error
raise KeyError
return hashed_key
#----------------------------------------
def get_item(arr,N,key):
index = find_item(arr,N,key) #Keep the results of get_item, that is the position of key in arr(hash table)
return arr[index]
#-----------------------------------------
l = 0 #lenght, that is how many elements in arr are not None
collisions = 0 #The number of collitions
print("-----------\nload factor:",max_load_factor)
t0 = time.time()
i=0
while i!=1000000: #Create the data serial
b = CreatNewItem()
(l,N,arr,collisions) = put(arr,b,N,l,collisions) #Put new data in arr(hash table)
i=i+1
t1 = time.time() - t0 #Calculate running time
print('\ntime is {:0.20f}'.format(t1))
print("\ncollisions:",collisions)
(card,money) = Find_max_money(arr,N) #Call Find_max_money to find the card with the maximum amount of money
print("\nThe card with the most money is:",card,"and the money:",money)
c = get_item(arr,N,card) #Call Find_most_visit to find the card with the maximum amount of visits
(card2,visits) = Find_most_visits(arr,N)
print("\nThe card with the most visits is:",card2,"and the vistits:",visits)
c1 = get_item(arr,N,card2)
(day,max_visits) = Find_most_visited_day(arr,N) #Call Find_most_visited_day to find the day with the maximum amount of visits
print("\nThe day with the most visits is:",day,"and the vistits:",max_visits)