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

Я могу найти множество информации в Интернете (о переполнении стека и т. Д.) О том, что это очень неэффективная и плохая практика использования + или же += для конкатенации в Python.

Я не могу найти, почему += это так неэффективно. Помимо упоминания здесь, что "оно было оптимизировано для улучшения на 20% в определенных случаях" (все еще неясно, что это за случаи), я не могу найти никакой дополнительной информации.

Что происходит на более техническом уровне, что делает ''.join() превосходит другие методы конкатенации Python?

Источник

2 ответа

Решение

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

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

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

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

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

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

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

Источник

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

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

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 также являются неизменяемыми объектами.

Источник
Другие вопросы по тегам