Почему '.join() быстрее, чем + = в Python?

Ответ 1

Скажем, у вас есть этот код для создания строки из трех строк:

x = 'foo'
x += 'bar'  # 'foobar'
x += 'baz'  # 'foobarbaz'

В этом случае Python сначала должен выделить и создать 'foobar', прежде чем он сможет выделить и создать 'foobarbaz'.

Итак, для каждого вызываемого +=, все содержимое строки и все, что добавляется к ней, необходимо скопировать в совершенно новый буфер памяти. Другими словами, если у вас есть строки N, которые нужно объединить, вам нужно выделить приблизительно N временные строки, а первая подстрока будет скопирована ~ N раз. Последняя подстрока копируется только один раз, но в среднем каждая подстрока копируется ~N/2 раз.

С .join Python может сыграть несколько трюков, так как промежуточные строки не нужно создавать. CPython определяет, сколько памяти ему нужно, а затем выделяет буфер с правильным размером. Наконец, он затем копирует каждую часть в новый буфер, что означает, что каждый фрагмент копируется только один раз.

Существуют и другие жизнеспособные подходы, которые в некоторых случаях могут привести к повышению производительности для +=. Например. если внутреннее строковое представление на самом деле является rope или если среда исполнения достаточно умна, чтобы как-то понять, что временные строки не имеют используйте программу и оптимизируйте ее.

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

Ответ 2

Я думаю, что это поведение лучше всего объясняется в главе буфера строки Lua.

Чтобы переписать это объяснение в контексте Python, давайте начнем с невинного фрагмента кода (производного от документа Lua docs):

s = ""
for l in some_list:
  s += l

Предположим, что каждый l равен 20 байтам, а s уже обработан размером 50 КБ. Когда Python объединяет s + l, он создает новую строку с 50 020 байтами и копирует 50 КБ из s в эту новую строку. То есть для каждой новой строки программа перемещает 50 КБ памяти и растет. Прочитав 100 новых строк (всего 2 КБ), фрагмент уже переместил более 5 МБ памяти. Чтобы усугубить ситуацию, после задания

s += l

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

И, в конце:

Эта проблема не свойственна Lua: другие языки с истинным мусором коллекции и где строки являются неизменяемыми объектами, представляют собой аналогичные поведение, Java - самый известный пример. (Java предлагает структура StringBuffer, чтобы улучшить проблему.)

Строки Python также являются неизменяемыми объектами.