Ха sh таблица задач для образовательных целей - PullRequest
Новая
       10

Ха sh таблица задач для образовательных целей

2 голосов
/ 27 апреля 2020

Проблема заключается в следующем: требуется создать и использовать га sh структуру таблицы в проблемном большом количестве ключей.

Вот шаги:

Создание одного миллиона (1 000 000) посещений универмага и оплата кредитной картой.

Из очень большого количества различных карт создается относительно небольшое подмножество следующим образом. Кредитные карты для посещений будут иметь шестнадцать (16) указанных c фиксированных цифр, например 1234567890123456, но в четырех (4) из шестнадцати (16) случайных позиций они также будут иметь четыре символа: X, Y, Z, W в случайном порядке , например, 12Y45W789012Z4X6 В других местах цены являются начальными.

Я написал коды. Предполагается, что он работает очень быстро, но работает очень медленно, и я не знаю почему ... В настоящее время я использую свой код для 10 000 карт. Не могли бы вы помочь мне? Прошу прощения, мой бедный английский sh ...

Код ниже: 

import string
import random
import time

random.seed(1059442)
global max_load_factor

max_load_factor = 0.6

def printGreaterThan2(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 = printGreaterThan2(1000)


arr = [ [] for _ in range(N)]
arr = [ None for _ in range(N)]



def CreatNewItem():
letters = "WXZY"
days = ["Mon", "Tue", "Wed" , "Thu" , "Fri", "Sat"]
s = ''
count = 0
num = ['1','2','3','4','5','6','7','8','9','0','1','2','3','4','5','6']
list_a = []

while(count!=4):
    a = random.randint(0,15)
    b = random.choice(letters)
    if b not in num and a not in list_a:
        num[a] = b
        count = count + 1
        list_a.append(a)

s = ''.join(num)

d = random.randint(0,5)
day = days[d]
money = random.randint(10,100)
a = [s,day,money]

return a



def hash(key, tablesize):
    sum = 0
    for pos in range(len(key)):
        sum = sum + ord(key[pos])
    hash = sum % tablesize
    return hash

#--------------------------------------
def rehash(oldhash , tablesize):
    rehash = ( oldhash + 1 ) % tablesize
    return rehash
#--------------------------------------
def put2 (arr,a,N,lenght,collitions):

    if float(lenght)/float(N) >= max_load_factor:
        (arr,N,collitions) = Resize(arr,N,lenght,collitions)


    key = a[0]
    i  = hash(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 :
                collitions = collitions +1 
                j = 1
            i = rehash(i,N)

    return (lenght,N,arr,collitions ) 





#----------------------------------------


def Resize(arr,N,lenght,collitions):
    print("resize")
    N = printGreaterThan2(2*N)
    collitions = 0

    arr2 = [ [] for _ in range(N)]
    arr2 = [ None for _ in range(N)]

    for p in arr:
        if p is not None:
            (lenght,N,arr2,collitions)=put2(arr2,p,N,lenght,collitions)

    return (arr2,N,collitions)


#-----------------------------------------    
l = 0
cards = []
collitions = 0



t0 = time.time()
i=0

while i!=10000:
    b = CreatNewItem()

    (l,N,arr,collitions) = put2(arr,b,N,l,collitions)

    i=i+1


t1 = time.time() - t0
print('\ntime is {:0.20f}'.format(t1))
...