Це 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_palindrom, що нам тільки в плюс. Тепер є зміст змінити цикли. Зробимо їх не зростаючими, а навпаки. Отже, новий код:

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: не варто робити все двічі

Переглянувши цикл, помічаємо, що всі множення виконуються двічі, тобто, окрім 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, - ретельно перевіряйте свій код. В дуже багатьох випадках ви здатні отримати прийнятні показники ефективності".