Zadatak 1
Zadatak 2
Zadatak 1
# file: 'z7-1.py'
import math
import random
import time
from math import floor
class Data :
def __init__ ( self , key = None ):
self . key = key
self . literal = str ( key )
class ChainedHash :
def __init__ ( self , p = 27 , m = 10000 ):
self . p = p
self . m = m
self . a = random . randint ( 0 , p )
self . b = random . randint ( 1 , p )
self . L = [[]] * m
def insert ( self , x ):
h = self . hash ( x . key )
if x in self . L [ h ]:
self . L [ h ]. remove ( x )
self . L [ h ]. append ( x )
def search ( self , k ):
h = self . hash ( k )
for i in self . L [ h ]:
if i . key == k :
return i
return None
def delete ( self , x ):
h = self . hash ( x . key )
if x in self . L [ h ]:
self . L [ h ]. remove ( x )
def hash1 ( self , k ):
return k % m
def hash2 ( self , k ):
KNUTH = 0.6180339887
return floor ( m * (( k * KNUTH ) % 1 ))
def hash3 ( self , k ):
return (( a * k + b ) % p ) % m
def hash ( self , k ):
return self . hash1 ( k )
def random_list ( min , max , elements ):
list = random . sample ( range ( min , max ), elements )
return list
def test ( n , p , m ):
l = random_list ( 1 , n + 1 , n )
start_time = time . clock ()
L = ChainedHash ( p , m )
for i in l :
x = Data ( i )
L . insert ( x )
end_time = time . clock () - start_time
print ( "n:" , n , "m:" , m , "p:" , p , "duration:" , end_time )
if __name__ == "__main__" :
for n in [ 10000 , 50000 , 100000 ]:
for p in [ 23 , 9973 , 99991 ]:
for m in [ p , p // 2 , p // 4 ]:
test ( n , p , m )
Zadatak 2
# file: 'z7-2.py'
import math
import random
import time
from math import floor
class Data :
def __init__ ( self , key = None ):
self . key = key
self . literal = str ( key )
class HashTable :
def __init__ ( self , m = 10000 , c1 = 1 / 2 , c2 = 1 / 2 ):
self . m = m
self . c1 = c1
self . c2 = c2
self . T = [ None ] * m
def insert ( self , k ):
i = 0
while True :
j = self . hash ( k , i )
if self . T [ j ] == None :
self . T [ j ] == k
return j
else :
i += 1
if i == self . m :
break
print ( "ERROR 408" )
def search ( self , k ):
i = 0
while True :
j = self . hash ( k , i )
if self . T [ j ] == None :
return j
i += 1
if self . T [ j ] == None or i == self . m :
break
return None
def delete ( self , x ):
h = self . hash ( x . key )
if x in self . L [ h ]:
self . L [ h ]. remove ( x )
def h1 ( self , k ):
return k % self . m
def h2 ( self , k ):
return 1 + ( k % ( self . m - 1 ))
def hash1 ( self , k , i ):
return ( self . h1 ( k ) + i ) % self . m
def hash2 ( self , k , i ):
return ( self . h1 ( k ) + self . c1 * i + self . c2 * i ** 2 ) % self . m
def hash3 ( self , k , i ):
return ( self . h1 ( k ) + self . h2 ( k )) % self . m
def hash ( self , k , i ):
return self . hash1 ( k , i )
def random_list ( min , max , elements ):
list = random . sample ( range ( min , max ), elements )
return list
def test ( n , m ):
l = random_list ( 1 , n + 1 , n )
start_time = time . clock ()
L = HashTable ( m )
for i in l :
L . insert ( i )
end_time = time . clock () - start_time
print ( "n:" , n , "m:" , m , "duration:" , end_time )
if __name__ == "__main__" :
for n in [ 10000 , 50000 , 100000 ]:
for m in [ n , n // 2 , n // 4 ]:
test ( n , m )
Comments 💬
© 2018 - 2023 Milovan Tomašević. All rights reserved.
Impress
|
Cookies Policy
Powered by MT v9.1.4