Quelle est l'efficacité de la concaténation de chaînes de Python et quand est-elle optimisée ?

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

Lors de l'ajout d'une chaîne à une autre chaîne, il est efficace de optimiser le fonctionnement, notamment pour les scénarios avec plusieurs concaténations. La méthode traditionnelle décrite dans la question, var3 = var1 var2, n'est pas toujours la plus efficace.

CPython Optimization

CPython, l'implémentation par défaut de Python, utilise une optimisation spécifique pour la concaténation de chaînes lorsqu'une seule référence à la chaîne initiale existe. Cette optimisation tente d'étendre la chaîne en place, ce qui entraîne une opération O(n) amortie. Cela signifie que pour des scénarios tels que :

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

qui étaient auparavant O(n^2), sont désormais beaucoup plus rapides, à O(n).

Détails de mise en œuvre

L'optimisation de CPython est implémentée dans la fonction _PyBytes_Resize dans bytesobject.c. Il réalloue la mémoire pour l'objet chaîne, augmentant sa taille de la quantité spécifiée. En cas de succès, il met à jour la taille de la chaîne et définit un octet nul final pour terminer la chaîne.

Vérification empirique

Pour démontrer cette optimisation de manière empirique, considérez ce qui suit timeit résultats :

$ python -m timeit -s"s=''" "for i in xrange(10):s+='a'"
1000000 loops, best of 3: 1.85 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(100):s+='a'"
10000 loops, best of 3: 16.8 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000):s+='a'"
10000 loops, best of 3: 158 usec per loop
$ python -m timeit -s"s=''" "for i in xrange(10000):s+='a'"
1000 loops, best of 3: 1.71 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(100000):s+='a'"
10 loops, best of 3: 14.6 msec per loop
$ python -m timeit -s"s=''" "for i in xrange(1000000):s+='a'"
10 loops, best of 3: 173 msec per loop

Pour les chaînes plus petites, la surcharge est minime, mais à mesure que la taille de la chaîne augmente, l'approche optimisée devient nettement plus efficace.

Attention

> ;

Il est important de noter que cette optimisation ne fait pas partie de la spécification Python. Il s'agit d'un détail d'implémentation spécifique de CPython et peut ne pas être présent dans d'autres implémentations Python comme PyPy ou Jython.

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!