Регистрация - Вход

Наши спонсоры


Шаблоны 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() цикла. "Конечно,-- ответил я,-- но это делается ценой вызова функции (лямбда функции) для каждого элемента списка. Я бьюсь об заклад, что это медленнее, поскольку в Python накладные расходы вызова функций больше чем для цикла for." (Ладно, я уже выполнил сравнения. 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() - интерпретатор байт-кода должен выполнить три байт-код инструкции для каждого запроса (считать 'chr', считать 'item', вызвать), в то время, как функция 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.5N2 - 0.5*N. В дополнение к этому, выполняются N операций размещения строк, но для достаточно большого N, терм N2 вызовет переполнение. Действительно, для списка в 8 раз длиннее (2048 элементов), этим функциям времени требуется намного больше чем в 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, которые выполнены на C. В частности, string.joinfields(list_of_strings, delimiter) конкатенирует список строк, размещая delimiter (разделитель) между каждыми двумя строками. Ничто нам не мешает сцеплять список символов (которые являются просто строками длины 1 в Python), используя пустую строку как разделитель. Смотрите:
    import string

    def f6(list):

        return string.joinfields(map(chr, list), "")
Эта функция выполнилась раз в четыре-пять быстрей чем наш самый быстрый кандидат, f3(). Кроме того, она не обладает квадратичным поведением других версий. И Победитель - ... На следующий день я вспомнил необычное добавление к Python: модуль массивов. Бывает, иногда нужно создать массив однобайтовых целых из списка целых чисел Python, и к тому же так, чтобы каждый массив мог быть записан в файл или преобразован в строку как двоичная структура данных. Вот наша функция, реализованная с использованием этих операций:
    import array

    def f7(list):

        return array.array('b', list).tostring()
Она приблизительно в три раза быстрее чем f6(), и от 12 до 15 раз быстрее чем f3()! Причем, здесь, к тому же, используется меньшее количество промежуточного хранения - создается лишь 2 объекта размерами N байтов (плюс стандартный заголовок), в то время, как f6() начинает с рапределения списка из N элементов, который обычно обходится в 4N байт (8N байт на 64-разрядной машине) - предпологая, что символьные объекты размещены коллективно с подобными же объектами где-то в другом месте программы (подобно малым целым числам, Python кэширует строки единичной длины в большинстве случаев). "Стоп,-- сказал мой друг,-- прежде, чем мы сделаем реализацию, время работы которой окажется отрицательным - найденного способа достаточно для моей программы". Я согласился, хотя и хотел попробовать еще одно улучшение: написать функцию целиком на C. При этом можно получить минимальные требования хранения (просто сразу же выделить память под строку длины N) и сэкономить несколько инструкций в C-коде, которые, я знал, были в модуле массивов, из-за его универсальности (поддержка целых чисел размером в 1, 2, и 4 байта). Однако, не было бы способа избежать необходимости извлечения элементов из списка по одному, а затем извлекать из них целые числа C, обе операции - довольно дорогостоящие в Python-C API, так что, я ожидал очень скромного ускорения, по сравнению с f7(). От данного усилия по написанию и испытанию улучшения, к тому же зависящего от нестандартного расширения Python, я решил отказаться... Вывод Если Вы испытываете потребность в быстродействии, используйте встроенные функции - Вы не можете превзойти цикл, написанный на C. Просмотрите библиотечное руководство для встроенной функции, которая делает то, что Вы хотите. Если если такой нет, ниже приводятся некоторые принципы для оптимизации цикла:
  • Правило номер один: оптимизируйте только те фрагменты, которые критичны, в смысле быстродействия. Оптимизируйте только самый внутренний цикл. (Это правило касается не только Python, но это вовсе не причина игнорировать его, поскольку, так можно избежать массу лишней работы. :-)
  • Чем меньше команд, тем лучше. Использование слишком большого объема байт-код инструкций и поиска переменных редко оправданно.
  • Используйте внутренние операции. Встроенный в map() цикл быстрее чем явный цикл for; а цикл while с явным счетчиком цикла еще медленнее.
  • Избегайте вызовов функций, написанных на Python в вашем внутреннем цикле. Это включает лямбда функции. Встраивая код во внутренний цикл, можно сэкономить массу времени.
  • Локальные переменные быстрее чем глобальные; если Вы используете глобальные константы в цикле, скопируете их в локальные переменные перед циклом. Учтите, что в Python имена функций (глобальных или встроенных) - также глобальные константы!
  • Старайтесь использовать map(), filter() и reduce() чтобы заменить явный цикл, но только, если Вы можете использовать встроенную функцию: map со встроенной функцией быстрее чем цикла for, но цикла for со встроенным кодом превосходит map с лямбда-функцией!
  • Проверьте свои алгоритмы на предмет квадратичного поведения. Но примите во внимание, что более сложный алгоритм оправдан только для больших N - для малых N, усложнение того не стоит. В нашем случае, 256 оказалось достаточно малым, чтобы более простая версия была быстрее. У Вас же ситуация может измениться - и это стоит проверить.
  • И последнее, но не маловажное: соберайте данные. Превосходный Python модуль profile может быстро выявить критические места в Вашем коде. Если Вы рассматриваете различные версии алгоритма, сравнивайте их в напряженном цикле, используя функцию time.clock().
Кстати, ниже приводится временнАя функция, которую я использовал. Она вызывает функцию f n*10 раз с аргументом a, затем печатает имя функции и затрачиваемое ею время, округленное до миллисекунд. 10 вызовов подряд нужны, чтобы минимизировать внешнии цикл самОй функции timing, засекающей время. Можно было пойти еще дальше и делать 100 вызовов..., заметьте также, что выражение range(n) записано до того, как засекается время - это еще один прием, чтобы минимизировать ошибку в измерениях. Если Вас волнует эта погрешность, Вы можете откалибровать засекающую функцию timing, вызывая ее с пустой функцией.
    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)



    И несколько менее очевидный:



:::python

    import array

    def g2(string):

        return array.array('b', string).tolist()
Измерения показывают, что g2() приблизительно в пять раз быстрее чем g1(). Хотя, есть одна ловушка: g2() возвращает целые числа в диапазоне -128..127, в то время, как g1() - в диапазоне 0..255. Если Вам нужны положительные числа, g1() оказывается быстрее, чем любая последующая обработка результата g2().
автор: Гвидо ван Россум
перевод: С.Тезадов

КОММЕНТАРИИ







Теги


RSS

Архив



Счетчики



Linux coutner