import time import random import csv def record(n, mode="random"): records = [(f"user_{i:05d}", f"123-456-{i:04d}") for i in range(n)] if mode == "random": random.shuffle(records) return records N = 1000 records_shuffled = record(N, "random") records_sorted = record(N, "sorted") all_results = [] def time_1(func, repeat=5): times = [] for _ in range(repeat): start = time.perf_counter() func() end = time.perf_counter() times.append(end - start) return sum(times) / repeat, times # 1 def ll_insert(head, name, phone): if head and head['name'] == name: head['phone'] = phone return head current = head while current and current['next']: if current['next']['name'] == name: current['next']['phone'] = phone return head current = current['next'] new_node = {'name': name, 'phone': phone, 'next': None} if head is None: return new_node current = head while current['next']: 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 ll_list_all(head): records = [] current = head while current: records.append((current['name'], current['phone'])) current = current['next'] records.sort(key=lambda x: x[0]) return records # 2 def hash_func(name, size): return sum(ord(ch) for ch in name) % size def ht_create(size=200): return [None] * size def ht_insert(table, name, phone): idx = hash_func(name, len(table)) table[idx] = ll_insert(table[idx], name, phone) def ht_find(table, name): idx = hash_func(name, len(table)) return ll_find(table[idx], name) def ht_delete(table, name): idx = hash_func(name, len(table)) table[idx] = ll_delete(table[idx], name) def ht_list_all(table): records = [] for bucket in table: current = bucket while current: records.append((current['name'], current['phone'])) current = current['next'] records.sort(key=lambda x: x[0]) return records # 3 def bst_insert(root, name, phone): if root is None: return {'name': name, 'phone': phone, 'left': None, 'right': None} if name < root['name']: root['left'] = bst_insert(root['left'], name, phone) elif name > root['name']: root['right'] = bst_insert(root['right'], name, phone) else: root['phone'] = phone return root def bst_find(root, name): if root is None: return None if name == root['name']: return root['phone'] elif name < root['name']: return bst_find(root['left'], name) else: return bst_find(root['right'], name) def _find_min(node): while node['left']: node = node['left'] return node def bst_delete(root, name): if root is None: return None if name < root['name']: root['left'] = bst_delete(root['left'], name) elif name > root['name']: root['right'] = bst_delete(root['right'], name) else: if root['left'] is None: return root['right'] if root['right'] is None: return root['left'] min_node = _find_min(root['right']) root['name'] = min_node['name'] root['phone'] = min_node['phone'] root['right'] = bst_delete(root['right'], min_node['name']) return root def bst_list_all(root): result = [] if root: result.extend(bst_list_all(root['left'])) result.append((root['name'], root['phone'])) result.extend(bst_list_all(root['right'])) return result all_names = [name for name, _ in records_shuffled] existing = random.sample(all_names, 100) none_names = [f"None_{i}" for i in range(10)] find_names = existing + none_names random.shuffle(find_names) delete_names = random.sample(all_names, 50) for struct_name, struct_funcs in [ ("LinkedList", (ll_insert, ll_find, ll_delete, ll_list_all)), ("HashTable", (ht_insert, ht_find, ht_delete, ht_list_all)), ("BST", (bst_insert, bst_find, bst_delete, bst_list_all)) ]: print(f"\n{struct_name}") insert, find, delete, list_all = struct_funcs for mode, records in [("случайный", records_shuffled), ("отсортированный", records_sorted)]: def insert_func(data=records): if struct_name == "LinkedList": obj = None for name, phone in data: obj = insert(obj, name, phone) elif struct_name == "HashTable": obj = ht_create() for name, phone in data: insert(obj, name, phone) else: # BST obj = None for name, phone in data: obj = insert(obj, name, phone) avg, times = time_1(insert_func) print(f" Вставка ({mode}): {avg:.6f}") for t in times: all_results.append([struct_name, mode, "вставка", t]) if struct_name == "LinkedList": obj = None for name, phone in records_shuffled: obj = insert(obj, name, phone) elif struct_name == "HashTable": obj = ht_create() for name, phone in records_shuffled: insert(obj, name, phone) else: # BST obj = None for name, phone in records_shuffled: obj = insert(obj, name, phone) def find_func(): for name in find_names: find(obj, name) avg, times = time_1(find_func) print(f" Поиск 110 записей: {avg:.6f}") for t in times: all_results.append([struct_name, "случайный", "поиск", t]) def delete_func(): if struct_name == "LinkedList": temp = None for n, p in records_shuffled: temp = insert(temp, n, p) for name in delete_names: temp = delete(temp, name) elif struct_name == "HashTable": temp = ht_create() for n, p in records_shuffled: insert(temp, n, p) for name in delete_names: delete(temp, name) else: temp = None for n, p in records_shuffled: temp = insert(temp, n, p) for name in delete_names: temp = delete(temp, name) avg, times = time_1(delete_func) print(f" Удаление 50 записей: {avg:.6f}") for t in times: all_results.append([struct_name, "случайный", "удаление", t]) with open("experiment_results.csv", "w", newline="", encoding="utf-8") as f: writer = csv.writer(f) writer.writerow(["Structure", "Mode", "Operation", "Time_sec"]) writer.writerows(all_results)