Por qué unir es más rápido que la concatenación normal

Question

He visto varios ejemplos de diferentes idiomas que demuestran inequívocamente que unir elementos de una lista (matriz) es mucho más rápido que concatenar una cadena. Lamentablemente, no encontré una explicación de por qué? ¿Puede alguien explicar el algoritmo interno que funciona en ambas operaciones y por qué es el más rápido que otro?

Aquí está un ejemplo de pitón de lo que quiero decir:

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

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

Gracias es adelantado)

Answer 1

El código en una función de unión sabe por adelantado todas las cadenas que se le pide que concatenen y qué tan grandes son esas cadenas, por lo tanto, puede calcular la longitud final de la cadena antes de comenzar la operación. Por lo tanto, solo necesita asignar memoria para la cadena final una vez y luego puede colocar cada cadena fuente (y delimitador) en el lugar correcto de la memoria.

Por otro lado, una sola operación + = en una cadena no tiene más remedio que asignar suficiente memoria para la cadena final que es la concatenación de solo dos cadenas. Posterior + = debe hacer lo mismo, cada memoria asignada que en el próximo + = será descartada. Cada vez que se reproduce la cadena cada vez mayor de un lugar en la memoria a otro.

Answer 2

Bueno, esto es en gran medida depende del idioma, pero en general la idea de que hay, que una gran operación es más rápido que muchos pequeños. En su segundo ejemplo, la unión conoce todos los elementos a los que tiene que unirse y así puede asignar los recursos necesarios y colocar los caracteres. La concatenación en su primer ejemplo tiene que reasignar recursos en cada paso (el peor de los casos).

Answer 3

Esto se debe a que una parte cada vez mayor de la memoria tiene que ser asignado para la concatenación de cadenas:

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 

Lo que pasa es que realice grandes asignaciones y las copias, pero luego dar la vuelta y tirar a la basura. Muy derrochador

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

Answer 4

No sé los detalles internos de unirse, pero en la primera versión que crear una nueva cadena cada vez que se llama al operador + =. Como las cadenas son inmutables, cada vez que se asigna nueva memoria y se realiza una copia.

Ahora, la combinación (que es un método de cadena) solo podría hacer una única asignación, ya que puede calcular el tamaño de antemano.

Answer 5

La razón es que las cadenas en Python (y en muchos otros lenguajes) son immutable objects, es decir, una vez creadas, no se pueden cambiar. En cambio, concatenar una cadena realmente hace una nueva cadena que consiste en concatenar los contenidos de las dos cadenas más pequeñas y luego reemplaza la cadena anterior por la nueva.

Dado que la creación de una cadena lleva cierto tiempo (necesidad de asignar memoria, copiar el contenido de la cadena a esa memoria, etc.), hacer muchas cadenas lleva más tiempo que hacer una sola cadena. Hacer N concatenaciones requiere la creación de N nuevas cadenas en el proceso. join(), por otro lado, solo tiene que crear una sola cadena (el resultado final) y, por lo tanto, funciona mucho más rápido.

Answer 6

Ver python string join performance y uno anwser específica que describe muy bien:

El consejo es sobre la concatenación de una gran cantidad de cadenas.

Para calcular s = s1 + s2 + ... + sn,

1) usando +. Se crea una nueva cadena s1 + s2, luego se crea una nueva cadena s1 + s2 + s3, ..., etc., lo que implica una gran cantidad de operaciones de asignación y copia de memoria. De hecho, s1 se copia n-1 veces, s2 se copia tiempo n-2, ..., etc.

2) usando "" .join ([s1, s2, ..., sn]). La concatenación se realiza en una pasada, y cada carácter en las cadenas se copia una sola vez.

Answer 7

Las otras respuestas han cubierto básicamente, pero si quieres más detalles, Joel Spolsky tiene un artículo en el que describe "Schlemiel the painter's algorithm", que es muy relevante y muy bien hace que el caso de por qué la comprensión de este tipo de baja Los detalles de la implementación del nivel siguen siendo muy importantes, incluso si trabaja en un lenguaje de alto nivel como Python.