Cómo agregar eficientemente una cadena a otra en Python

En Python, concatenar cadenas con el operador '' es una tarea común. Si bien el siguiente código es sencillo:

var1 = "foo"
var2 = "bar"
var3 = var1   var2

Plantea dudas sobre la eficiencia, especialmente para cadenas grandes o concatenaciones repetidas.

Extensión de cadena in situ

Afortunadamente, CPython ha implementado una optimización para mejorar la eficiencia de la concatenación de cadenas. Cuando solo existe una única referencia a una cadena y se le agrega otra cadena, CPython intenta extender la cadena original en su lugar. Esta optimización hace que la operación se amortice O(n).

Por ejemplo, el siguiente código solía ser O(n^2):

s = ""
for i in range(n):
    s  = str(i)

Sin embargo, con la optimización, ahora se ejecuta en O(n).

Detalles de implementación de Python

Aquí hay un extracto del código fuente de Python C que ilustra la optimización:

int
_PyBytes_Resize(PyObject **pv, Py_ssize_t newsize)
{
    /* ... */
    *pv = (PyObject *)
        PyObject_REALLOC((char *)v, PyBytesObject_SIZE   newsize);
    if (*pv == NULL) {
        PyObject_Del(v);
        PyErr_NoMemory();
        return -1;
    }
    _Py_NewReference(*pv);
    sv = (PyBytesObject *) *pv;
    Py_SIZE(sv) = newsize;
    sv->ob_sval[newsize] = '\0';
    sv->ob_shash = -1;          /* invalidate cached hash value */
    return 0;
}

Esta función permite cambiar el tamaño de un objeto de cadena, pero solo si hay una sola referencia a él. El tamaño de la cadena se cambia conservando la ubicación de memoria original.

Precaución

Es crucial tener en cuenta que esta optimización no forma parte de la especificación de Python. Se implementa únicamente en el intérprete CPython. Otras implementaciones de Python, como PyPy o Jython, pueden exhibir diferentes características de rendimiento.

Pruebas empíricas

Empíricamente, la optimización es evidente en el rendimiento del siguiente código:

import timeit

s = ""
for i in range(10):
    s  = 'a'

# Time the concatenation of 10 'a' characters
t1 = timeit.timeit(stmt="""s = ""
for i in range(10):
    s  = 'a'""", globals=globals(), number=1000000)

# Time the concatenation of 100 'a' characters
t2 = timeit.timeit(stmt="""s = ""
for i in range(100):
    s  = 'a'""", globals=globals(), number=100000)

# Time the concatenation of 1000 'a' characters
t3 = timeit.timeit(stmt="""s = ""
for i in range(1000):
    s  = 'a'""", globals=globals(), number=10000)

print("10 'a':", t1)
print("100 'a':", t2)
print("1000 'a':", t3)

Los resultados muestran un aumento significativo en el tiempo de ejecución a medida que crece el número de concatenaciones, lo que indica que la optimización no es aplicable para cadenas más grandes.

Conclusión

Si bien la optimización de la extensión de cadenas in situ de Python mejora drásticamente la eficiencia de la concatenación de cadenas en ciertos escenarios, es esencial comprender las limitaciones de esta implementación. Para cadenas grandes o cuando las consideraciones de administración de memoria son primordiales, pueden ser necesarios métodos alternativos de manipulación de cadenas para lograr un rendimiento óptimo.