Como anexar com eficiência uma string a outra em Python

Em Python, concatenar strings com o operador ' ' é uma tarefa comum. Embora o código a seguir seja simples:

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

Isso levanta questões sobre eficiência, especialmente para strings grandes ou concatenações repetidas.

Extensão de string no local

Felizmente, CPython implementou uma otimização para aumentar a eficiência da concatenação de strings. Quando existe apenas uma única referência a uma string e outra string é anexada a ela, o CPython tenta estender a string original no lugar. Essa otimização faz com que a operação seja amortizada O(n).

Por exemplo, o código a seguir costumava ser O(n^2):

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

No entanto, com a otimização, ele agora é executado em O(n).

Detalhes de implementação do Python

Aqui está um trecho do código-fonte Python C que ilustra a otimização:

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 função permite o redimensionamento de um objeto string, mas somente se houver apenas uma referência a ele. O tamanho da string é alterado preservando a localização original da memória.

Cuidado

É crucial observar que essa otimização não faz parte da especificação Python. É implementado apenas no interpretador CPython. Outras implementações Python, como PyPy ou Jython, podem apresentar características de desempenho diferentes.

Testes Empíricos

Empiricamente, a otimização é evidente no desempenho do seguinte 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)

Os resultados mostram um aumento significativo no tempo de execução à medida que o número de concatenações aumenta, indicando que a otimização não é aplicável para strings maiores.

Conclusão

Embora a otimização da extensão de string no local do Python melhore drasticamente a eficiência da concatenação de strings em determinados cenários, é essencial entender as limitações dessa implementação. Para strings grandes ou quando as considerações de gerenciamento de memória são fundamentais, métodos alternativos de manipulação de strings podem ser necessários para alcançar o desempenho ideal.