In developer’s way

Перевод статьи Оливера Кроу (Oliver Crow) Efficient String Concatenation in Python

Сравнение производительности нескольких способов

Введение

Формирование длинных строк в языке программирования Python иногда может привести к очень медленному выполнению кода. В этой статье я исследую производительность различных способов сложения строк.

Строковые объекты в Питоне являются немутирующими — т.е. каждый раз при присвоении переменной строкового значения происходит создание нового объекта в памяти, содержащего новое значение переменной. Это отличается от языков наподобие Perl и BASIC, где строковые переменные могут быть изменены по месту. Типичная операция формирования длинной строки из множества коротких является не очень эффективной в Питоне, если использовать самый очевидный способ дописывания фрагментов в конец имеющейся строки. Каждый раз при дописывании в конец строки интерпретатору Питон приходится создавать новый строковый объект и копировать в него содержимое как добавляемой, так и имеющейся строки. Как только вы начнёте работать с большИми строками, этот процесс начнёт становиться всё более и более медленным.

Какие ещё способы [сложения строк] существуют, и как сопоставляется их производительность? Я решил попробовать несколько разных способов формирования очень длинных строк и увидеть, насколько они различаются по эффективности.

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

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

0123456789010111213141516171819

Хотя эта тестовая задача является частным случаем и не встречается ни в одной реальной программе (которую я могу себе только представить), она является хорошей тестовой задачей, поскольку её просто запрограммировать, и она проста как для понимания, так и для вычисления. Также, складываемые строки различаются по содержимому и длине, что предотвращает любые возможные оптимизации в интерпретаторе или в аппаратном обеспечении, которые возможно имеют место на больших строках из повторяющихся данных. Не думаю, что интерпретатор Питона действительно это делает, однако это хороший принцип — использовать тесты, не подверженные таким ситуативным оптимизациям.

Шесть способов

Вот способы, которые я тестировал. Каждый их этих шести фрагментов кода, написанных на Питоне, формирует на выходе одну и ту же строку.

Способ 1: Простое дописывание

def method1():
    out_str = ''
    for num in xrange(loop_count):
        out_str += `num`
    return out_str

Лично для меня это самое очевидное решение — использовать оператор добавления (+=) для дописыания каждого фрагмента к имеющейся строке. Переменная loop_count указывает, сколько строк нужно сложить. Тильды (`) вокруг числа на четвёртой линии конвертирует число в строку. Вы можете добиться того же результата с помощью функции str(), но она работает слегка медленнее, поэтому я придерживался тильды во всех способах. Как я уже упоминал, хотя этот метод является самым очевидным, он вообще не является эффективным. Как вы можете увидеть в таблице результатов, производительность составила всего лишь 3770 строковых операций в секунду. Если вам требуется много сложений, то это не то, что вам нужно.

Способ 2: Класс MutableString

def method2():
    from UserString import MutableString
    out_str = MutableString()
    for num in xrange(loop_count):
        out_str += `num`
    return out_str

Библиотека Питона содержит класс MutableString. Согласно документации, этот класс создан для образовательных задач. Можно подумать, что его оператор добавления не будет заново выделять память или копировать строки. Однако на тестовой задаче этот метод сработал ещё хуже, чем Способ №1. Исследуя исходный код файла UserString.py я обнаружил, что хранилищем для MutableString является потомок строкового типа данных, и на самом деле MutableString даже не переписывает метод __add__. Сложение с использованием этого класса не может быть быстрее обычной операции над немутирующими строками (Способ №1), в действительности же дополнительные накладные расходы на выполнение методов класса MutableString делают этот способ значительно медленнее.

Способ 3: Массив символов

def method3():
    from array import array
    char_array = array('c') 
    for num in xrange(loop_count):
        char_array.fromstring(`num`)
    return char_array.tostring()

Я почти не пробовал этот способ, но однажды я увидел его в почтовой рассылке и решил дать ему шанс. Идея состоит в том, чтобы для хранения строки использовать массив из символов. Массивы являются мутирующими в Питоне, что позволят изменять их по месту, без копирования имеющегося содержимого. В нашей задаче нас не интересует изменение имеющихся элементов массива — нам нужно просто добавлять новые элементы в его конец. Метод fromstring() посимвольно добавляет строку к имеющемуся массиву.

Способ 4: Создать массив строк, потом объединить

def method4():
    str_list = []
    for num in xrange(loop_count):
        str_list.append(`num`)
    return ''.join(str_list)

Этот подход обычно предлагается как очень “питоновский” способ сложения строк. Сначала создаётся список с фрагментами строки, затем одной операцией объединения формируется итоговая строка, в которой все элементы списка сложены друг с другом.

На последней строке вы могли заметить необычный стиль Питона — мы вызываем метод join на пустом строковом объекте. Не так много языков позволяют вызывать методы на строковом значении. Если это задевает ваше чувство прекрасного, вы можете заменить последнюю строку на следующую:

    return string.join(str_list, '')

Способ 5: Запись в псевдо-файл

def method5():
    from cStringIO import StringIO
    file_str = StringIO()
    for num in xrange(loop_count):
        file_str.write(`num`)

    return file_str.getvalue()

Модуль cStringIO предоставляет класс StringIO, который выглядит как обычный файл, но хранится в памяти. Очевидно, что дописывать в файл легко — вы просто пишете данные в его конец, то же самое верно и для этого модуля. Существует также похожий модуль StringIO, но в отличие от cStringIO он реализован не на C, а на Питоне. Он должен быть весьма быстрым. Используя этот объект мы можем сформировать нашу строку путём последовательной записи фрагментов и получения результата методом getvalue().

Что интересно — в Java, так же как и в Python, строковые объекты являются немутирующими. Однако в Java есть класс StringBuffer. Он немного мощнее чем питоновский StringIO или подход с массивом символов, поскольку он позволяет не только добавлять фрагменты, но и удалять их или вставлять в произвольное место.

Способ 6: Преобразование списка

def method6():
    return ''.join([`num` for num in xrange(loop_count)])

Этот способ самый короткий. Я испорчу сюрприз и скажу, что он ещё и самый быстрый. Он крайне лаконичный и также весьма понятный. Создать список, используя преобразование списка, а затем объединить все элементы вместе. Проще некуда. На самом деле это всего лишь сокращённый вариант Способа №4, и он использует почти столько же оперативной памяти. Однако он быстрее, поскольку не приходится в каждом цикле вызывать метод list.append() .

Результаты

Меня интересовало как время, затраченное на формирование строки, так и объём памяти, используемой интерпретатором Питона во время выполнения задачи. Хотя память дёшева, есть несколько причин, по которым объём используемой памяти может быть важным фактором. Например, программа может быть запущена на системе с ограниченными ресурсами. Так, в “shared hosting” окружении машина может быть настроена на ограничение объёма используемой памяти для каждого процесса. Если процесс превысил выделенную на него квоту памяти, то он, как правило, убивается ядром. Это будет раздражающим для скриптов CGI, и весьма прискорбным для долгоживущих серверных процессов. В этих случаях защита от непредсказуемого роста используемой памяти является важной. Другая причина состоит в том, что когда вы работаете с очень длинными строками, то слишком большой рост используемой интерпретатором памяти может привести [подсистему виртуальной памяти] к использованию своппинга для этого процесса. Тогда производительность пойдёт под гору. Не имеет значения, что вы нашли самый быстрый алгоритм в мире — если он использует слишком много памяти, то он будет выполняться как черепаха. Если использовать алгоритм, использующий меньше памяти, шанс на своппинг снижается, а производительность становится более предсказуемой.

Каждый способ я проверял отдельным тестом, использующим свой собственный питоновский процесс. Тесты проводились используя Python 2.2.1 на компьютере PII Celeron 433МГц под управлением FreeBSD 4.9.

Результаты: двадцать тысяч чисел

В первом тесте 20.000 чисел были объединены в строку длиной 86кб.

Способ	Сложений в секунду	Размер процесса (Кб)
Способ №1	3770	2424
Способ №2	2230	2424
Способ №3	29.600	2452
Способ №4	83.700	3028
Способ №5	90.900	2536
Способ №6	119.800	3000

Результаты: пятьсот тысяч чисел

Дальше я попробовал запустить каждый способ, используя 500.000 чисел, объединяемых в строку длиной 2,82мб. Это гораздо более серьёзный тест, и мы начали видеть, что размер питоновского процесса растёт, подстраиваясь к используемой в вычислениях структуре данных.

Способ	Сложений в секунду	Размер процесса (Кб)
Способ №3	17.100	8.016
Способ №4	74.800	22.872
Способ №5	94.900	10.480
Способ №6	102.100	22.844

Я даже не пытался запускать эти тесты используя Способы №1 и №2. Они копируют исходную строку целиком при каждом дописывании, поэтому их производительность будет O(n^2). Соединение половины миллиона чисел этими способами займёт много минут.

Сравнивая результаты этого теста с предыдущим, обратите внимание на то, что количество сложений в единицу времени стало ниже для Способов №3, №4 и №6. Это не удивительно — строковое представление каждого числа стало немного длиннее в этом тесте — обычно 5 цифр вместо 4-х. В первом тесте Способ №3 был в 10 раз быстрее, чем первые два способа, но он не очень хорошо масштабируется на более длинном тесте. Сейчас он показывает менее чем 60% от своей производительности в предыдущем тесте. Однако, он использует меньше памяти, чем любой другой приемлемый метод. Очевидно, что в этом случае Питон делает отличную работу по эффективному хранению массива и освобождению памяти из-под временных строк.

Способ №4 более чем в 20 раз быстрее простого дописывания в тесте с 20.000 и по-прежнему хорош на 500.000. Что интересно — Способ №5 лучше проявил себя на более длинном тесте. Способ №6 по-прежнему абсолютный лидер, но Способ №5 делает больше сложений в единицу времени и почти догнал Способ №6. Можно догадаться, что при увеличении теста Способ №5 обгонит Способ №6.

Стоит отметить также разницу в потребляемой памяти. В конце вычислений Способом №6 интерпретатор использует 22,84Мб памяти, что в 8 раз больше размера выходной строки, тогда как Способы №3 и №5 используют менее 1/2 от этого объёма.

Выводы

Лично я буду использовать Способ №6 в большинстве настоящих программ. Он быстр и лёгок для понимания. Он требует, чтобы можно было написать одно выражение, которое вернёт каждое складываемое значение. Иногда это просто неудобно — например, когда есть несколько кусков кода, генерирующих вывод. В этом случае вы можете выбрать между Способами №4 и №5.

Способ №4 выигрывает по гибкости. Вы можете использовать любые операции над множествами при работе со списком строк — вставлять, удалять и изменять. Производительность сложения весьма пристойная.

Способ №5 выигрывает по эффективности. Он использует меньше памяти, чем способы со списком (Способы №4 и №6), и при очень большом количестве операций (~700.000) он даже быстрее, чем преобразование списка (Способ №6). Если же вы делаете много сложений строк, то cStringIO — это то, что вам нужно.

Методика измерения

Измерение времени выполнения каждого метода было относительно простым. Я использовал Питоновскую библиотеку timing для измерения затраченного времени. Я не пытался измерять затраченное Питоном процессорное время (чтобы не зависеть от других работающих программ), но машина не была загружена во время тестов, поэтому вряд ли такое измерение дало бы значительно отличающийся результат.

Изменение использования памяти было немного более замысловатым. В настоящее время Python не предоставляет способа для наблюдения за размером выделяемой под объекты памяти, поэтому я использовал юниксовую команду ps для отслеживания выделяемой под процесс памяти. Поскольку размер процесса изменяется в течение выполнения, я хотел измерить максимум используемой памяти. Чтобы это сделать, я запускал команду ps сразу после окончания вычислений. Вызов функции ps_stat() был вставлен сразу перед возвратом из функции method(), чтобы измерять размер процесса до того, как сборщик мусора начнёт уничтожать все локальные переменные функции. Я запускал код, немного изменённый по сравнению с тем, что вы видели ранее, — результат вычисления хранился в строковой переменной, которую выполнял ps_stat(). Моя реализация ps_stat() использует разделение чтобы выделить поля, возвращаемые ps, и выбирает значение размера виртуальной памяти по номеру поля. Значение 15, вероятно, нужно будет изменить для других версий ps.

Полный код, который я использовал, доступен здесь.

from cStringIO import StringIO
import timing, commands, os
from sys import argv

# .....
# method definitions go here
# .....

def ps_stat():
        global process_size
        ps = commands.getoutput('ps -up ' + `pid`)
        process_size = ps.split()[15]

def call_method(num):
        global process_size
        timing.start()
        z = eval('method' + str(num))()
        timing.finish()
        print "method", num
        print "time", float(timing.micro()) / 1000000
        print "output size ", len(z) / 1024, "kb"
        print "process size", process_size, "kb"
        print

loop_count = 500000
pid = os.getpid()

call_method(argv[1])

xrange против range

Я пробовал использовать range вместо xrange, чтобы предварительно рассчитать список чисел. Удивительно — каждый раз range выполнялся немного быстрее. Разница составляла около 1% в самых быстрых способах. Не думаю, что это хорошее оправдание для использования range вместо xrange в общем случае, так как range требует больше памяти, и скорее именно это станет проблемой, а не дополнительный 1% времени, потраченный на перебор xrange.

Армин Риго (Armin Rigo) недавно высказал мысль, что xrange может быть убран как отдельная конструкция языка, если интерпретатор будет достаточно умён, чтобы возвращать объект, который использует подходящее место хранения (итератор или список) в зависимости от контекста. Я нахожу этот аргумент неосуществимым с точки зрения устройства языка, хотя я и не представляю, насколько сложно будет реализовать такую оптимизацию.

Дальнейшая работа

Я бы хотел сравнить другие языки на этой же задаче. Сами собой напрашиваются Perl, PHP, Java и C. Также будет интересно провести серию тестов, используя увеличивающиеся длины строк, и сделать график этих результатов.

Автор: Оливер Кроу (Oliver Crow)