Есть список из 100 000 заблокированных user_id в переменной banned. Для каждого из миллиона событий нужно проверить, заблокирован ли пользователь. Как ускорить проверку?
AПреобразовать
banned в tuple — проверка in у кортежей быстрее, чем у списковBОставить
list и использовать bisect — бинарный поиск быстрее полного перебораCПреобразовать
banned в set — проверка in у множества работает за O(1)DОтсортировать
list — тогда in автоматически использует бинарный поискПравильный ответ. Проверка
x in set работает за O(1) в среднем, а x in list — за O(n). Для массовых проверок множество значительно быстрее.Разбор
Список проверяет принадлежность последовательным перебором элементов — O(n). Множество использует хеш-таблицу, поэтому проверка x in s занимает O(1) в среднем. При 100 000 элементах и миллионе проверок разница огромна. Сортировка списка не помогает: оператор in у list не использует бинарный поиск — он всегда делает линейный перебор.
Проверь себя · 1/3разбор после ответа
Даны два словаря
d1 = {'a': 1, 'b': 2} и d2 = {'b': 3, 'c': 4}. Что вернёт выражение d1 | d2 в Python 3.9+?Ещё вопросы по теме «Коллекции и структуры данных»
- Есть список событий `events = ["click"]`. Список `events` используется в нескольких местах по ссылке, поэтому важно изменить именно тот же объект (не создавать новый). Нужно добавить элементы из `new_events = ["view", "purchase"]`, чтобы итог был плоским. Какой вариант корректен?
- Есть словарь `d = {"country": "RU"}`. Нужно получить значение по ключу `"city"`, но если ключа нет — вернуть строку `"unknown"` без исключения. Что правильно?
- В логах есть список `user_ids` с повторениями. Как получить количество уникальных пользователей?
- Что произойдёт при выполнении кода `t = (1, 2); t[0] = 9`?
- Дан список `nums = [10, 20, 30, 40]`. Чему равен результат выражения `nums[1:3]`?
- Все вопросы по «Коллекции и структуры данных» →