Чем быстрее поиск в словаре или в списке и почему
Что проверяют
Понимаете ли вы разницу между доступом по хешу и линейным перебором и умеете ли выбрать структуру под задачу. Для data-ml это не теория: проверка if x in list внутри цикла по датасету превращает минуту в час, и в чужих ноутбуках такое встречается постоянно.
Как отвечать
Сначала цифры, потом почему. Поиск по ключу в словаре в среднем O(1): ключ хешируется, хеш указывает на ячейку, сравнивается один элемент или несколько. Поиск значения в списке это O(n), элементы лежат подряд, и чтобы узнать, есть ли нужный, приходится пройти по всем.
Дальше то, что отличает заученный ответ от рабочего:
- O(1) у словаря средняя и амортизированная. При плохом хеше всё вырождается в линейный перебор, а вставка иногда стоит дорого, потому что при заполнении таблица перестраивается целиком.
- Ключ обязан быть хешируемым и неизменяемым: список или массив ключом не станет, нужен кортеж.
- Если нужна только проверка принадлежности, берут
set, а не словарь: та же сложность, меньше памяти. - Список проигрывает не всегда. Доступ по индексу у него тоже O(1), он компактнее в памяти, и на десятке элементов перебор обгонит вычисление хеша.
- Отсортированный список ищется двоичным поиском за O(log n) через
bisect, это компромисс, когда важен порядок.
Рабочий приём, который стоит проговорить вслух:
ids = set(ids_list) # построение O(n), проверка O(1)
rows = [r for r in data if r.key in ids]В pandas тот же принцип: фильтр по идентификаторам делают через isin, соединение таблиц через merge, а не циклом с поиском по колонке.
Где спотыкаются
Говорят «словарь всегда быстрее». Быстрее по ключу. Поиск по значению в словаре это тот же полный перебор, только с накладными расходами сверху.
Второе: смешивают поиск и обход. Пройти все элементы в обоих случаях O(n), выигрыш словаря именно в точечном доступе, и ради одной единственной проверки строить его не окупится.
Третье: забывают про память. Хеш-таблица держит запас пустых ячеек, поэтому словарь на миллионы ключей съедает кратно больше списка, и на больших выборках упираются в память раньше, чем в скорость.