¿Por qué es ” .join () más rápido que + = en Python?

Soy capaz de encontrar una gran cantidad de información en línea (en Stack Overflow y otros) sobre cómo es una práctica muy ineficiente y mala utilizar + o += para la concatenación en Python.

Parece que no puedo encontrar POR QUÉ += es tan ineficiente. Fuera de una mención aquí de que “se ha optimizado para una mejora del 20% en ciertos casos” (aún no está claro cuáles son esos casos), no puedo encontrar ninguna información adicional.

¿Qué está sucediendo en un nivel más técnico que hace que ''.join() superior a otros métodos de concatenación de Python?

Digamos que tiene este código para construir una cadena a partir de tres cadenas:

 x = 'foo' x += 'bar' # 'foobar' x += 'baz' # 'foobarbaz' 

En este caso, Python primero necesita asignar y crear 'foobar' antes de poder asignar y crear 'foobarbaz' .

Por lo tanto, para cada += que se llama, todo el contenido de la cadena y todo lo que se le agrega deben copiarse en un búfer de memoria completamente nuevo. En otras palabras, si tiene N cadenas para unir, necesita asignar aproximadamente N cadenas temporales y la primera subcadena se copia ~ N veces. La última subcadena solo se copia una vez, pero en promedio, cada subcadena se copia ~N/2 veces.

Con .join , Python puede jugar una serie de trucos ya que no es necesario crear las cadenas intermedias. CPython calcula cuánta memoria necesita por adelantado y luego asigna un búfer de tamaño correcto. Finalmente, luego copia cada pieza en el nuevo búfer, lo que significa que cada pieza solo se copia una vez.


Hay otros enfoques viables que podrían conducir a un mejor desempeño para += en algunos casos. Por ejemplo, si la representación de cadena interna es en realidad una rope o si el tiempo de ejecución es lo suficientemente inteligente como para entender de alguna manera que las cadenas temporales no sirven para el progtwig y las optimizan.

Sin embargo, CPython ciertamente no realiza estas optimizaciones de manera confiable (aunque puede ser para algunos casos de esquina ) y dado que es la implementación más común en uso, muchas de las mejores prácticas se basan en lo que funciona bien para CPython. Tener un conjunto estandarizado de normas también hace que sea más fácil para otras implementaciones enfocar sus esfuerzos de optimización también.

Creo que este comportamiento se explica mejor en el capítulo del búfer de cadenas de Lua .

Para volver a escribir esa explicación en el contexto de Python, comencemos con un fragmento de código inocente (un derivado del que se encuentra en los documentos de Lua):

 s = "" for l in some_list: s += l 

Supongamos que cada l es de 20 bytes y la s ya ha sido analizada a un tamaño de 50 KB. Cuando Python concatena s + l , crea una nueva cadena con 50,020 bytes y copia 50 KB de s en esta nueva cadena. Es decir, para cada nueva línea, el progtwig mueve 50 KB de memoria, y sigue creciendo. Después de leer 100 líneas nuevas (solo 2 KB), el fragmento ya ha movido más de 5 MB de memoria. Para empeorar las cosas, después de la tarea.

 s += l 

la vieja cadena ahora es basura. Después de dos ciclos de bucle, hay dos cadenas antiguas que hacen un total de más de 100 KB de basura. Entonces, el comstackdor de lenguaje decide ejecutar su recolector de basura y libera esos 100 KB. El problema es que esto sucederá cada dos ciclos y el progtwig ejecutará su recolector de basura dos mil veces antes de leer la lista completa. Incluso con todo este trabajo, su uso de memoria será un gran múltiplo del tamaño de la lista.

Y al final:

Este problema no es exclusivo de Lua: otros lenguajes con recolección de basura real, y donde las cadenas son objetos inmutables, presentan un comportamiento similar, siendo Java el ejemplo más famoso. (Java ofrece la estructura StringBuffer para mejorar el problema.)

Las cuerdas de Python también son objetos inmutables .