Почему соединение происходит быстрее обычного конкатенации

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

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

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

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

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

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

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

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

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

 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 

См. Производительность объединения строк python и один конкретный андерсор, который описывает его очень хорошо:

Совет о конкатенировании множества строк.

Для вычисления s = s1 + s2 + … + sn,

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

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

Другие ответы в основном касались этого, но если вы хотите еще более подробно, у Джоэла Спольского есть статья, где он описывает « Schlemiel – алгоритм художника », который чрезвычайно важен и красиво объясняет, почему понимание такого уровня детализации реализации на низком уровне все еще очень важно, даже если вы работаете на языке высокого уровня, таком как Python.

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

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

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