---

import sqlite3
import time
import random

# Параметры
NUM_NAMES = 1000          # количество разных имён
NUM_CITIES = 1000         # количество разных городов
TOTAL_RECORDS = 1_000_000 # общее число записей (можно менять)
SEED = 42                 # фиксируем случайность для воспроизводимости

random.seed(SEED)

# Генерируем списки имён и городов вида name1, name2, ..., city1, city2, ...
names = [f"name{i}" for i in range(1, NUM_NAMES + 1)]
cities = [f"city{i}" for i in range(1, NUM_CITIES + 1)]

# --- 1. Создаём одинаковые данные для списка и БД ---------------------------
print(f"Генерация {TOTAL_RECORDS:,} записей...")
t_gen_start = time.perf_counter()
data = [(random.choice(names), random.choice(cities)) for _ in range(TOTAL_RECORDS)]
t_gen = time.perf_counter() - t_gen_start
print(f"Данные сгенерированы за {t_gen:.2f} сек.\n")

# Выбираем, кого будем искать (для примера – пара из середины списков)
search_name = "name500"
search_city = "city500"


# --- 2. Поиск в списке -------------------------------------------------------
def count_in_list(data, name, city):
    """Подсчёт строк в списке методом линейного перебора."""
    count = 0
    for n, c in data:
        if n == name and c == city:
            count += 1
    return count

print(f"Поиск в списке: name={search_name}, city={search_city}")
t0 = time.perf_counter()
cnt_list = count_in_list(data, search_name, search_city)
t_list = time.perf_counter() - t0
print(f"Найдено: {cnt_list}, время: {t_list:.6f} сек.\n")


# --- 3. SQLite (в памяти) ----------------------------------------------------
# in-memory база работает быстро, исключая влияние дисковой подсистемы
conn = sqlite3.connect(":memory:")
cur = conn.cursor()

# Создаём таблицу БЕЗ индексов
cur.execute("CREATE TABLE people (name TEXT, city TEXT)")

# Массовая вставка в одной транзакции – самый быстрый способ
print("Наполнение БД (без индексов)...")
t_insert_start = time.perf_counter()
cur.execute("BEGIN TRANSACTION")
cur.executemany("INSERT INTO people VALUES (?, ?)", data)
conn.commit()
t_insert = time.perf_counter() - t_insert_start
print(f"Вставка выполнена за {t_insert:.2f} сек.\n")

# Поиск в БД без индекса (полное сканирование таблицы)
print(f"Поиск в БД БЕЗ индекса: name={search_name}, city={search_city}")
t0 = time.perf_counter()
cur.execute("SELECT COUNT(*) FROM people WHERE name=? AND city=?",
            (search_name, search_city))
cnt_db_no_idx = cur.fetchone()[0]
t_db_no_idx = time.perf_counter() - t0
print(f"Найдено: {cnt_db_no_idx}, время: {t_db_no_idx:.6f} сек.\n")

# --- 4. Создаём индекс и повторяем поиск ------------------------------------
print("Создание индекса (name, city)...")
t_idx_start = time.perf_counter()
cur.execute("CREATE INDEX idx_name_city ON people (name, city)")
t_idx = time.perf_counter() - t_idx_start
print(f"Индекс создан за {t_idx:.3f} сек.\n")

# Поиск с индексом
print(f"Поиск в БД С индексом: name={search_name}, city={search_city}")
t0 = time.perf_counter()
cur.execute("SELECT COUNT(*) FROM people WHERE name=? AND city=?",
            (search_name, search_city))
cnt_db_idx = cur.fetchone()[0]
t_db_idx = time.perf_counter() - t0
print(f"Найдено: {cnt_db_idx}, время: {t_db_idx:.6f} сек.\n")

conn.close()

# --- 5. Итоговая таблица -----------------------------------------------------
print("=" * 60)
print(f"{'Метод':<30} {'Найдено':<10} {'Время, сек'}")
print("-" * 60)
print(f"{'Список (линейный перебор)':<30} {cnt_list:<10} {t_list:.6f}")
print(f"{'БД без индекса (full scan)':<30} {cnt_db_no_idx:<10} {t_db_no_idx:.6f}")
print(f"{'БД с индексом (B-tree)':<30} {cnt_db_idx:<10} {t_db_idx:.6f}")
print("=" * 60)