Подходы языка Python - забавный пример оптимизации

Однажды приятель задал мне, казалось бы, простой вопрос: как лучше всего преобразовать список целых чисел в строку, предполагая, что эти целые числа представлены в формате ASCII. Например, список [97, 98, 99] должен быть преобразован в строку 'abc'. Допустим, что мы хотим написать для этого некоторую функцию.

Первый вариант, который я придумал, был откровенно простым:
def f1(list):
 string = ""
 for item in list:
 string = string + chr(item)
 return string

"Этот способ не может быть самым быстрым,"- сказал мой приятель. Как насчет вот такого:
def f2(list):
 return reduce(lambda string, item: string + chr(item), list, "")

Этот вариант выполняет в точности тот же набор строковых операций, что и предыдущий, но тут мы отказались от накладных расходов на выполнение цикла for в пользу, как предполагалось, более быстрого неявного цикла функции reduce().

"Конечно,"- ответил я, - "но он делает все это за счет вызова функции (lambda) для каждого элемента списка. Могу спорить, что это медленнее, ведь вызов функции в языке Python требует больших накладных расходов, чем цикл".

(Хорошо, я уже сравнил перед этим: f2() потребовала на 60% больше времени, чем f1(). Вот так :-)

"Хмм,"- сказал мой знакомый - "мне нужно, чтобы все это работало быстрее". "Хорошо," - сказал я, - "как насчет такой версии":
def f3(list):
 string = ""
 for character in map(chr, list):
 string = string + character
 return string

К обоюдному удивлению, f3() оказалась вдвое быстрее, чем f1()! Причина нашего удивления была двоякой: во-первых, в этом случае использовался больший объем памяти (результат вызова map(chr, list) представляет собой еще один список той же длины); во-вторых, здесь содержалось два цикла вместо одного (тот, что заключен в функции map(), и цикл for).

Безусловно, пространство за счет времени - это известный компромисс, так что первое не должно было нас удивить. И все же как два цикла оказались быстрее, чем один? Этому есть две причины.

Во-первых, в f1() встроенная функции chr() ищется при каждой итерации, тогда как в f3() это делается только один раз (при обработке аргумента map()). "Поиск относительно дорог," - сказал я приятелю- "поскольку правила динамической области имен Python предполагают поиск сначала в общем словаре текущего модуля (где он оказывается неудачным), а затем в словаре встроенных функций (где и находят искомое). Хуже то, что неудачный словарный поиск в среднем чуть медленнее, чем успешный, из-за особенностей цепочечного хэширования."

Вторая причина того, что f3() быстрее, чем f1(), заключается в том, что обращение к chr(item), выполняемое интерпретатором байт-кода, вероятно, чуть медленнее, чем когда это делается функцией map() - интерпретатору байт-кода приходится выполнять три байт-кодовых инструкции для каждого обращения (load 'chr', load 'item', call), тогда как функция map() делает это все на C.

Все это привело нас к идее компромисса, который позволил бы не тратить лишнее пространство, но ускорил бы поиск функции chr():
def f4(list):
 string = ""
 lchr = chr
 for item in list:
 string = string + lchr(item)
 return string

Как и ожидалось, f4() оказалась медленнее, чем f3(), но только на 25%; и все же была примерно на 40% быстрее, чем f1(). Так получилось потому, что поиск локальных переменных происходит быстрее, чем поиск глобальных или встроенных переменных: "компилятор" языка Python оптимизирует большую часть тел функций таким образом, что для локальных переменных не требуется поиска в словаре, а достаточно простой индексации массива. Относительная скорость f4() в сравнении с f1() и f3() предполагает существование обоих названных выше причин быстрой работы функции f3(), однако первая причина (меньшее число поисков) чуть важнее. (Чтобы получить более точные данные об этом, мы должны были бы вкомпилировать соответствующие возможности в интерпретатор).

Тем не менее, наш лучший вариант, f3(), до сих пор был всего лишь в два раза быстрее, чем самое прямолинейное решение, f1(). Могли ли мы что-то улучшить?

Я беспокоился, что квадратичное поведение алгоритма нас погубит. До сих пор мы использовали в качестве тестовых данных список из 256 целых чисел, поскольку именно для этого моему знакомому и нужна была рассматриваемая функция. Но что было бы, если применить ее к списку из двух тысяч символов? Мы бы соединяли все более и более длинные строки, по одному символу за раз. Легко видеть, что, помимо накладных расходов, чтобы создать таким образом список длиной N, придется копировать 1 + 2 + 3 + ... + (N-1) символов, или N*(N-1)/2, или 0.5*N**2 - 0.5*N. Кроме того, существует N операций выделения строки, однако для достаточно большого N элемент, содержащий N**2, превосходит по накладным расходам эти операции. Действительно, для списка в 2048 элементов, который в 8 раз длиннее тестового, любая из этих функций выполняется медленнее много больше, чем в 8 раз; фактически, ближе к 16. Я не осмелился попробовать список, в 64 раза длиннее тестового.

Для того чтобы избежать квадратичного поведения подобных алгоритмов, существует общий подход. Я записал его для строк, состоящих точно из 256 элементов:
def f5(list):
 string = ""
 for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
 s = ""
 for character in map(chr, list[i:i+16]):
 s = s + character
 string = string + s
 return string

К несчастью, для списка из 256 элементов эта версия работала немного медленнее (хотя и не более чем на 20%), чем f3(). Поскольку написание общей версии могло только замедлить процесс, мы не стали беспокоиться о том, чтобы далее рассматривать это направление (за исключением того, что мы все же сравнили его с вариантом, не использующим map(), который, конечно же, опять оказался медленнее).

В конце концов я попробовал радикально отличный от предыдущих подход: использовать только неявные циклы. Заметьте, что вся операция в целом может быть описана следующим образом: применить chr() к каждому из элементов списка; затем конкатенировать полученные символы. Мы уже использовали неявный цикл для первой части: map(). К счастью, в строковом модуле есть несколько реализованных на С функций конкатенации строк. В частности, string.joinfields(list_of_strings, delimiter) конкатенирует список строк, помещая заданный разделитель между каждыми двумя строками. Ничто не мешало нам произвести конкатенацию списка символов (которые всего лишь строки единичной длины в языке Python), используя пустую строку как разделитель. Слушайте и смотрите:
import string
 def f6(list):
 return string.joinfields(map(chr, list), "")

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

И победителем стал...

На следующий день я вспомнил об одной особенности языка Python: модуле array. Этот модуль имеет операции создания массива однобайтовых целых чисел из списка целых чисел языка Python, и каждый массив может быть записан в файл или преобразован в строку как бинарная структура данных. Вот наша функция, реализованная с использованием этих операций:
import array
 def f7(list):
 return array.array('b', list).tostring()

Это уже втрое быстрее, чем f6(), или в 12-15 раз быстрее чем f3()! Здесь также использован меньший объем промежуточный памяти - выделяются только два объекта из N байт (плюс фиксированные накладные расходы), тогда как f6() начинает с выделения списка из N элементов, которое обычно стоит 4N байт (8N байт на 64-битной машине) - в предположении, что символьные объекты разделяются с подобными объектами повсюду в программе (как для малых целых чисел, в большинстве случаев Python кэширует строки единичной длины).

"Стоп,"- сказал мой знакомый -"остановимся, пока мы не получили отрицательного времени выполнения - такой скорости вполне достаточно для моей программы". Я согласился, хотя мне хотелось попробовать еще один подход: написать всю функцию на С. Это помогло бы минимизировать потребности в объеме памяти (она будет выделять сразу строку длины N) и сэкономить несколько лишних инструкций в коде на С, которые, как я знал, были в модуле array, так как он более универсален (поддерживает целые числа шириной в 1, 2 и 4 байта). Тем не менее, при этом не удалось бы избежать необходимости извлекать элементы из списка по одному, а также получать из них целые числа С: обе эти операции являются достаточно дорогостоящими в Python-C API, так что я предполагал в лучшем случае небольшое ускорение по сравнению с f7(). Учитывая усилия, которые необходимо было бы затратить на написание и тестирование расширения (в сравнении с набрасыванием пары строк на Python), и зависимость от нестандартного расширения Python, я решил не исследовать этот вариант...
Вывод
Если вам крайне необходима скорость, обратитесь к встроенным функциям - вы не сможете создать цикл лучше, чем написанный на С. Поищите функции, делающие то, что вам нужно, в библиотечном руководстве по встроенным функциям. Если там нет такой функции, ниже приводятся некоторые принципы оптимизации циклов:

* Правило номер один: оптимизируйте только явно критические участки. Оптимизируйте только самый внутренний цикл. (Это правило существует независимо от языка Python, но невредно его повторить, поскольку оно может сэкономить много работы. :-)
* Маленькое красиво. Учитывая высокие накладные расходы на байт-кодовые инструкции и поиск переменных, редко стоит добавлять в код дополнительные проверки для экономии небольшой работы.
* Используйте встроенные операции. Неявный цикл в map() работает быстрее, чем явный цикл for; цикл while с явным счетчиком цикла работает еще медленнее.
* Избегайте вызова функций, написанных на Python, во внутреннем цикле. Это относится и к lambda. Развертка (inlining) внутреннего цикла может сэкономить много времени.
* Локальные переменные обрабатываются быстрее, чем глобальные; если вы используете глобальную константу в цикле, скопируйте ее в локальную переменную перед циклом. Кроме того, в языке Python функции (глобальные или встроенные) также являются глобальными константами!
* Попробуйте использовать map(), filter() или reduce() для замены явного цикла for, но только если вы можете использовать встроенную функцию: map() со встроенной функцией быстрее for, однако for с развернутым (in-line) кодом быстрее, чем map() с lambda-функцией!
* Проверьте ваш алгоритм на квадратичное поведение. Но заметьте, что более сложный алгоритм окупается только в случае больших значений N - для маленьких N сложность не окупается. В нашем случае 256 оказалось достаточно маленьким значением для того, чтобы более простая версия функции оставалась самой быстрой. Ваши затраты в разных случаях могут отличаться - это стоит исследовать.
* И последнее по упоминанию, но не по значению: собирайте данные. Великолепный модуль профилирования языка Python может быстро продемонстрировать вам узкое место в вашем коде. Если вы сравниваете разные версии некоторого алгоритма, тестируйте его в коротком цикле, используя функцию time.clock().

Кстати, вот функция хронометража, которую использовал я. Она вызывает функцию f n*10 раз с аргументом a, и печатает имя функции и следом - время, которое она отработала, округленное до миллисекунд. 10 повторных вызовов делаются для минимизации накладных расходов самой функции хронометража. Вы можете пойти даже дальше и сделать 100 вызовов... Заметьте также, что выражение range(n) рассчитывается вовне рамок измерения - другой прием минимизации расходов, вносимых функцией хронометража. Если вы обеспокоены этими расходами, вы можете откалибровать их с помощью вызова функции хронометража с пустой (ничего не делающей) функцией.
import time
 def timing(f, n, a):
 print f.__name__,
 r = range(n)
 t1 = time.clock()
 for i in r:
 f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
 t2 = time.clock()
 print round(t2-t1, 3)

Эпилог

Несколькими днями позже мой приятель снова обратился ко мне с вопросом: как ты произведешь обратную операцию? Т.е. создание списка ASCII-кодов из строки. О нет, вот мы и снова тут, промелькнуло у меня в голове...

Но в этот раз все оказалось относительно безболезненным. Было два кандидата, очевидный:
def g1(string):
 return map(ord, string)

И несколько менее очевидный:
import array
 def g2(string):
 return array.array('b', string).tolist()

Определение времени их работы показало, что g2() примерно в пять раз быстрее, чем g1(). Хотя была и ловушка: g2() возвращала целые числа в интервале -128..127, тогда как g1() возвращала целые числа в интервале 0..255. Если вам необходимы положительные числа, g1() будет быстрее, чем любая постобработка результатов, полученных с помощью g2(). (Примечание: с тех пор, как было написано это эссе, в модуль array был добавлен код типа 'B' для беззнаковых байт, таким образом теперь больше нет оснований для предпочтения функции g1()).
Теги:
оптимизация
Добавлено: 24 Мая 2018 20:57:46 Добавил: Андрей Ковальчук Нравится 0
Добавить
Комментарии:
Нету комментариев для вывода...