понедельник, 21 февраля 2011 г.

Это 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, - тщательно проверяйте свой код".

24 комментария:

  1. 5й пункт - это оптимизация алгоритма, а не кода. помойму

    ОтветитьУдалить
  2. По сути почти все - оптимизация (кроме 2 и 3). Программный код - это лишь форма представления алгоритма. Но основная идея не нарушена - полный перебор произведений с проверками (просто таким образом выкосили избыточность операций).

    ОтветитьУдалить
  3. Этот комментарий был удален автором.

    ОтветитьУдалить
  4. Лень проверять, но разве reversed не быстрее [::-1]?

    ОтветитьУдалить
  5. в 4-м пункт можно заменить
    if product > max_number and is_palindrome(product) :
    max_number = product

    на
    if is_palindrome(product) :
    return product

    ОтветитьУдалить
  6. @Amper
    reversed не быстрее. Попробовали бы сами (неужели так трудно код, хотя бы скопипастить :))

    @Zaglebelin
    Нельзя. Будет неверный результат.

    ОтветитьУдалить
  7. Следующие очевидные оптимизации -- преобразовывать в строку только один раз, не вызывать is_palindrome, а записать ее код непосредственно внутри цикла, и, раз функция вызываться не будет, локализовать str еще ближе, в локальном словаре сразу перед циклом. И, кстати, можно ведь записать генератор произведения двух переменным одним выражением, может быть, это будет быстрее.

    ОтветитьУдалить
  8. @Mikhail Edoshin
    Хотелось бы увидеть код таких оптимизаций от вас в сравнении с первоначальным вариантом.
    А то все я, да я ... :)

    ОтветитьУдалить
  9. Есть такой принцип: 20/80. 20% затрат дают 80% результата. Я это к тому, что ваш подход к оптимизации в корне неверен.

    Любая оптимизация скорости выполнения негативно отражается на читаемости кода. Поэтому нужно применить принцип 20/80 для того, чтобы сделав минимум изменений, добиться максимального прироста производительности. В идеале, применение ваших оптимизаций должно идти в обратном порядке.

    Практика показывает, что только профайлер и здравый смысл в силах указать на узкое место в программе. Ни в коем случае не нужно поддаваться соблазну делать оптимизации наподобие N2.

    Советую почитать книги Фаулера "Рефакторинг" и Макконелла "Совершенный код".

    ОтветитьУдалить
  10. Попробовал, но ускорение незначительное. Не при каждом прогоне и есть :) А один генератор по двум переменным оказывается медленнее, чем два цикла.

    Кстати, реально он находит 906609 вторым (993*913), после чего тупо гоняет цикл. Не могу отделаться от мысли, что можно как-то сразу выйти на него.

    И один пропуск заметил -- при перевороте границ нужно числа изменить, т. е. range(MAX-1, MIN-1) или, лучше, сами константы, а это нигде не обозначено.

    ОтветитьУдалить
  11. @Mikhail Edoshin
    >>> Не могу отделаться от мысли, что можно как-то сразу выйти на него.

    Зайдите на projecteuler.net - запостите результат, и вам откроются решения других. Там есть много описанных вариантов решения задачи. Но при таком брутфорсовском подходе не знаю, как еще сократить.

    >>> И один пропуск заметил -- при перевороте границ нужно числа изменить, т. е. range(MAX-1, MIN-1) или, лучше, сами константы, а это нигде не обозначено.

    Да, спасибо, поправлю.

    ОтветитьУдалить
  12. >>> Я это к тому, что ваш подход к оптимизации в корне неверен.

    Каюсь.

    >>> Советую почитать книги Фаулера "Рефакторинг"...

    Читаю :)

    Но это не цель написания статьи. Цель написания статьи не показать мего-классный супер метод оптимизации :), а скорее "наш ответ Чемберлену", то есть тем, кто тычет головой в код, который работает 20 секунд, говорит что питон тормоз, а потом еще пишет об этом на каждом углу, а ты смотришь, - а там можно сделать не 20, а 0.20 :)

    P.S.
    На самом деле немножко вдохновения получено от этого обсуждения:

    http://python.su/forum/viewtopic.php?id=10136

    ОтветитьУдалить
  13. Брутфорс быстрее уже не сделать - слишком уж простая штука is_palindrome.
    Все попытки, например, кеширования упираются в то, что кеширующая система работает медленней, чем кешируемая функция.

    Кстати, "патентованный" метод №2 выглядит несколько иначе. Ты просто переложил str из __builtins__ в globals. Круто, конечно - но разница небольшая. Нужно помещать в locals.

    Самый простой (хотя немного и не оптимальный) вариант:

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

    str берется из __defaults__ как LOAD_FAST.
    LOAD_CONST немного круче, но такое без ручного ковыряния в байткоде не сделаешь.

    ОтветитьУдалить
  14. >>> Самый простой (хотя немного и не оптимальный) вариант

    Зато красивый :)

    >>> str берется из __defaults__ как LOAD_FAST.
    LOAD_CONST немного круче, но такое без ручного ковыряния в байткоде не сделаешь.

    Так "низко" я пока не опускался...

    ОтветитьУдалить
  15. О кешировании: в Python 3.2 появился functools.lru_cache
    Симпатичный.

    ОтветитьУдалить
  16. @Андрей Светлов
    Да, обратил на него внимание, вот только еще не пробовал.

    ОтветитьУдалить
  17. Я попробовал применить к твоей задачке, быстро вставив код теста, чтобы работало в Python 3.1 (не хотелось сравнивать еще и производительность разных версий).

    На мой взгляд очень быстро должно работать, особенно если без лимита.

    Только is_palindrome был еще быстрее.

    Кстати, а на чем ты примеры тестировал?
    У меня получилась примерно такая же разница, но времена были ровно вдвое меньше.

    И это - два года назад купленный ноутбук.

    ОтветитьУдалить
  18. @Андрей Светлов
    Win 7, Intel Core 2 Duo ~2.9GHz, @Gb RAM

    ОтветитьУдалить
  19. Хмм. Примерно то же самое, но Ubuntu 10.10 Maveric

    ОтветитьУдалить
  20. Попробуйте функцию вообще убрать. Вызов функции это куча операций со стеком и пр. Аналог сишного инлайна.

    В 2.х на 32битных тачках можно ещё включить JIT.

    ОтветитьУдалить
  21. Вызов питоновской функции это никак не тормоза с C стеком и прочее.
    Куда дороже создание нового фрейма.
    Честно, не думал что подобные вещи интересны широкому кругу людей.
    Это - не разу не аналог C intrinsic.
    JIT - это что? psyco? А вы ее использовали?
    Или только читали о том, как хороша?

    ОтветитьУдалить
  22. >>> Вызов питоновской функции это никак не тормоза с C стеком и прочее. Куда дороже создание нового фрейма.

    Очень в точку!

    >> JIT - это что? psyco? А вы ее использовали?

    Есть еще PyPy и unladen (минута молчания)... так что уточнение, как говорится, в студию.

    P.S.
    Лично мне тема оптимизации интересна, так как, почему-то сам процесс приносит много удовольствия и зачастую новой информации :)

    ОтветитьУдалить
  23. Для "чистого" Питона оптимизация простая: читай dis.dis(...) и делай выводы.

    Создание C Extensions требует больших знаний.

    ОтветитьУдалить
  24. остання оптимізація неоптимальна - якщо йти від зворотнього, то приріст продуктивності в порівнянні з №5 складе 6750% для 8-ми значних паліндромів та 4-х значних дільників:

    def is_div(num):
    start = int(num**0.5) - 1
    for i in range(start, my_min, -1):
    rez, fl = divmod(num, i)
    if not fl and rez <= my_max:
    print start
    return True

    def polindroms():
    for i in range(my_max, my_min, -1):
    yield int( str(i) + str(i)[::-1] )

    def my_largest():
    for polindrom in polindroms():
    if is_div(polindrom):
    return polindrom

    ОтветитьУдалить

В этом гаджете обнаружена ошибка