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

simbolos en python

Question

Puedo 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 usar + o += para la concatenación en Python.

Parece que no puedo encontrar POR QUÉ += es tan ineficiente. Además de una mención here que "se ha optimizado para una mejora del 20% en ciertos casos" (todavía 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?

Answer 1

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

Para reescribir esa explicación en el contexto de Python, comencemos con un fragmento de código inocente (un derivado del que está en los documentos de Lua):

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

Suponga que cada l tiene 20 bytes y que s ya se ha analizado 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 programa 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 cuerda 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 compilador de idiomas decide ejecutar su recolector de basura y libera esos 100 KB. El problema es que esto sucederá cada dos ciclos y el programa 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 peculiar de Lua: otros lenguajes con verdadera recolección de basura, 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 cadenas de Python también son objetos inmutables .

Answer 2

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'' .

Entonces, para cada += que se llama, todo el contenido de la cadena y lo que sea que se agregue debe copiarse en un búfer de memoria completamente nuevo. En otras palabras, si tiene N cadenas para unir, debe 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 varios 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 rendimiento para += en algunos casos. Por ejemplo, si la representación de la cadena interna es realmente una rope o si el tiempo de ejecución es lo suficientemente inteligente como para descubrir de alguna manera que las cadenas temporales no son útiles para el programa y optimizarlas.

Sin embargo, CPython ciertamente no realiza estas optimizaciones de manera confiable (aunque puede hacerlo en algunos casos ) 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 facilita que otras implementaciones también enfoquen sus esfuerzos de optimización.