Проверка вхождения: list против set на большом наборе
Есть два контейнера с одинаковым содержимым — 100 000 строк:
banned_list = [...] # list из 100000 строк
banned_set = set(banned_list)
Для каждого из миллиона входящих логинов выполняется проверка login in banned_list либо login in banned_set. Как соотносятся средние стоимости одной проверки?
- Обе O(1): оператор `in` реализован одинаково для любых контейнеров
- Список O(1), множество O(log n): множество хранит элементы в отсортированном виде
- Список O(n), множество O(1) в среднем: множество считает хеш и идёт сразу в нужную корзину
- Список O(log n), множество O(1): список внутри использует двоичный поиск