Изучение языка программирования Python



Pdf көрінісі
бет14/14
Дата04.03.2023
өлшемі1,23 Mb.
#171016
1   ...   6   7   8   9   10   11   12   13   14
Байланысты:
python
бб, соц лекция, algebra-analitika, Практикалық жұмыс 6-7
Хэширование 
Напишем программу, которая по значению ключа рассчитает число 
«хэш». Число рассчитывается так, чтобы значения поискового ключа 
распределились среди всех возможных значений хэша равномерно. 
#описание элемента дерева 
numHashLen=577 
#количество возможных хэшей
from sys import argv 
#для ручного задания имени файла
class PHashNode: 
def __init__(self, val = []): 
self.val = val 
def hash_(s):
#хэш-функция
global numHashLen 
h = 0 
for i in s: 
h = h * 61 + ord(i) 
return h%numHashLen 
#создание списков 
countArr = [0 for _ in range(numHashLen)] 
searchArr = [PHashNode() for _ in range(numHashLen)] 
try:
#попытка получить имя файла из первого аргумента
fname = argv[1] 
except IndexError: 
fname = 'text1.txt' 
with open(fname, 'r') as f:
#чтение из файла и добавление в список 
слов
for line in f: 
for k in line.split(): 
searchArr[hash_(k)].val.append(k) 
countArr[hash_(k)] += 1 
print('\n'.join([str(i)+' '+str(countArr[i]) for i in 
range(len(countArr))]))
#вывод количества слов для каждого хэша

Хэш-функция для каждого символа умножает текущее значение 


(переменная 
h
) хэша, которое изначально для каждой строки равно нулю, на 61 
и прибавляет числовой код символа (функция 
ord
). К примеру, числовое 
представление "а" — 97, "€" — 8364. Функция возвращает остаток деления 
итогового значения на переменную 
numHashLen
, что ограничивает число 
возможных значений.


30
Не обязательно писать по одному слову в строке, в качестве разделителя 
можно использовать как переносы строк, так и пробелы.
Так для слова "лосось" действия будут следующими: 
ord("л") = 1083
h = 1083
ord("о") = 1086
h = 67149 
ord("с") = 1089
h = 4097178
ord("о") = 1086
h = 249928944
ord("с") = 1089
h = 15245666673
ord("ь") = 1100
h = 929985668153
Функция вернёт остаток от деления 929985668153 на 577, который равен 441. 


Достарыңызбен бөлісу:
1   ...   6   7   8   9   10   11   12   13   14




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет