Перейти до основного вмісту

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

Коментарі

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

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

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

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

    на
    if is_palindrome(product) :
    return product

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    ВідповістиВидалити
  11. >>> Я это к тому, что ваш подход к оптимизации в корне неверен.

    Каюсь.

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

    Читаю :)

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

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

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

    ВідповістиВидалити
  12. Брутфорс быстрее уже не сделать - слишком уж простая штука 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 немного круче, но такое без ручного ковыряния в байткоде не сделаешь.

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

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

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

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

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

    ВідповістиВидалити
  15. @Андрей Светлов
    Да, обратил на него внимание, вот только еще не пробовал.

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

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

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

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

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

    ВідповістиВидалити
  17. @Андрей Светлов
    Win 7, Intel Core 2 Duo ~2.9GHz, @Gb RAM

    ВідповістиВидалити
  18. Хмм. Примерно то же самое, но Ubuntu 10.10 Maveric

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

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

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

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

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

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

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

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

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

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

    ВідповістиВидалити
  23. остання оптимізація неоптимальна - якщо йти від зворотнього, то приріст продуктивності в порівнянні з №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

    ВідповістиВидалити

Дописати коментар

Популярні дописи з цього блогу

Регулярні вирази в Python: вивчення та оптимізація

Writing a regular expression is more than a skill -- it's an art. Jeffrey Friedl Що це таке? Рано чи піздно майже кожному програмісту в своєму житті доводиться стикатись з регулярними виразами. Термін "Регулярні вирази" є перекладом з англійської словосполучення "Regular expressions" і не є зовсім точним, а для тих, хто перший раз почув цей термін, мабуть, навіть спантеличуючим (я, наприклад, коли вперше почув, ніяк не міг собі второпати по назві, хоча б приблизно, що це, і для чого використовується). Літературний і більш осмислений переклад звучав би, мабуть, як "шаблонні вирази". Але назва вже прижилась, а скажете "шаблонні вирази" - вас просто не зрозуміють :). Звідси: Регулярний вираз -  це рядок, що задає шаблон пошуку під-рядків в рядку. Регулярні вирази використовуються для аналізу текстів на предмет відповідності текстової інформації деякому шаблону. Наприклад , шаблон, що задає слово, яке містить букву "к". Де застосовують

Python: як програмно перемкнути розкладку клавіатури в Windows

Дослідивши дане питання, я побачив, що Python не має засобів "з коробки" для вирішення цієї задачі. Відвоідно, задача повинна вирішуватись для каждої ОС своїм шляхом. Дане рішення було знайдено мною для ОС Windows XP +. Панацея - Win API Для того, щоб виконати завдання необхідно встановити додатково бібліотеку pywin32 , яка надає доступ до функцій Windows API з Python. З цієї бібліотеки нам знадобиться модуль win32api . >>> import win32api Дослідивши його вміст, можна побачити, що для роботы з розкладкою клавіатури є декілька функцій і одне системне повідомлення Windows - WM_INPUTLANGCHANGE : GetKeyboardLayout GetKeyboardLayoutList LoadKeyboardLayout В даному випадку для нас важлива саме остання функція - LoadKeyboardLayout . Дана функція завантажує нову розкладку (якщо вона ще не завантажена) і виконує після цього ще якісь дії; приймає в якості аргументів два: рядок з ідентифікатором розкладки. дію. Більш детально про їхні можливі значення можна почитати в MSDN . О

Python: PEP-8 чи не PEP-8

Пост - не технічний, кому не цікаво - можете далі не читати... PEP-8, хоча й фактично є пропозицією по розширенню Python під номером 8, серед Python програмістів уже став терміном, що позначає правила стилю оформлення коду. Ні, я не збираюсь зараз описувати його тут - про нього можна почитати в першоджерелі . Питання в тому, слідувати цьому стандарту, чи не слідувати? Ітак, стандарт це в більшості випадків добре, оскільки вносить порядок. Наприклад, стандарт USB 2.0 - просто прекрасний стандарт, уявіть собі, якби флешки були не USB, а кожна мала б свій вихід :)... Жахливо, так, були б у нас USB-порти як card-reader'и - 62 в 1.. Реально 62 в 1 Інша справа з PEP-8. Тут все по іншому, адже програма не змінює свою поведінку, якщо ми будемр робити відступ не в 4 пробіла, а 2 (добре, що більшість, все-таки, робить 4), або будемо ставити пробіл перед другою дужкою, чи не будемо і т.д..  Отже, кожен програміст може редагувати свій код як йому хочеться. Мені, наприклад, подобається