Comment ajouter efficacement une chaîne à une autre en Python

En Python, la concaténation de chaînes avec l'opérateur « » est une tâche courante. Alors que le code suivant est simple :

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

Cela soulève des questions sur l'efficacité, en particulier pour les grandes chaînes ou les concaténations répétées.

Extension de chaîne sur place

Heureusement, CPython a mis en œuvre une optimisation pour améliorer l'efficacité de la concaténation de chaînes. Lorsqu'une seule référence à une chaîne existe et qu'une autre chaîne y est ajoutée, CPython tente d'étendre la chaîne d'origine en place. Cette optimisation rend l'opération amortie O(n).

Par exemple, le code suivant était O(n^2) :

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

Cependant, avec l'optimisation, il s'exécute désormais en O(n).

Détails d'implémentation de Python

Voici un extrait du code source Python C qui illustre l'optimisation :

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;
}

Cette fonction permet de redimensionner un objet chaîne, mais seulement s'il n'y a qu'une seule référence à celui-ci. La taille de la chaîne est modifiée tout en préservant l'emplacement mémoire d'origine.

Attention

Il est crucial de noter que cette optimisation ne fait pas partie de la spécification Python. Il est implémenté uniquement dans l'interpréteur CPython. D'autres implémentations Python, telles que PyPy ou Jython, peuvent présenter des caractéristiques de performances différentes.

Tests empiriques

Empiriquement, l'optimisation est évidente dans les performances du code suivant :

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)

Les résultats montrent une augmentation significative du temps d'exécution à mesure que le nombre de concaténations augmente, indiquant que l'optimisation n'est pas applicable aux chaînes plus grandes.

Conclusion

Bien que l'optimisation des extensions de chaînes sur place de Python améliore considérablement l'efficacité de la concaténation de chaînes dans certains scénarios, il est essentiel de comprendre les limites de cette implémentation. Pour les chaînes volumineuses ou lorsque les considérations de gestion de la mémoire sont primordiales, des méthodes alternatives de manipulation de chaînes peuvent être nécessaires pour obtenir des performances optimales.