forked from UNN/2026-rff_mp
122 lines
3.8 KiB
Python
122 lines
3.8 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
|
||
|
||
current = head
|
||
prev = None
|
||
|
||
while current:
|
||
if current['name'] == name:
|
||
current['phone'] = phone
|
||
return head
|
||
prev = current
|
||
current = current['next']
|
||
|
||
prev['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 ll_list_all(head):
|
||
"""Собирает все записи"""
|
||
records = []
|
||
current = head
|
||
while current:
|
||
records.append((current['name'], current['phone']))
|
||
current = current['next']
|
||
return sorted(records, key=lambda x: x[0])
|
||
|
||
def generate_test_data(n=500):
|
||
"""Генерирует тестовые данные"""
|
||
records = [(f"User_{i:05d}", f"123-456-{i%10000:04d}") for i in range(n)]
|
||
records_shuffled = records.copy()
|
||
random.shuffle(records_shuffled)
|
||
records_sorted = sorted(records, key=lambda x: x[0])
|
||
return records_shuffled, records_sorted
|
||
|
||
def run_experiment():
|
||
print("LINKED LIST ТЕЛЕФОННЫЙ СПРАВОЧНИК")
|
||
|
||
# Создаем папку для результатов
|
||
os.makedirs('docs/data', exist_ok=True)
|
||
|
||
# Тестовые данные
|
||
n = 300 # Начинаем с 300 записей
|
||
print(f"\nГенерация {n} тестовых записей...")
|
||
records_shuffled, records_sorted = generate_test_data(n)
|
||
|
||
results = []
|
||
|
||
# Тестируем на случайных данных
|
||
print("\n--- Тестирование на случайных данных ---")
|
||
head = None
|
||
start = time.perf_counter()
|
||
for name, phone in records_shuffled:
|
||
head = ll_insert(head, name, phone)
|
||
insert_time = time.perf_counter() - start
|
||
print(f"Вставка: {insert_time:.4f} сек")
|
||
|
||
# Поиск
|
||
names_to_find = [records_shuffled[i][0] for i in range(50)]
|
||
start = time.perf_counter()
|
||
for name in names_to_find:
|
||
ll_find(head, 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:
|
||
head = ll_delete(head, name)
|
||
delete_time = time.perf_counter() - start
|
||
print(f"Удаление 25 записей: {delete_time:.4f} сек")
|
||
|
||
results.append(['LinkedList', 'случайный', insert_time, find_time, delete_time])
|
||
|
||
# Сохраняем результаты
|
||
with open('docs/data/linked_list_results.csv', 'w', newline='', encoding='utf-8') as f:
|
||
writer = csv.writer(f)
|
||
writer.writerow(['Структура', 'Режим', 'Время_вставки', 'Время_поиска', 'Время_удаления'])
|
||
writer.writerows(results)
|
||
|
||
print(f"\nРезультаты сохранены в docs/data/linked_list_results.csv")
|
||
|
||
if __name__ == "__main__":
|
||
run_experiment() |