L'optimisation de la concaténation de chaînes de Python s'applique-t-elle aux grandes chaînes ?

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

En Python, concaténer des chaînes avec l'opérateur ' ' est une tâche courante. Alors que le code suivant est simple :

<code class="python">var1 = "foo"
var2 = "bar"
var3 = var1 + var2</code>

Il 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 implémenté 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) :

<code class="python">s = ""
for i in range(n):
    s += str(i)</code>

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

Détails d'implémentation de Python

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

<code class="c">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] = '<pre class="brush:php;toolbar:false"><code class="python">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)</code>

'; 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 :

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.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!