Где быстрее поиск в списке или множестве?

Анализ производительности поиска

Множество (set) быстрее, чем список (list) — это золотое правило Python.

Временная сложность

• Зависит от позиции для list

Почему множество быстрее?

Множество использует хеш-таблицу — элемент кодируется в число (хеш), затем ищется в таблице за O(1). Список просто проходит по всем элементам слева направо.

Практический пример

import time

data = list(range(1_000_000))
data_set = set(data)

start = time.perf_counter()
for _ in range(100_000):
    999_999 in data
list_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(100_000):
    999_999 in data_set
set_time = time.perf_counter() - start

print(f'List: {list_time:.3f}s')
print(f'Set: {set_time:.3f}s')
print(f'Множество быстрее в {list_time / set_time:.0f}x раз!')

Множество быстрее в 500-1000 раз.

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

Используй set если:

• Нужна проверка принадлежности (in, not in)
• Нужны операции с множествами (объединение, пересечение)
• Порядок не важен
• Элементы уникальны

Используй list если:

• Важен порядок элементов
• Нужны индексы
• Могут быть дубликаты
• Нужны срезы

Нюанс с хешированием

Элементы множества должны быть хешируемы. Работает с int, str, tuple. Не работает со списками, словарями.

valid_set = {1, 'hello', (1, 2)}
# invalid_set = {1, 'hello', [1, 2]}  # TypeError

Вывод

Для проверки наличия элемента (in) множество дает на порядки лучшую производительность. Это критично при частых проверках на больших данных.