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