Ускоряем Python-код |
Этот небольшой пост хочу посвятить оптимизации скорости выполнения кода на Python. Зачастую говорят, что Python - большой тормоз. При этом представляют куски кода, мол, вот, - попробуй такое ускорить. Да, действительно, некоторый код нельзя ускорить, потому что... потому что гладиолус. Но в огромном количестве случаев случается так, что тормоза программы вовсе не из-за языка, а... правильно, из-за разработчика. И вся проблема кроется в реализации алгоритма. Хочу показать небольшой пример оптимизации небольшой математической задачки. Итак, начнем. Задачка очень простая, взятая из projecteuler.net.
Постановка задачи
Найти самый большой палиндром, который является произведением двух трехзначных чисел.
Решение в лоб
Итак, не вдаваясь в исследование математических свойств палиндромов, выполним решение задачки в лоб. Алгоритм примерно такой:
- Цикл по числам от 100 до 999.
- Внутренний цикл по числам от 100 до 999.
- Если произведение переменных итерации внешнего и внутреннего цикла - палиндром и он больше предыдущего найденного - запоминаем его.
- Получаем резульат.
Еще раз напомню, что основная задача здесь - написать код, а потом пытаться его оптимизировать, то есть не придумывать другой более быстрый алгоритм, а оптимизировать уже реализованный.
Итак, сделаем программу (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 секунд.
Результат: 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, - тщательно проверяйте свой код".
5й пункт - это оптимизация алгоритма, а не кода. помойму
ОтветитьУдалитьПо сути почти все - оптимизация (кроме 2 и 3). Программный код - это лишь форма представления алгоритма. Но основная идея не нарушена - полный перебор произведений с проверками (просто таким образом выкосили избыточность операций).
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЛень проверять, но разве reversed не быстрее [::-1]?
ОтветитьУдалитьв 4-м пункт можно заменить
ОтветитьУдалитьif product > max_number and is_palindrome(product) :
max_number = product
на
if is_palindrome(product) :
return product
@Amper
ОтветитьУдалитьreversed не быстрее. Попробовали бы сами (неужели так трудно код, хотя бы скопипастить :))
@Zaglebelin
Нельзя. Будет неверный результат.
Следующие очевидные оптимизации -- преобразовывать в строку только один раз, не вызывать is_palindrome, а записать ее код непосредственно внутри цикла, и, раз функция вызываться не будет, локализовать str еще ближе, в локальном словаре сразу перед циклом. И, кстати, можно ведь записать генератор произведения двух переменным одним выражением, может быть, это будет быстрее.
ОтветитьУдалить@Mikhail Edoshin
ОтветитьУдалитьХотелось бы увидеть код таких оптимизаций от вас в сравнении с первоначальным вариантом.
А то все я, да я ... :)
Есть такой принцип: 20/80. 20% затрат дают 80% результата. Я это к тому, что ваш подход к оптимизации в корне неверен.
ОтветитьУдалитьЛюбая оптимизация скорости выполнения негативно отражается на читаемости кода. Поэтому нужно применить принцип 20/80 для того, чтобы сделав минимум изменений, добиться максимального прироста производительности. В идеале, применение ваших оптимизаций должно идти в обратном порядке.
Практика показывает, что только профайлер и здравый смысл в силах указать на узкое место в программе. Ни в коем случае не нужно поддаваться соблазну делать оптимизации наподобие N2.
Советую почитать книги Фаулера "Рефакторинг" и Макконелла "Совершенный код".
Попробовал, но ускорение незначительное. Не при каждом прогоне и есть :) А один генератор по двум переменным оказывается медленнее, чем два цикла.
ОтветитьУдалитьКстати, реально он находит 906609 вторым (993*913), после чего тупо гоняет цикл. Не могу отделаться от мысли, что можно как-то сразу выйти на него.
И один пропуск заметил -- при перевороте границ нужно числа изменить, т. е. range(MAX-1, MIN-1) или, лучше, сами константы, а это нигде не обозначено.
@Mikhail Edoshin
ОтветитьУдалить>>> Не могу отделаться от мысли, что можно как-то сразу выйти на него.
Зайдите на projecteuler.net - запостите результат, и вам откроются решения других. Там есть много описанных вариантов решения задачи. Но при таком брутфорсовском подходе не знаю, как еще сократить.
>>> И один пропуск заметил -- при перевороте границ нужно числа изменить, т. е. range(MAX-1, MIN-1) или, лучше, сами константы, а это нигде не обозначено.
Да, спасибо, поправлю.
>>> Я это к тому, что ваш подход к оптимизации в корне неверен.
ОтветитьУдалитьКаюсь.
>>> Советую почитать книги Фаулера "Рефакторинг"...
Читаю :)
Но это не цель написания статьи. Цель написания статьи не показать мего-классный супер метод оптимизации :), а скорее "наш ответ Чемберлену", то есть тем, кто тычет головой в код, который работает 20 секунд, говорит что питон тормоз, а потом еще пишет об этом на каждом углу, а ты смотришь, - а там можно сделать не 20, а 0.20 :)
P.S.
На самом деле немножко вдохновения получено от этого обсуждения:
http://python.su/forum/viewtopic.php?id=10136
Брутфорс быстрее уже не сделать - слишком уж простая штука 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 немного круче, но такое без ручного ковыряния в байткоде не сделаешь.
>>> Самый простой (хотя немного и не оптимальный) вариант
ОтветитьУдалитьЗато красивый :)
>>> str берется из __defaults__ как LOAD_FAST.
LOAD_CONST немного круче, но такое без ручного ковыряния в байткоде не сделаешь.
Так "низко" я пока не опускался...
О кешировании: в Python 3.2 появился functools.lru_cache
ОтветитьУдалитьСимпатичный.
@Андрей Светлов
ОтветитьУдалитьДа, обратил на него внимание, вот только еще не пробовал.
Я попробовал применить к твоей задачке, быстро вставив код теста, чтобы работало в Python 3.1 (не хотелось сравнивать еще и производительность разных версий).
ОтветитьУдалитьНа мой взгляд очень быстро должно работать, особенно если без лимита.
Только is_palindrome был еще быстрее.
Кстати, а на чем ты примеры тестировал?
У меня получилась примерно такая же разница, но времена были ровно вдвое меньше.
И это - два года назад купленный ноутбук.
@Андрей Светлов
ОтветитьУдалитьWin 7, Intel Core 2 Duo ~2.9GHz, @Gb RAM
Хмм. Примерно то же самое, но Ubuntu 10.10 Maveric
ОтветитьУдалитьПопробуйте функцию вообще убрать. Вызов функции это куча операций со стеком и пр. Аналог сишного инлайна.
ОтветитьУдалитьВ 2.х на 32битных тачках можно ещё включить JIT.
Вызов питоновской функции это никак не тормоза с C стеком и прочее.
ОтветитьУдалитьКуда дороже создание нового фрейма.
Честно, не думал что подобные вещи интересны широкому кругу людей.
Это - не разу не аналог C intrinsic.
JIT - это что? psyco? А вы ее использовали?
Или только читали о том, как хороша?
>>> Вызов питоновской функции это никак не тормоза с C стеком и прочее. Куда дороже создание нового фрейма.
ОтветитьУдалитьОчень в точку!
>> JIT - это что? psyco? А вы ее использовали?
Есть еще PyPy и unladen (минута молчания)... так что уточнение, как говорится, в студию.
P.S.
Лично мне тема оптимизации интересна, так как, почему-то сам процесс приносит много удовольствия и зачастую новой информации :)
Для "чистого" Питона оптимизация простая: читай dis.dis(...) и делай выводы.
ОтветитьУдалитьСоздание C Extensions требует больших знаний.
остання оптимізація неоптимальна - якщо йти від зворотнього, то приріст продуктивності в порівнянні з №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