Почему соединение быстрее, чем обычное конкатенация

Question

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

Вот питон пример того, что я имею в виду:

# This is slow 
x = 'a' 
x += 'b' 
... 
x += 'z' 

# This is fast 
x = ['a', 'b', ... 'z'] 
x = ''.join(x) 

Спасибо это заранее)

Answer 1

Код в функции соединения знает перед всеми строками, их попросят конкатенировать и насколько велики эти строки, поэтому он может вычислить конечную длину строки перед началом операции. Следовательно, нужно только выделить память для окончательной строки один раз, а затем она может поместить каждую строку источника (и разделитель) в нужное место в памяти.

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

Answer 2

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

Answer 3

Это происходит потому, что все больше и больше кусок памяти должен быть выделен для конкатенации строк:

x = 'a' # String of size 1 allocated 
x += 'b' # String of size 2 allocated, x copied, and 'b' added. Old x discarded 
x += 'b' # String of size 3 allocated, x copied, and 'c' added. Old x discarded 
x += 'b' # String of size 4 allocated, x copied, and 'd' added. Old x discarded 
x += 'b' # String of size 5 allocated, x copied, and 'e' added. Old x discarded 

Так что же происходит вы выполняете большие распределения и копию, а затем развернуться и бросить их прочь. Очень расточительно.

x = ['a', 'b', ..., 'z'] # 26 small allocations 
x = ''.join(x) # A single, large allocation 

Answer 4

Я не знаю, внутренности присоединиться, но в первой версии вы создаете новую строку каждый раз, когда вы называете оператор + =. Поскольку строки неизменяемы, каждый раз, когда выделяется новая память, и создается копия.

Теперь соединение (которое является строковым методом) может выполнять только одно выделение, так как оно может заранее рассчитать размер.

Answer 5

Причина в том, что строки в Python (и многих других языках) являются immutable objects - то есть, после их создания они не могут быть изменены. Вместо этого, конкатенирование строки фактически создает строку , которая состоит из содержимого двух меньших строк, которые конкатенируются, а затем заменяет старую строку новой.

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

Answer 6

См python string join performance и один конкретный anwser, который описывает это очень хорошо:

консультация о конкатенации много строк.

Для вычисления s = s1 + s2 + ... + зп,

1) с помощью +. Создается новая строка s1 + s2, затем создается новая строка s1 + s2 + s3, ... и т. Д., Поэтому задействовано много операций по распределению памяти и копированию. Фактически, s1 копируется n-1 раз, s2 копируется n-2 раз, ... и т. Д.

2) используя "" .join ([s1, s2, ..., sn]). Конкатенация выполняется за один проход, и каждый символ в строках копируется только один раз.

Answer 7

других ответов был в основном покрыт, но если вы хотите еще больше деталей, Джоэл Спольски имеет статью, в которой он описывает «Schlemiel the painter's algorithm», которая является весьма актуальной и хорошо делает дело, почему понимание такого рода низких уровень детализации реализации по-прежнему очень важен, даже если вы работаете на языке высокого уровня, таком как Python.