Эффективное использование any и all в Python

Вот вам задача: надо проверить, входит ли число 200 миллионов в диапазон от 0 до 1 миллиарда. Знаю, что на Python её решение выглядит до крайности примитивно — достаточно воспользоваться функцией any и списковым включением:

def find_200_million() -> bool:
    return any([number == 200_000_000 for number in range(1_000_000_000)])

Правда, работает это всё не так уж и быстро. Всё же, речь идёт о миллиарде чисел… Программа просто «подвисает» на то время, что нужно для её выполнения. В моём случае это «подвисание» растянулось на 42 секунды.

Почему? Можно ли обойтись без «подвисания»?

Для начала разберёмся с тем, что тут происходит, а потом подумаем о том, можно ли как-то ускорить эту программу.

Когда мы вызываем функцию — происходит две вещи:

1. Запускается механизм спискового включения, генерирующий список из примерно 1 миллиарда логических значений, указывающих на то, равно ли каждое из чисел 200 миллионам.

2. Затем запускается функция any. Она перебирает этот список, проверяя, равен ли какой-нибудь из его элементов значению True. А как только это значение будет обнаружено, функция возвращает результаты своей работы.

Получается, что тут имеется два цикла, в ходе выполнения которых происходит 1,2 миллиарда итераций! Функция any доберётся до 200-миллионного значения достаточно быстро. А вот списковое включение, с другой стороны, создаёт «тяжёлый» список из 1 миллиарда логических значений. Это занимает много времени. Когда я запустил эту программу, формирование списка заняло примерно 40 секунд. А функция any нашла в нём первое значение True всего за 2 секунды.

Теперь, когда мы выяснили, что тут происходит — зададимся вопросом о том, можно ли улучшить производительность программы. Главные проблемы здесь — необходимость работы с огромным количеством значений, и то, что создание списка занимает определённое время. А значит — если мы сократим количество значений, добавляемых в список, это должно привести к тому, что программа будет работать быстрее.

Более эффективная реализация механизма спискового включения

Наш список можно сделать меньше, пользуясь фильтрующей конструкцией if спискового включения. Это приведёт к генерированию списка, содержащего только значения True:

def find_200_million() -> bool:
    return any([True for number in range(1_000_000_000) if number == 200_000_000])

Теперь мы генерируем список, который содержит лишь один элемент — для каждого числа, равного 200 миллионам. В нашем случае это значит, что получится список, содержащий лишь один элемент. Тестируя это решение, я обнаружил, что список формируется за 33 секунды — примерно на 7 секунд быстрее. А функция any завершает работу почти мгновенно, так как ей надо проверить список, в котором содержится лишь один элемент. Поэтому теперь вместо 42 секунд на решение задачи уходит лишь 33 секунды!

Можно ли это ещё как-нибудь ускорить?

33 секунды — это всё ещё серьёзное время. Как его улучшить? Сейчас механизм спискового включения перебирает 1 миллиард элементов, каждый из них проверяет, а потом выдаёт список. Что если вместо этого использовать генераторное выражение? Принесёт ли это пользу?

def find_200_million() -> bool:
    return any(True for number in range(1_000_000_000) if number == 200_000_000)

Этот вариант программы выдаёт результат всего за 6 секунд!

Почему генераторное выражение оказывается таким быстрым?

Генераторные выражения не быстрее списковых включений. Единственное их преимущество заключается в том, что они создают следующий элемент списка по запросу. А списковые включения заранее генерируют весь список. При использовании any ценность генераторных выражений в том, что они останавливаются при обнаружении совпадения.

Пошагово разберём вышеприведённый код для того чтобы лучше понять то, как он работает:

1. Создаётся генератор, который идёт по значениям от 0 до 999,999,999 и выдаёт True для каждого значения, равного 200 миллионам.

2. Функция any получает генератор и запрашивает из него первое значение.

3. Генератор начинает проходиться по числам до тех пор, пока не выдаст то, которое соответствует условию равенства 200 миллионам. После этого он выдаёт True. Это значение получает any.

4. Когда функция any получает True, она завершает работу, ничего больше не проверяя.

Получается, что эта программа быстрее из-за того, что она не перебирает числа диапазона, превышающие 200 миллионов!

Если же, с другой стороны, мы искали бы последнее число в диапазоне (999,999,999), скорость нашего решения была бы практически такой же, как при использовании спискового включения. Новое решение быстрее старого только в том случае, когда первое значение, удовлетворяющее условию, не находится в конце пространства поиска.

Хорошо, а что если бы мы не воспользовались фильтрацией с помощью if?

А тут появляется такой вопрос: что если бы мы построили условие с использованием получаемого значения и не пользовались бы фильтром if в генераторном выражении?

def find_200_million() -> bool:
    return any(number == 200_000_000 for number in range(1_000_000_000))

Этот вариант решения задачи завершает работу примерно за 9 секунд. То есть — он примерно на 3 секунды медленнее, чем при использовании фильтра if. Это так из-за того, что теперь генератор получает False для чисел от 0 до 199,999,999, а any, до завершения работы, приходится делать 200 миллионов проверок. А это на 199,999,999 больше проверок, чем тогда, когда мы пользовались фильтрацией с помощью if.

Итоги

Использование фильтрации, основанной на if, сужает пространство поиска, которое нужно просматривать any. При правильном использовании фильтрации функции any приходится проверить лишь первое полученное значение. Кроме того, в ситуациях, подобной нашей, рекомендуется пользоваться генераторными выражениями. Они не всегда быстрее списковых включений, но они останавливаются сразу после того, как any завершает работу. Это часто приводит к экономии времени и всегда позволяет экономить память!

Так, погодите, а что там с функцией all?

Применимо ли это всё к функции all? Можно ли ускорить и её? Да! Это возможно!

Функция any интересуется значениями True и возвращает True, находя первое из них, или False — если не нашла ни одного. А функция all действует с точностью до наоборот. Она ищет значения False и возвращает False, когда найдёт первое такое значение, или возвращает True, если ни одного значения False не нашла. Поэтому те же подходы к оптимизации кода можно применить и к all, перенастроив if на поиск состояния отказа и выдавая False, а не True!

def all_not_equal_to_200_million() -> bool:
    return all(False for number in range(1_000_000_000) if number == 200_000_000)

В этом коде False выдаётся только в том случае, если будет найдено число, удовлетворяющее состоянию отказа, соответствующего равенству значения 200 миллионам. Если ни одно число не равно 200 миллионам — ничего не будет выдано и all вернёт True, так как генератор окажется пустым.

В итоге оказывается, что выжать максимальную производительность из any и all можно, пользуясь генераторными выражениями и фильтрами, основанными на if.