Utter_step 18 июл 2011 в 21:38

Ускорение кода на Python средствами самого языка

5 мин

82K

Python *

+74

Комментарии 46

funca 19 июл 2011 в 01:35

Так почему бы не импортировать их в самой функции?

здесь, напротив, рекомендуют так не делать — если функция станет выполняться многократно, то импорты будут создавать лишний оверхед, т.к. python всё равно вынужден их интерпретировать и выполнять. поместить имена в локальный контекст можно другим способом.

думаю, функция сильно выиграет, если вынесите повторяющиеся вычисления за пределы циклов. например (width / 1.29), (width / 2.6)

Utter_step 19 июл 2011 в 02:10

Промахнулся с утра…

Добавлю еще:
Для если бы значения width изменялись в течении работы программы, то, да, их безусловно требовалось бы поместить на уровень выше частовызываемой функции вместо того чтобы считать в ней.

Днем помещу Ваши замечания в пост, спасибо за коментакрий!

susl 19 июл 2011 в 03:22

будет ~0 прирост, потому что это самый внешний цикл. практически вся работа в самом вложенном (300 итераций который).

Utter_step 19 июл 2011 в 02:06

С первым — в общем случае вы правы, но к функциям полученным на шаге 0 это не совсем применимо, чаще всего они отрабатывают один раз. Но для часто вызываемых функций Ваше решение безусловно будет верней.

Со вторым — не совсем. Интерпретатор при запуске создает кортеж co_constants, в котором лежат значения неизменные для всего вызова функции, так что по сути эти значения будут вычислены единожды при запуске.

nolar 19 июл 2011 в 02:53

>… за счет мелких и незначительных изменения, таких как замен ** на *, можно заставить зеленого змея ползать до двух раз быстрее, без применения тяжелой артиллерии…

Из чего следует, что питону не хватает умного оптимизатора кода (в случае CPython, на этапе py->pyc), наподобие тех, что есть в си-компиляторах уже годы как. Хватило хотя бы банального сопоставления с известными алгоритмическими паттернами, типа вот этого возведения в квадрат или приведения типов.

gribozavr 19 июл 2011 в 03:06

Не всё так просто. А всё из-за динамической типизации: в выражении x**2 икс может оказаться объектом с перегруженнным методом __pow__, и тогда замена на __mul__(2) неправомерна, так как спецификация языка не обызявает авторов наделять __pow__ семантикой возведения в степень. Поэтому необходимо сначала доказать, что икс будет вещественным числом (или если доказать невозможно, то «заметить», что в большинстве случаев он является вещественным), и сделать замену (а если не доказали — то вставить проверку типа в том месте, где доказательство сломалось и контролировать правомерность оптимизации).

kmike 19 июл 2011 в 08:20

В этом смысле pypy рулит, т.к. у него как раз вся информация есть о типах реал-тайм, JIT поэтому же теоретически (и иногда практически) может давать более оптимизированный код и большее ускорение, чем статический компилятор.

eigrad 19 июл 2011 в 08:13

В качестве умного оптимизатора кода в данном случае должен выступать сам программист. Не умеете писать на Python'е — пишите блин на Visual Basic. Там действительно в большинстве случаев препроцессор и оптимизатор априори умнее программиста, даже подсказки дают что где не так написано.

eigrad 19 июл 2011 в 08:15

Для Python'а есть кстати pylint, он иногда помогает вскую чушь исправлять.

susl 19 июл 2011 в 03:26

Можно не считать арктангенс и потом косинус.
cos(arctan(y / x)) = x / sqrt(x*x + y*y)
так как вы p уже посчитали, то
phi = math.atan2(y, x — 0.25)
pc = 0.5 — 0.5 * math.cos(phi)
можно заменить на
pc = 0.5 — 0.5 * x / p

С другой стороны эта оптимизация в среднем цикле, а вся работа в самом вложенном. Я даже не уверен замена y ** 2 на y * y и т.д. дала бы видимый прирост.

P.S. PyPy is the new psyco

Utter_step 19 июл 2011 в 03:36

Как ни странно, замена pc = 0.5 — 0.5 * x / p, приводит к увеличению времени работы на 0.17сек, т.е. на 5%. Вечером попробую разобраться, интересный момент.

Замена y ** 2 на y * y дает прирост в ~4%, т.к. даже средний цикл выполняется ширина * высота раз, т.е. в данном случае 600 * 600 = 360000 раз.

susl 19 июл 2011 в 04:02

Да, но внутренний цикл выполняется в 300 раз чаще. Я понимаю что во многих случаях до него работа и не доходит вовсе. И все-таки, для меня сюрприз что аж 4% прирост

Utter_step 19 июл 2011 в 04:16

Если интересует — могу в ЛС кинуть код, получившийся наиболее оптимальным.

homm 19 июл 2011 в 04:03

Последняя оптимизация вообще не понятно, для чего приведена. «А еще я обнаружил, что такая картинка у меня уже давно сгенерирована, поэтому генерация заняла 0с».

Utter_step 19 июл 2011 в 04:09

Ну это уже так, баловство:)

Да и на самом деле ситуация немного сложнее чем Вы описали — задачи с симметричными решениями — частая ситуация, поэтому найдя ось симметрии можно действительно сократить время выполнения вдвое.
Но все же, это далеко от общего случая поэтому и указанно вскользь, как небольшой хак.

alexey_uzhva 19 июл 2011 в 06:24

ИМХО наоборот эта оптимизация должна была идти первой. После чего разработчик должен почесать затылок и подумать, может быть 1.5сек достаточно для его задачи и имеет ли смысл платить ухудшением кода за дополнительные 18% скорости. Ответ будет зависеть от задачи и далеко не всегда дальнейшая оптимизация будет иметь смысл.

Utter_step 19 июл 2011 в 06:30

Верно, но а) эта оптимизация не применима в общем случае, в отличии от остальных описанных
б) я не просто так указывал процентное изменение, 1.5сек вполне достаточно, но код, работающий с 600*600 за 1.5 сек отработает на, скажем 6000*6000 (адекватное разрешение для изучения фрактала) за ~150сек, а тут уж даже десятые доли процента не помешают.
После всех оптимизаций+хак, 6000*6000 обрабатывается за 79сек, что всяко лучше 150.)

alexey_uzhva 19 июл 2011 в 07:58

Да, оптимизации иногда важны и нужны. Однако даже в случае 150сек на обработку вашего фрактала, действительно ли 2.5 минуты это много? Ведь изучение может занять ну по крайней мере часы, так что минуту или две будет генерироваться картинка — часто тоже имеет весьма мало значения.

Я в общем-то к чему — любая цифра должна рассматриваться в контексте. Для какого-то вычисления 2 минуты катастрофически много, а для какой-то работы, которая сама по себе занимает часы, 2 минуты или одна — не более чем статистическая погрешность, и портить из-за нее код не имеет смысла.

Nostromo 19 июл 2011 в 06:18

blip.tv/pycon-us-videos-2009-2010-2011/introduction-to-python-profiling-1966784

название видео говорит само за себя. Отличный материал про профилирование на питоне с 2009 pycon

Nostromo 19 июл 2011 в 07:02

ну и примерно по смыслу аналогичный доклад для тех кто не хочет слушать английскую речь — на русском языке, с PyCamp Kyiv 2010
betv.com.ua/actions/pycamp2010/2010/pycamp-kyiv-2010-aleksandr-shigin-pochemu-python-tormoz/
за линк спасибо юзеру masterkey.habrahabr.ru/

ssmaxss 19 июл 2011 в 06:30

Как-то все слишком мудрено и сравнительно малорезультативно.
а) На Psyco больше рассчитывать не стоит, вместо него надо смотреть на pypy
б) Задачка вычислительная => очень легко и полезно было бы использовать cython. Получится сишной расширение, С для этого знать особо не надо, скорость разработки практически такая же как и у Python. (Скорее всего ускорение 2х можно будет получить вообще ничего не делая и просто скомпилировав уже имеющийся cython'ом). При правильной оптимизации можно получить ускорение 100х и больше.

sphinks 19 июл 2011 в 07:26

Хороший материал, спасибо за статью.

JiLiZART 19 июл 2011 в 07:29

мне тут сосед подсказывает что
там
1) -(width/1.29)/(width/2.6) это константа, width сокращается и 2.6 делится на 1.29.
2) (2 — width/1.29)/(width/2.6) — (1-w/1.29)/(w/2.6) = (2 — w/1.29 — 1 + w/1.29)/(w/2.6) = (1/(w/2.6)) = 2.6/w :)
Ладно если второе выполнится 1 раз, то первое выполнится 600 раз при том что это обычная константа.

kmike 19 июл 2011 в 07:51

Psyco умер, pypy — это «все или ничего» (кусок нельзя ускорить), ускорение через смену алгоритма — это абсолютно правильно, но и так понятно, профайлер — это хорошо.

Но на практике подобные вычисления стоит ускорять через cython или numpy. Не нужно их бояться) Cython не потребует даже переписывать код (можно просто рядом очень небольшой файлик с подсказками положить), numpy переписывать потребует, но, скорее всего, в итоге код короче получится.

sdfsdhgjkbmnmxc 19 июл 2011 в 08:13

Ещё можно экономить на создании объектов. Например, не создавать каждый раз в цикле xrange(width), а сделать в начале функции «width_range = range(width)», а внутри уже «for X in width_range:».

Sardar 19 июл 2011 в 08:49

xrange(width) это генератор, а range(width) даст список. Создание генератора довольно простая вещь, тем более он сам себе и итератор. Пробег по списку создаст скрытый итератор в цикле. К тому же при ощутимо большом width будем сильно потреблять память.

Итог: по моему xrange почти всегда лучше.

sdfsdhgjkbmnmxc 19 июл 2011 в 10:34

С первым абзацем полностью согласен.

Но то, что xrange «почти всегда лучше» это немного некорректный вывод. Если надо меньше памяти, то, конечно, лучше xrange. Но если надо быстрее (а топик был именно о скорости), то избавившись от создания сотен или тысяч мелких одинаковых объектов, пусть даже генераторов, можно выиграть немного времени. Я проверял.

hellman 19 июл 2011 в 11:02

В любом случай range или xrange создается один раз.

sdfsdhgjkbmnmxc 19 июл 2011 в 11:04

Как это — в любом?

hellman 19 июл 2011 в 13:48

А, вы имели ввиду внутренний цикл. Извиняюсь, не понял.
А как вы собираетесь «сбрасывать» xrange? Второй раз он не итерируется просто так.

hellman 19 июл 2011 в 13:54

А не, итерируется. Я мучал сам итератор, а не xrange.

sdfsdhgjkbmnmxc 19 июл 2011 в 14:01

О, и правда. Тогда вообще всё замечательно: width_range=xrange(width) — и расход памяти не увеличивается, и скорость растёт.

sdfsdhgjkbmnmxc 19 июл 2011 в 13:58

См. исходный комментарий:

Например, не создавать каждый раз в цикле xrange(width), а сделать в начале функции «width_range = range(width)», а внутри уже «for X in width_range:».

Sardar 19 июл 2011 в 16:53

При пробеге по списку интерпретатор создает итератор по списку (в прямом смысле вызывая __iter__), что по любому создаст «мелкий одинаковый объект».

Да, вывод не верный. Более правильно будет: для циклов по целым числам быстрей xrange.

А range нужен что бы просто создать список. Любой список. Способность пробежаться по нему, к примеру по буквам range('a', 'z') это скорее бонус =)

sdfsdhgjkbmnmxc 25 июл 2011 в 14:40

1) __iter__-__iter__ом, но ведь имеет значение, вызывать __iter__ у уже существующего инстанса или каждый раз создавать его перед вызовом?

2) range всё-таки может создать не любой список, а только «containing arithmetic progressions» (http://docs.python.org/library/functions.html#range). range('a', 'z') это вообще TypeError.

3) в конце-концов, можно позвать cProfiler, и проверить:

import cProfile
i = 5000

def xrange_xrange():
    for x in xrange(i):
        for y in xrange(i):
            (x, y)

def xrange_prerange():
    y_range = range(i)
    for x in xrange(i):
        for y in y_range:
            (x, y)

for _ in range(10):
    cProfile.run('xrange_xrange()')
    cProfile.run('xrange_prerange()')
    print '=' * 10

Сокращённый вывод:
==========
3 function calls in 7.061 CPU seconds
4 function calls in 6.022 CPU seconds
==========
3 function calls in 6.605 CPU seconds
4 function calls in 5.749 CPU seconds
==========
3 function calls in 6.548 CPU seconds
4 function calls in 5.927 CPU seconds
==========
3 function calls in 6.052 CPU seconds
4 function calls in 6.182 CPU seconds
==========
3 function calls in 5.970 CPU seconds
4 function calls in 5.966 CPU seconds
==========
3 function calls in 7.590 CPU seconds
4 function calls in 5.955 CPU seconds
==========
3 function calls in 6.167 CPU seconds
4 function calls in 5.867 CPU seconds
==========
3 function calls in 6.763 CPU seconds
4 function calls in 6.048 CPU seconds
==========
3 function calls in 5.988 CPU seconds
4 function calls in 5.690 CPU seconds
==========
3 function calls in 5.827 CPU seconds
4 function calls in 6.048 CPU seconds
==========

Т.е. эффект от выноса range() за внешний цикл хотя и не очень значительный, но есть.

homm 19 июл 2011 в 09:37

Просьба к автору: не поленитесь, запустите на PyPy, всем же, думаю, интересно :)

Utter_step 19 июл 2011 в 10:30

Вечером — обязательно!)

Utter_step 19 июл 2011 в 18:14

Пока испытываю некоторые проблемы с ~~удалением гланд через~~сборкой PIL для PyPy под 64bit виндой.
Если так и не выйдет — завтра будет под рукой машина под linux, проведу все тесты заново на ней.

Utter_step 24 июл 2011 в 18:07

Под PyPy так и не удалось завести PIL (RPython вылетал с трейсом:
Fatal RPython error: NotImplementedError
про обращении к pixel access object'y PIL'я)

Однако, если заменить реальную раскраску пикселей на добавление значения цвета в двумерный массив PyPy дает ускорение в 4 раза.
Но, неизвестно, как бы он отработал взаимодействие с PIL, так что данный результат не стоит считать состоятельным, увы.

sylvio 19 июл 2011 в 11:10

Можно значительно улучшить статью, если не заниматься шаманством, а сравнить дизассемблированные листинги.

import dis
dis.dis(func)

alextretyak 6 окт 2018 в 04:15

А может кто-нибудь объяснить как работает вот эта строчка кода?

pix[X, Y] = (255, 255, 255)

(я думал, что правильно писать так: pix[X][Y] или pix[Y][X])

Просто если pix = [[1, 2], [3, 4]], то pix[0, 1] у меня выдаёт ошибку ‘‘list indices must be integers or slices, not tuple’’.

homm 6 окт 2018 в 10:30

Просто если pix = [[1, 2], [3, 4]]

Так pix это не список, это то что возвращает img.load().

alextretyak 6 окт 2018 в 10:34

Эм. А что такое img? Имя модуля? И где посмотреть код этой img.load()?

homm 6 окт 2018 в 10:57

img это объект изображения в библиотеке Pillow. img.load() возвращает объект доступа к пикселям. Странно, конечно, что автор об этом ничего не сказал.

Barafu_Albino_Cheetah 6 окт 2018 в 10:54

А вы вот так объявите:

 pix = {(1,1): 0,(1,2):0,(1,3):0}

alextretyak 6 окт 2018 в 10:56

Здорово! А я не догадался…
Но это не снимает вопрос о том, где смотреть код функции img.load(). [А, уже ответили выше.]

Зарегистрируйтесь на Хабре, чтобы оставить комментарий