Есть list из 100 000 заблокированных идентификаторов пользователя в переменной banned. Для каждого из миллиона событий нужно проверить, заблокирован ли пользователь. Как ускорить проверку?

list проверяет принадлежность последовательным перебором элементов — O(n). set использует хеш-таблицу, поэтому проверка принадлежности занимает O(1) в среднем. При 100 000 элементах и миллионе проверок разница огромна. Сортировка list не помогает: оператор in у list не использует бинарный поиск, а всегда делает линейный перебор. У tuple логика та же, что и у list.