Idioma de concatenación de cuerdas de Python. Necesita aclaración.

De http://jaynes.colorado.edu/PythonIdioms.html

“Cree cadenas como una lista y use ” .join al final. Join es un método de cadena llamado en el separador, no en la lista. Al llamarlo desde la cadena vacía concatena las piezas sin separador, que es una peculiaridad de Python y más bien sorprendente al principio. Esto es importante: ¡la construcción de cadenas con + es tiempo cuadrático en lugar de lineal! Si aprendes un idioma, aprende este.

Incorrecto: para s en cadenas: resultado + = s

Derecha: result = ” .join (cadenas) ”

No estoy seguro de por qué esto es cierto. Si tengo algunas cadenas, quiero unirme a ellas, para mí no es intuitivamente mejor para mí ponerlas en una lista y luego llamar ” .join. ¿No ponerlos en una lista crea algunos gastos generales? Para aclarar…

Línea de comando de Python:

>>> str1 = 'Not' >>> str2 = 'Cool' >>> str3 = ''.join([str1, ' ', str2]) #The more efficient way **A** >>> print str3 Not Cool >>> str3 = str1 + ' ' + str2 #The bad way **B** >>> print str3 Not Cool 

¿Es A el tiempo realmente lineal y B es el tiempo cuadrático?

Sí. Para los ejemplos que eligió, la importancia no está clara porque solo tiene dos cadenas muy cortas, por lo que el apéndice probablemente sería más rápido.

Pero cada vez que haces a + b con cadenas en Python, se genera una nueva asignación y luego se copian todos los bytes de a y b en la nueva cadena. Si hace esto en un bucle con muchas cadenas, estos bytes deben copiarse una y otra vez, una y otra vez, y cada vez que la cantidad que tiene que copiarse se hace más larga. Esto da el comportamiento cuadrático.

Por otro lado, al crear una lista de cadenas no se copia el contenido de las cadenas, solo se copian las referencias. Esto es increíblemente rápido, y se ejecuta en tiempo lineal. El método de unión hace una sola asignación de memoria y copia cada cadena en la posición correcta solo una vez. Esto también toma solo tiempo lineal.

Así que sí, use el idioma ''.join si está tratando con un gran número de cadenas. Por sólo dos cuerdas no importa.

Si necesita más convincente, pruébelo usted mismo creando una cadena de 10M de caracteres:

 >>> chars = ['a'] * 10000000 >>> r = '' >>> for c in chars: r += c >>> print len(r) 

Comparado con:

 >>> chars = ['a'] * 10000000 >>> r = ''.join(chars) >>> print len(r) 

El primer método tarda unos 10 segundos. El segundo lleva menos de 1 segundo.

La concatenación repetida es cuadrática porque es el algoritmo de Schlemiel el pintor (tenga en cuenta que algunas implementaciones lo optimizarán para que no sea cuadrático). join evita esto porque toma la lista completa de cadenas, asigna el espacio necesario y realiza la concatenación en una sola pasada.

Cuando codifica s1 + s2 , Python necesita asignar un nuevo objeto de cadena, copiar todos los caracteres de s1 en él, y luego todos los caracteres de s2 . Esta operación trivial no soporta costos de tiempo cuadráticos: el costo es O(len(s1) + len(s2)) (más una constante para la asignación, pero eso no figura en big-O ;-).

Sin embargo, considere el código en la cita que está dando: for s in strings: result += s .

Aquí, cada vez que se agrega una nueva s , todas las anteriores deben copiarse primero en el espacio recién asignado para el result (las cadenas son inmutables, por lo que la nueva asignación y la copia deben tener lugar). Supongamos que tiene N cadenas de longitud L: copiará L caracteres la primera vez, luego 2 * L la segunda vez, luego 3 * L la tercera vez … en total, eso lo convierte en L * N * (N+1) / 2 caracteres se copian … así que, sí, es cuadrático en N.

En algunos otros casos, un algoritmo cuadrático puede ser más rápido que uno lineal para valores suficientemente pequeños de N (porque los multiplicadores y los costos fijos constantes pueden ser mucho más pequeños); pero ese no es el caso aquí porque las asignaciones son costosas (tanto directa como indirectamente debido a la probabilidad de fragmentar la memoria). En comparación, los gastos generales de acumular las cadenas en una lista son esencialmente despreciables.

Joel escribe sobre esto en Back to Basics .

No es obvio si te refieres a lo mismo que a otras personas. Esta optimización es importante cuando tiene muchas cadenas, digamos M de longitud N. Entonces

UNA

 x = ''.join(strings) # Takes M*N operations 

segundo

 x = '' for s in strings: x = x + s # Takes N + 2*N + ... + M*N operations 

A menos que la implementación lo optimice, sí, A es lineal en la longitud total T = M*N y B es T*T / N que siempre es peor y aproximadamente cuadrática si M >> N

Ahora, ¿por qué es realmente muy intuitivo join ? Cuando dices “Tengo algunas cadenas”, esto generalmente se puede formalizar diciendo que tienes un iterador que devuelve cadenas. Ahora, esto es exactamente lo que pasas a "string".join()