Выбор ответа Senior Коллекции обновлено
Почему dict иногда тормозит на вставке
Вопрос
Почему отдельная вставка в большой dict иногда занимает заметно больше времени, чем обычно?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Таблица изредка перестраивается в большую: O(n), но амортизированно O(1). Хеш-таблица держит запас свободных слотов.
Варианты ответа
- Python пересортировывает ключи после каждой вставки
- Таблица изредка перестраивается в большую: O(n), но амортизированно O(1)правильный ответ
- Каждая вставка проверяет все ключи на равенство через
== - Сборщик мусора блокирует словарь на время своего прохода
Разбор
Хеш-таблица держит запас свободных слотов. Когда заполнение превышает порог, CPython выделяет таблицу большего размера и перераспределяет записи. Эта операция дорогая, но удвоение размера делает её редкой, и в среднем вставка остаётся O(1). Для задач с жёсткими требованиями к задержке иногда заранее создают словарь нужного размера другими способами. Сортировки и полного перебора ключей нет.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.