Pourquoi '' .join () est-il plus rapide que + = en Python?

Question

Je suis en mesure de trouver une foule d'information en ligne (sur un Débordement de Pile ou autre) sur la façon dont il est très inefficace et les mauvaises pratiques d'utilisation + ou += pour la concaténation en Python.

Je n'arrive pas à trouver POURQUOI += est donc inefficace. En dehors d'une mention ici que "il a été optimisé pour améliorer de 20% dans certains cas" (pas encore clairement quels sont ces cas), je ne trouve pas de renseignements supplémentaires.

Ce qui se passe sur un plan plus technique qui rend ''.join() supérieure à celle d'autres Python concaténation des méthodes?

Answer 1

Disons que vous avez ce code pour construire une chaîne de caractères à partir de trois chaînes:

x = 'foo'
x += 'bar'  # 'foobar'
x += 'baz'  # 'foobarbaz'

Dans ce cas, Python a d'abord besoin d'allouer et de créer 'foobar' avant d'allouer et de créer 'foobarbaz'.

Donc, pour chaque += qui est appelée, l'ensemble du contenu de la chaîne et tout ce qui est arriver, ajouté à cela doivent être copiés dans un tout nouveau mémoire tampon. En d'autres termes, si vous avez N cordes à être rejoint, vous avez besoin d'allouer environ N temporaire des chaînes et de la première sous-chaîne est copié ~N fois. La dernière sous-chaîne obtient seulement une fois copié, mais en moyenne, chaque sous-chaîne est copié ~N/2 temps.

Avec .join, Python peut jouer un certain nombre de tours depuis l'intermédiaire de chaînes n'ont pas besoin d'être créé. Disponible les chiffres de la mémoire dont il a besoin à l'avant et répartit correctement la taille de la mémoire tampon. Enfin, il copie ensuite chaque morceau dans le nouveau tampon, ce qui signifie que chaque pièce est seulement une fois copié.

---

Il existe d'autres approches viables qui pourrait conduire à de meilleures performances pour += dans certains cas. E. g. si la représentation de chaîne est en fait un rope ou si le moteur d'exécution est en fait assez intelligent pour en quelque sorte la figure que les chaînes temporaires sont d'aucune utilité pour le programme et de les optimiser à l'écart.

Cependant, Disponible certainement ne pas faire ces optimisations de manière fiable (même si ça peut un peu le coin des cas) et depuis c'est la plus commune de mise en œuvre en cours d'utilisation, de nombreuses bonnes pratiques sont basées sur ce qui fonctionne bien pour Disponible. Avoir un ensemble normalisé de normes rend également plus facile pour les autres implémentations de concentrer leurs efforts d'optimisation.

Answer 2

Je pense que ce comportement est mieux expliqué dans Lua dans la chaîne de mémoire tampon chapitre.

Réécrire cette explication dans le contexte de Python, nous allons commencer avec un innocent extrait de code (un dérivé de l'un à Arus docs):

s = ""
for l in some_list:
  s += l

Supposons que chaque l de 20 octets et l' s a déjà été analysée pour une taille de 50 KO. Quand Python concatène s + l il crée une nouvelle chaîne avec 50,020 octets et des copies de 50 KO de s dans cette nouvelle chaîne. C'est, pour chaque nouvelle ligne, le programme passe de 50 KO de mémoire, et de la croissance. Après la lecture de 100 nouvelles lignes (seulement 2 KO), l'extrait a déjà transporté plus de 5 MO de mémoire. Pour aggraver les choses, après la cession

s += l

la vieille chaîne est maintenant des ordures. Après deux cycles de boucle, il y a deux vieux cordes pour un total de plus de 100 KO de déchets. Ainsi, le compilateur de langage décide de faire de son garbage collector et libère les 100 KO. Le problème est que cela va se produire tous les deux cycles, et le programme va exécuter son garbage collector deux mille fois avant de lire la liste dans son ensemble. Même avec tout ce travail, son utilisation de la mémoire sera un multiple de la liste est de taille.

Et, à la fin:

Ce problème n'est pas propre à Lua: Autres langues avec une vraie poubelle collection, et où les chaînes de caractères sont des objets immuables, même comportement, Java étant l'exemple le plus célèbre. (Java offre la structure StringBuffer à atténuer le problème.)

Python les cordes sont également des objets immuables.