Почему порядок объединения строк в python сильно влияет на скорость?

Question

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

Подход 1:

total_str = ""
for m in messages:
    total_str = total_str + m + "\n"

Это былочрезвычайно медленный - после примерно 100 000-го сообщения добавление каждого сообщения занимает около 2-3 с, а после 300 000-го сообщения этот процесс в основном останавливается.

Подход 2:

total_str = ""
for m in messages:
    tmp = m + "\n"
    total_str = total_str + tmp

Этоподход завершил объединение всех 1,6 миллионов сообщений менее чем за секунду.

Что меня интересует, так почему второй подход намного быстрее первого?

Answer 1

a + b + c - это не единственная операция, которая объединяет a, b и c в одну строку.Это две операции, t = a + b и t + c, что означает копирование содержимого a дважды ;один раз скопировать a в t, и снова, когда t скопируется в результат t + c.Поскольку в вашем примере a - это строка, которая становится все длиннее, вы на best удваивает объем данных, копируемых на каждом шаге.

Лучший подход - избегатьвсе временные объекты str, созданные + и использующие join:

total_str = "\n".join(messages)

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

Answer 2

Строки Python являются неизменяемыми и непрерывными.Первое означает, что они не могут быть изменены, а второе означает, что они хранятся в одном месте в памяти.Это отличается от, например, структуры данных веревки , где добавление данных является дешевой операцией, для которой нужно только сформировать новый узел для конца.Это означает, что операция конкатенации должна каждый раз копировать обе входные строки и что-то вроде total_str = total_str + m + "\n", поскольку + является левой ассоциативно , копирует все total_str дважды.Обычным решением является сохранение всех маленьких строк до полного завершения набора и использование str.join для выполнения конкатенации за один проход.Это будет копировать каждую строку компонента только один раз, вместо геометрического (пропорционального квадрату) числа раз.Другой вариант, чтобы построить буфер по мере продвижения, это использовать io.StringIO.Это даст вам файлоподобный объект, похожий на StringBuilder в некоторых других языках, из которого вы можете извлечь окончательную строку.У нас также есть такие операции, как writelines, которые могут принимать итерации, поэтому соединение может вообще не понадобиться.

Я полагаю, почему вторая реализация смогла быть намного быстрее (не только в два раза быстрее), что существуют оптимизации, которые иногда позволяют CPython не выполнять копию левого операндасовсем.PyUnicode_Append, по-видимому, имеет именно такую ​​оптимизацию, основанную на unicode_modifiable, в которой он может мутировать объект, если счетчик ссылок равен точно 1, строка никогда не хэшировалась, и некоторые другие условия.Обычно это относится к локальной переменной, где вы используете +=, и, вероятно, компилятору удалось сгенерировать такое поведение, когда в том же присваивании не было второго оператора.

Answer 3

Ну, поскольку a = a + b + c выполняется как a = (a + b) + c, можно видеть, что порядок вычислений следующий:

• tmp_1 = a + b.Это должно скопировать огромную строку a, потому что строки неизменны.
• a = tmp_1 + c.Это должно скопировать (даже больше) огромную строку tmp_1, потому что строки являются неизменяемыми.

Итак, задействовано две огромных копии, тогда как во второй версии a = a + tmp (как в вашем втором примере), только одна такая копия необходима.Последний подход, очевидно, будет быстрее.