Posts: 3
Threads: 2
Joined: Mar 2020
May-02-2020, 08:59 AM
(This post was last modified: May-02-2020, 09:05 AM by Yoriz.)
Hello,
I have the following code and I would like it to give results in about 20 seconds. Thanks...
import string
import random
import time
random.seed(1059442)
global max_load_factor
max_load_factor = 0.1
#--------------------------------
def primeGreaterThan2(num):
while True:
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)]
#-------------------------------------
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)
if sl[p].isdigit():
sl[p] = x
break
s = ''.join(sl)
d = random.randint(0,5)
day = days[d]
money = random.randint(10,100)
a = [s,day,money]
return a
#--------------------------------------
def Ηash(key, tablesize):
sum = 0
for pos in range(len(key)):
sum = sum + ord(key[pos])*10**pos
h = sum % tablesize
return h
#--------------------------------------
def rehash(oldhash , tablesize):
rh = ( oldhash + 1 ) % tablesize
return rh
#----------------------------------------
def put2 (arr,a,N,lenght,collisions):
if float(lenght)/float(N) >= max_load_factor:
(arr,N,collisions) = Resize(arr,N,lenght,collisions)
key = a[0]
i = Ηash(key,N)
j =0
while (True):
if arr[i] is None:
arr[i] = a
lenght = lenght + 1
break
elif arr[i][0] == key:
arr[i][2] = arr[i][2] + a[2]
arr[i][1] = arr[i][1] + a[1]
break
else:
if j == 0 :
collisions = collisions +1 #gia na υπολογιζω τα collition μονο στην πρωτη συγκρουση
j = 1
i = rehash(i,N)
return (lenght,N,arr,collisions )
#----------------------------------------
def Resize(arr,N,lenght,collisions):
N = primeGreaterThan2(2*N)
#N=2*N
collisions = 0
lenght = 0
arr2 = [ None for _ in range(N)]
for p in arr:
if p is not None:
(lenght,N,arr2,collisions)=put2(arr2,p,N,lenght,collisions)
return (arr2,N,collisions)
#----------------------------------------
def Find_max_money(arr,N):
max_money = 0
for i in range(0,N):
if arr[i] == None:
continue
elif arr[i][2] > max_money:
max_money = arr[i][2]
key = arr[i][0]
return (key,max_money)
#----------------------------------------
def Find_most_visits(arr,N):
max_len = 0
for i in range(0,N):
if arr[i] == None:
continue
elif len(arr[i][1]) > max_len:
max_len = len(arr[i][1])
key = arr[i][0]
visits = int(max_len/3)
return (key,visits)
#-----------------------------------------
def Find_most_visited_day(arr,N):
days = ["Mon", "Tue", "Wed" , "Thu" , "Fri", "Sat"]
visits = [0,0,0,0,0,0]
max_v = 0
d = 0
for i in range(0,len(days)):
for j in range(0,N):
if arr[j] == None:
continue
else:
v = arr[j][1].count(days[i])
visits[i] = visits[i] + v
for i in range(0,len(visits)):
if visits[i] > max_v:
max_v = visits[i]
d = i
mday = days[d]
return(mday,max_v)
#-----------------------------------------
def find_item(arr,N,key):
hashed_key = Hash(key,N)
if arr[hashed_key] is None:
raise KeyError
if arr[hashed_key][0] != key:
original_key = hashed_key
while arr[hashed_key][0] != key:
hashed_key = rehash(hashed_key,N)
if arr[hashed_key] is None:
raise KeyError
if hashed_key == original_key:
raise KeyError
return hashed_key
#----------------------------------------
def get_item(arr,N,key):
index = find_item(arr,N,key)
return arr[index]
#-----------------------------------------
l = 0
collisions = 0
print("-----------\n load factor:",max_load_factor)
t0 = time.time()
i=0
while i!=1000000:
b = CreatNewItem()
(l,N,arr,collisions) = put2(arr,b,N,l,collisions)
i=i+1
t1 = time.time() - t0
print('\ntime is {:0.20f}'.format(t1))
print("collisions",collisions)
(card,money) = Find_max_money(arr,N)
print("The card with the most money is:",card,"and the money:",money)
(card2,visits) = Find_most_visits(arr,N)
print("The card with the most visits is:",card2,"and the vistits:",visits)
(day,max_visits) = Find_most_visited_day(arr,N)
print("The day with the most visits is:",card2,"and the vistits:",visits)
Posts: 8,091
Threads: 154
Joined: Sep 2016
This is code without any comments, but with bunch of meaningless one letter names and use of global variables.
I doubt anyone in their right minds would put efforts to try and decipher it, what it is doing and why it is not fast as per your expectations.
Posts: 3
Threads: 2
Joined: Mar 2020
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)
|
