forked from UNN/2026-rff_mp
133 lines
4.0 KiB
Python
133 lines
4.0 KiB
Python
import time
|
||
import csv
|
||
import random
|
||
import os
|
||
|
||
def create_node(name, phone):
|
||
"""Создает узел для бакета"""
|
||
return {'name': name, 'phone': phone, 'next': None}
|
||
|
||
def ll_insert(head, name, phone):
|
||
"""Вставка в связный список"""
|
||
new_node = create_node(name, phone)
|
||
|
||
if head is None:
|
||
return new_node
|
||
|
||
if head['name'] == name:
|
||
head['phone'] = phone
|
||
return head
|
||
|
||
current = head
|
||
while current['next']:
|
||
if current['next']['name'] == name:
|
||
current['next']['phone'] = phone
|
||
return head
|
||
current = current['next']
|
||
|
||
current['next'] = new_node
|
||
return head
|
||
|
||
def ll_find(head, name):
|
||
"""Поиск в связном списке"""
|
||
current = head
|
||
while current:
|
||
if current['name'] == name:
|
||
return current['phone']
|
||
current = current['next']
|
||
return None
|
||
|
||
def ll_delete(head, name):
|
||
"""Удаление из связного списка"""
|
||
if head is None:
|
||
return None
|
||
|
||
if head['name'] == name:
|
||
return head['next']
|
||
|
||
current = head
|
||
while current['next']:
|
||
if current['next']['name'] == name:
|
||
current['next'] = current['next']['next']
|
||
return head
|
||
current = current['next']
|
||
|
||
return head
|
||
|
||
def hash_function(name, table_size):
|
||
"""Простая хеш-функция"""
|
||
return sum(ord(c) for c in name) % table_size
|
||
|
||
def ht_insert(table, name, phone):
|
||
"""Вставка в хеш-таблицу"""
|
||
index = hash_function(name, len(table))
|
||
table[index] = ll_insert(table[index], name, phone)
|
||
|
||
def ht_find(table, name):
|
||
"""Поиск в хеш-таблице"""
|
||
index = hash_function(name, len(table))
|
||
return ll_find(table[index], name)
|
||
|
||
def ht_delete(table, name):
|
||
"""Удаление из хеш-таблицы"""
|
||
index = hash_function(name, len(table))
|
||
table[index] = ll_delete(table[index], name)
|
||
|
||
def generate_test_data(n=500):
|
||
"""Генерирует тестовые данные"""
|
||
records = [(f"User_{i:05d}", f"123-456-{i%10000:04d}") for i in range(n)]
|
||
random.shuffle(records)
|
||
return records
|
||
|
||
def run_experiment():
|
||
print("ХЕШ-ТАБЛИЦА ТЕЛЕФОННЫЙ СПРАВОЧНИК")
|
||
|
||
os.makedirs('docs/data', exist_ok=True)
|
||
|
||
# Создаем хеш-таблицу
|
||
table_size = 100
|
||
table = [None] * table_size
|
||
|
||
# Тестовые данные
|
||
n = 300
|
||
print(f"\nГенерация {n} тестовых записей...")
|
||
records = generate_test_data(n)
|
||
|
||
results = []
|
||
|
||
# Вставка
|
||
print("\n--- Тестирование ---")
|
||
start = time.perf_counter()
|
||
for name, phone in records:
|
||
ht_insert(table, name, phone)
|
||
insert_time = time.perf_counter() - start
|
||
print(f"Вставка: {insert_time:.4f} сек")
|
||
|
||
# Поиск
|
||
names_to_find = [records[i][0] for i in range(50)]
|
||
start = time.perf_counter()
|
||
for name in names_to_find:
|
||
ht_find(table, name)
|
||
find_time = time.perf_counter() - start
|
||
print(f"Поиск 50 записей: {find_time:.4f} сек")
|
||
|
||
# Удаление
|
||
names_to_delete = names_to_find[:25]
|
||
start = time.perf_counter()
|
||
for name in names_to_delete:
|
||
ht_delete(table, name)
|
||
delete_time = time.perf_counter() - start
|
||
print(f"Удаление 25 записей: {delete_time:.4f} сек")
|
||
|
||
results.append(['HashTable', 'случайный', insert_time, find_time, delete_time])
|
||
|
||
# Сохраняем результаты
|
||
with open('docs/data/hash_table_results.csv', 'w', newline='', encoding='utf-8') as f:
|
||
writer = csv.writer(f)
|
||
writer.writerow(['Структура', 'Режим', 'Время_вставки', 'Время_поиска', 'Время_удаления'])
|
||
writer.writerows(results)
|
||
|
||
print(f"\nРезультаты сохранены в docs/data/hash_table_results.csv")
|
||
|
||
if __name__ == "__main__":
|
||
run_experiment() |