Это Python такой тормоз или я?

Пролог

Ускоряем Python-код

Этот небольшой пост хочу посвятить оптимизации скорости выполнения кода на Python. Зачастую говорят, что Python - большой тормоз. При этом представляют куски кода, мол, вот, - попробуй такое ускорить. Да, действительно, некоторый код нельзя ускорить, потому что... потому что гладиолус. Но в огромном количестве случаев случается так, что тормоза программы вовсе не из-за языка, а... правильно, из-за разработчика. И вся проблема кроется в реализации алгоритма. Хочу показать небольшой пример оптимизации небольшой математической задачки. Итак, начнем. Задачка очень простая, взятая из projecteuler.net. 

Постановка задачи

Найти самый большой палиндром, который является произведением двух трехзначных чисел.

Решение в лоб

Итак, не вдаваясь в исследование математических свойств палиндромов, выполним решение задачки в лоб. Алгоритм примерно такой:

1. Цикл по числам от 100 до 999.
2. Внутренний цикл по числам от 100 до 999.
3. Если произведение переменных итерации внешнего и внутреннего цикла - палиндром и он больше предыдущего найденного - запоминаем его.
4. Получаем резульат.

Еще раз напомню, что основная задача здесь - написать код, а потом пытаться его оптимизировать, то есть не придумывать другой более быстрый алгоритм, а оптимизировать уже реализованный.

Итак, сделаем программу (Python 3.1)

from timeit import timeit

def is_palindrome(number):
    return str(number) == str(number)[::-1]

MIN = 100
MAX = 1000

def largest():
    max_number = 0
    for i in range(MIN, MAX):
        for j in range(MIN, MAX):
            if is_palindrome(i*j) and i*j > max_number:
                max_number = i*j
    return max_number

print (timeit('largest()', 'from __main__ import largest', number = 1))
print(largest())

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


Результат: 906609
Самое быстрое время выполнения: 1.6514 секунд.

Оптимизация № 1: очевидная.

Итак, мы видим здесь одно очевидное улучшение, которое можно выполнить. У нас операция умножения выполняется три раза. Сделаем так, чтобы выполнялась 1 раз (дальше буду приводить только код функции largest, чтобы не засорять текст):

def largest():
    max_number = 0
    for i in range(MIN, MAX):
        for j in range(MIN, MAX):
            product = i * j
            if is_palindrome(product) and product > max_number:
                max_number = product
    return max_number

Результат: 906609

Самое быстрое время выполнения: 1.5932 секунд

Прирост: 3.65%

Немного, но, тем не менее, код немножко ускорился.

Оптимизация №2: это просто интересно

Есть такой момент, что иногда очень часто вызываемые встроенные функциям удобно присваивать псевдонимы в локальном пространстве функции (спасибо semargl89). Таким образом интерпретатор не будет каждый раз при вызове функции искать указатель на нее. В данном случае, такая функция - str. Добавим следующую строчку перед функцией is_palindrom, и изменим соответственно саму функцию is_palindrom:

lstr = str
def is_palindrome(number):
    return lstr(number) == lstr(number)[::-1]

Результат: 906609

Самое быстрое время выполнения: 1.5514 секунд

Прирост (от первого варианта): 6,44%

Еще немножко ускорили.

Оптимизация №3: веселые условия

Итак, смотрим дальше, что же тут можно еще сделать. Цикли мы никак не изменим. А вот количество вызовов злосчастной is_palindrom можно сократить. А это, по большому счету, сама затратная функция, ведь здесь выполняется преобразование чисел, реверсинг строки, а потом еще и сравнение. Не секрет, что Python обладает сокращенной моделью вычисления условий. То есть, если на некотором этапе условной конструкции уже можно дать ответ, остальную часть конструкции он выполнять не будет. Вот новый код:

def largest():
    max_number = 0
    for i in range(MIN, MAX):
        for j in range(MIN, MAX):
            product = i * j
            if product > max_number and is_palindrome(product) :
                max_number = product
    return max_number

Как видите, все, что мы сделали - поменяли местами операнды оператора and: первым теперь идет условие product > max_number. Таким образом, каждый раз, когда произведение не больше уже найденного - мы не проверяем, является ли оно палиндромом. А результаты на самом то деле поражают:

Результат: 906609

Самое быстрое время выполнения: 0.2731 секунд

Прирост (от первого варианта): 604,69%

Это ж уже почти в семь раз! Что ж, идем дальше.

Оптимизация №4: выходит из предыдущей

Итак, в связи с таким поворотом событий, логически предположить, что чем раньше мы находим большие палиндромы, тем меньше раз вызывается is_palinfrom, что нам только на руку. Теперь есть смысл изменить циклы. Сделаем их не возрастающими, а совсем наоборот. Итак, новый код:

def largest():
    max_number = 0
    for i in range(MAX-1, MIN-1, -1):
        for j in range(MAX-1, MIN-1, -1):
            product = i * j
            if product > max_number and is_palindrome(product) :
                max_number = product
    return max_number

Результат: 906609

Самое быстрое время выполнения: 0.1925 секунд

Прирост (от первого варианта): 857,87%

И еще одно существенное ускорение. Наш код уже быстрее примерно в восемь с половиной раз!

Оптимизация №5: не надо делать все по 2 раза

Просмотрев цикл, мы заметим, что все умножения выполняются по два раза, то есть, кроме i * j выполняется еще и j * i. Давайте исключать такие нехорошие вещи:

def largest():
    max_number = 0
    for i in range(MAX-1, MIN-1, -1):
        for j in range(MAX-1, i - 1, -1):
            product = i * j
            if product > max_number and is_palindrome(product) :
                max_number = product
    return max_number

Итак, мы сделали внутренний цикл поменьше, при этом даже ничего не поломали.

Результат: 906609

Самое быстрое время выполнения: 0.0938 секунд

Прирост (от первого варианта): 1760,55%

Ну, думаю, хватит

Итак, проведя несколько минут медитации над кодом, можно добиться ускорения примерно в 20 раз. Не так уж плохо. Мораль сей басни такова: "перед тем как грешить на Python, - тщательно проверяйте свой код".