Выбор ответа Junior Коллекции спрашивают часто обновлено
Проверка x in для list и set
Вопрос
Код проверяет 10 000 id из списка ids на вхождение в allowed, где тоже 10 000 элементов. Какое изменение ускорит его сильнее всего?
allowed = load_allowed() # list
result = [i for i in ids if i in allowed]
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Превратить allowed в set один раз. i in list это линейный поиск, и весь цикл O(n·m), около 10⁸ сравнений. set ищет за O(1) в среднем, итог O(n + m).
Варианты ответа
- Отсортировать
allowedсписком - Заменить
forна list comprehension сfilter - Использовать
allowed.index(i)вместо оператораin - Превратить
allowedвsetодин разправильный ответ
Разбор
i in list это линейный поиск, и весь цикл O(n·m), около 10⁸ сравнений. set ищет за O(1) в среднем, итог O(n + m). Comprehension ускоряет лишь накладные расходы интерпретатора. Сортировка без бинарного поиска ничего не даёт, а in по отсортированному списку остаётся линейным. index тоже линейный и вдобавок кидает ValueError.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.