Какие структуры данных выберешь, если требуется быстрый поиск?

Выбор структур данных для быстрого поиска

Выбор структуры данных критически влияет на скорость поиска. Разные структуры обеспечивают разные временные сложности.

Временные сложности (Big O)

# Временная сложность операций
Structure          | Поиск    | Вставка  | Удаление
------------------|----------|----------|----------
Массив (list)      | O(n)     | O(n)     | O(n)
Отсорт. массив     | O(log n) | O(n)     | O(n)
Линк. список       | O(n)     | O(1)     | O(1)
Hash table (dict)  | O(1)*    | O(1)*    | O(1)*
Set                | O(1)*    | O(1)*    | O(1)*
Binary Search Tree | O(log n) | O(log n) | O(log n)
B-Tree             | O(log n) | O(log n) | O(log n)
Три (Trie)         | O(m)     | O(m)     | O(m)

* В среднем случае, при хорошем распределении хеша

1. Set для уникальных элементов

Когда использовать

• Проверка принадлежности (member of)
• Уникальные элементы
• Удаление дубликатов
• Множественные операции (union, intersection)

# O(1) в среднем случае
users = {"alice", "bob", "charlie"}

if "alice" in users:  # O(1) очень быстро
    print("Пользователь найден")

# Удалить дубликаты из списка
original = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(original))  # [1, 2, 3, 4]

# Множественные операции
set_a = {1, 2, 3}
set_b = {2, 3, 4}

intersection = set_a & set_b  # {2, 3} — общие элементы
union = set_a | set_b          # {1, 2, 3, 4} — все элементы
difference = set_a - set_b     # {1} — только в set_a

2. Dict для быстрого поиска по ключу

Когда использовать

• Поиск по уникальному идентификатору
• Кэширование значений
• Отображение ключ-значение

# O(1) в среднем случае
users = {
    1: "Alice",
    2: "Bob",
    3: "Charlie"
}

user = users[2]  # O(1) очень быстро

# Использовать как кэш
from functools import lru_cache

@lru_cache(maxsize=128)
def expensive_calculation(n):
    # Результаты кэшируются в dict
    return n ** 2

result = expensive_calculation(10)  # Вычисляется
result = expensive_calculation(10)  # Берётся из кэша O(1)

3. Binary Search Tree для отсортированного поиска

Когда использовать

• Нужно поддерживать отсортированный порядок
• Часто нужны операции: найти, найти меньше/больше
• Диапазонные запросы

from bintrees import BTree

# BST поддерживает порядок
tree = BTree()
for val in [5, 3, 7, 2, 4, 6, 8]:
    tree[val] = f"value_{val}"

# Поиск O(log n)
value = tree[5]  # O(log n)

# Найти первый элемент >= 5
for key in tree.keys_at(5, None):  # Все ключи от 5 и выше
    print(key)

# Диапазон (например, все числа от 3 до 7)
for key in tree.keys_at(3, 7):
    print(key)  # 3, 4, 5, 6, 7

4. Отсортированный список с bisect для двоичного поиска

Когда использовать

• Данные уже отсортированы
• Нужна вставка в отсортированном порядке
• Двоичный поиск в статических данных

import bisect

# Отсортированный список
scores = [10, 20, 30, 40, 50]

# Двоичный поиск O(log n)
index = bisect.bisect_left(scores, 30)  # Индекс где 30 находится
print(index)  # 2

if index < len(scores) and scores[index] == 30:
    print("Найдено")

# Найти позицию для вставки
insert_pos = bisect.bisect_right(scores, 25)
scores.insert(insert_pos, 25)  # O(n) для вставки!
print(scores)  # [10, 20, 25, 30, 40, 50]

# Диапазонный поиск
start = bisect.bisect_left(scores, 20)
end = bisect.bisect_right(scores, 40)
range_values = scores[start:end]  # O(log n) для поиска
print(range_values)  # [20, 25, 30, 40]

5. Trie (префиксное дерево) для строковых поисков

Когда использовать

• Автозаполнение
• Проверка существования слова
• Префиксные запросы
• Словари

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
    
    def search(self, word):
        """O(m) где m длина слова"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_word
    
    def starts_with(self, prefix):
        """Найти все слова с данным префиксом"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        return self._dfs(node, prefix)
    
    def _dfs(self, node, prefix):
        results = []
        if node.is_word:
            results.append(prefix)
        for char, child in node.children.items():
            results.extend(self._dfs(child, prefix + char))
        return results

# Использование
trie = Trie()
for word in ["apple", "app", "application", "apply"]:
    trie.insert(word)

print(trie.search("apple"))  # True O(5)
print(trie.starts_with("app"))  # [app, apple, application, apply]

6. Хеш-таблица с разрешением коллизий

Когда использовать

• Нужен O(1) поиск
• Хеширование пользовательских объектов
• Распределение нагрузки

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # Chaining
    
    def _hash(self, key):
        """Простая хеш-функция"""
        return hash(key) % self.size
    
    def insert(self, key, value):
        """O(1) в среднем"""
        index = self._hash(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))
    
    def search(self, key):
        """O(1) в среднем"""
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None
    
    def delete(self, key):
        """O(1) в среднем"""
        index = self._hash(key)
        self.table[index] = [(k, v) for k, v in self.table[index] if k != key]

hash_table = HashTable()
hash_table.insert("name", "Alice")
print(hash_table.search("name"))  # Alice O(1)

7. Index для базы данных

B+ Tree (используется в БД)

from sqlalchemy import Column, Integer, String, Index, create_engine
from sqlalchemy.orm import declarative_base

Base = declarative_base()

class User(Base):
    __tablename__ = "users"
    
    id = Column(Integer, primary_key=True)
    email = Column(String, unique=True)  # Автоматически индексируется
    name = Column(String)
    age = Column(Integer)
    
    # Явные индексы
    __table_args__ = (
        Index('idx_email', 'email'),           # O(log n) поиск
        Index('idx_name', 'name'),
        Index('idx_age_name', 'age', 'name'), # Составной индекс
    )

# Использование индекса в запросе
engine = create_engine("postgresql://localhost/db")

# Этот запрос использует индекс idx_email
user = session.query(User).filter(User.email == "alice@example.com").first()  # O(log n)

# Этот запрос НЕ использует индекс
users = session.query(User).filter(User.name.startswith("A")).all()  # O(n)

Рекомендации по выбору

# Задача: Быстро проверить наличие элемента
решение = SET
# items = {"apple", "banana", "cherry"}
# if "apple" in items:  # O(1)

# Задача: Быстро найти значение по ключу
решение = DICT
# users = {1: "Alice", 2: "Bob"}
# user = users[1]  # O(1)

# Задача: Найти элементы в диапазоне
решение = SORTED ARRAY с BISECT или B-TREE
# scores = [10, 20, 30, 40, 50]
# start = bisect.bisect_left(scores, 20)
# end = bisect.bisect_right(scores, 40)
# range = scores[start:end]  # O(log n)

# Задача: Автозаполнение по префиксу
решение = TRIE
# trie.starts_with("app")  # O(m) где m длина префикса

# Задача: Поиск в базе данных
решение = B+ TREE INDEX
# CREATE INDEX idx_email ON users(email);
# SELECT * FROM users WHERE email = 'alice@example.com';  # O(log n)

Итого

Для быстрого поиска выбери:

1. Set — проверка наличия, O(1)
2. Dict — поиск по ключу, O(1)
3. Binary Search с bisect — в отсортированном массиве, O(log n)
4. B-Tree — упорядоченные данные с поддержкой диапазонов, O(log n)
5. Trie — префиксные запросы для строк, O(m)
6. Database Index — в production, B+ Tree индексы

Помни: нет одного правильного ответа, выбор зависит от требований!