Зачем быть.'' join () быстрее, чем += в Python?

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

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

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

2 58
python optimization

2 ответа:

допустим, у вас есть этот код, чтобы построить строку из трех строк:

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

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

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

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

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

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

74

Я думаю, что это поведение лучше всего объяснить в глава строкового буфера 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 также неизменяемые объекты.

5