Я видел несколько примеров из разных языков, которые однозначно доказывают, что объединение элементов списка (массива) быстрее, чем просто конкатенация строки. К сожалению, я не нашел объяснения, почему? Может ли кто-нибудь объяснить внутренний алгоритм, который работает под обеими операциями, и почему он быстрее, чем другой.
Вот пример 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]). Конкатенация выполняется за один проход, и каждый char в строках копируется только один раз.
Другие ответы в основном охватывали его, но если вы хотите еще более подробно, Джоэл Спольский имеет статью, в которой он описывает " Schlemiel - алгоритм художника", что крайне важно и хорошо объясняет, почему понимание такого рода деталей реализации низкого уровня по-прежнему очень важно, даже если вы работаете на языке высокого уровня, таком как Python.
Хорошо, это сильно зависит от языка, но в целом идея заключается в том, что одна большая операция выполняется быстрее, чем многие маленькие. Во втором примере соединение знает все элементы, к которым он должен присоединиться, и поэтому может просто выделить необходимые ресурсы и поместить символы. Конкатенация в первом примере должна перераспределять ресурсы на каждом шаге (наихудший случай).
Я не знаю внутренних элементов соединения, но в первой версии вы создаете новую строку каждый раз, когда вы вызываете оператор + =. Поскольку строки неизменяемы, каждый раз, когда выделяется новая память и выполняется копия.
Теперь соединение (которое является строковым методом) может выполнять только одно выделение, так как оно может заранее рассчитать размер.