← Все вопросы
Что быстрее для проверки наличия — поиск в списке или в множестве?
21
Часто проверяю if x in collection. Заметил, что советуют для этого множество, а не список. Насколько реально разница большая и почему?
3 ответа
30
✓ Принятый ответ — помог автору
Разница огромная на больших данных. Поиск x in список — это O(n): Python идёт по элементам подряд, пока не найдёт. Поиск x in множестве (или среди ключей словаря) — в среднем O(1): он считает хеш x и прыгает сразу в нужную ячейку, не перебирая всё.
big_list = list(range(1_000_000))
big_set = set(big_list)
999_999 in big_list # медленно: проходит почти весь список
999_999 in big_set # мгновенно: один хеш-доступ
Практическое правило: если структура нужна в основном для проверок «есть/нет» и порядок/дубли не важны — храни в set. На паре десятков элементов разницы не почувствуешь, но на тысячах и больше — это разница между миллисекундами и секундами.
Олег Захаров переписал проверку с list на set, цикл стал летать 🔥 · 20 месяцев назад
10
В множестве — O(1) против O(n) у списка. Для частых проверок in всегда set.
4
В множестве.
Ваш ответ
Войдите, чтобы ответить на вопрос.
