Сообщить об ошибкеКороткий ответ
Проверка вхождения в list выполняется за O(n), потому что требует последовательного перебора, а в set или dict — в среднем за O(1) благодаря хеш-таблице, поэтому для больших коллекций set значительно быстрее.
Как это работает подробнее
list хранит элементы последовательно, и in сравнивает искомое значение с каждым элементом по очереди, пока не найдёт совпадение или не дойдёт до конца. set и dict используют хеш-таблицу: по хешу значения сразу вычисляется бакет, где оно должно лежать.
Пример кода
example.py
import timeit
big_list = list(range(100_000))
big_set = set(big_list)
t_list = timeit.timeit(lambda: 99_999 in big_list, number=1000)
t_set = timeit.timeit(lambda: 99_999 in big_set, number=1000)
print(t_list, t_set)
# t_list на несколько порядков больше t_set — наглядное подтверждение O(n) vs O(1)Что использовать на практике
- Практика. Если в коде есть цикл с проверкой
if x in big_list, суммарная сложность становится O(n*m), что на больших объёмах данных приводит к заметным замедлениям; замена list на set для таких проверок — одна из самых дешёвых оптимизаций.
Подводные камни
- Риск. Используют list для частых проверок вхождения просто потому, что порядок элементов кажется важным, не замечая, что для самой проверки порядок не нужен; путают сложность списка и множества, считая обе структуры одинаково быстрыми «потому что обе встроенные».