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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

Совет касается объединения множества строк.

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

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

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

Answer 4

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

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 5

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

Answer 6

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

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

Answer 7

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