Pourquoi ".join () plus rapide que + = en Python?
je suis en mesure de trouver une foule d'informations en ligne (sur le débordement de la pile et autres) sur la façon dont c'est une pratique très inefficace et mauvaise d'utiliser + ou += pour la concaténation en Python.
Je ne vois pas pourquoi += est si inefficace. En dehors d'une mention ici que "il a été optimisé pour l'amélioration de 20% dans certains cas" (toujours pas clair ce que ces cas sont), Je ne peux pas trouver d'informations supplémentaires.
que se passe-t-il à un niveau plus technique qui rend ''.join() supérieur aux autres méthodes de concaténation Python?
2 réponses
disons que vous avez ce code pour construire une chaîne à partir de trois chaînes:
x = 'foo'
x += 'bar' # 'foobar'
x += 'baz' # 'foobarbaz'
dans ce cas, Python doit d'abord allouer et créer 'foobar' avant de pouvoir allouer et créer 'foobarbaz' .
donc pour chaque += qui est appelé, tout le contenu de la chaîne et tout ce qui y est ajouté doivent être copiés dans un tampon mémoire entièrement nouveau. En d'autres termes, si vous avez N être joint, vous devez allouer environ N chaînes temporaires et la première chaîne est copiée ~n fois. La dernière sous-couche n'est copiée qu'une fois, mais en moyenne, chaque sous-couche est copiée ~N/2 fois.
avec .join , Python peut jouer un certain nombre de trucs puisque les chaînes intermédiaires n'ont pas besoin d'être créées. CPython calcule combien de mémoire il lui faut à l'avance, puis attribue un tampon de taille correcte. 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 pourraient conduire à de meilleures performances pour += dans certains cas. Par exemple: si la représentation de la chaîne interne est en fait une rope ou si l'exécution est suffisamment intelligente pour comprendre d'une manière ou d'une autre que les chaînes temporaires ne sont d'aucune utilité pour le programme et optimiser loin.
cependant, CPython fait certainement pas faire ces optimisations de manière fiable (bien qu'il puisse pour un quelques cas de coin ) et comme il s'agit de la mise en œuvre la plus commune dans l'utilisation, de nombreuses meilleures pratiques sont basées sur ce qui fonctionne bien pour CPython. Avoir un ensemble normalisé de normes rend également plus facile pour les autres implémentations de concentrer leurs efforts d'optimisation.
je pense que ce comportement est mieux expliqué dans chapitre tampon de chaîne de Lua .
pour réécrire cette explication dans le contexte de Python, commençons par un extrait de code innocent (dérivé de celui de Lua's docs):
s = ""
for l in some_list:
s += l
suppose que chaque l est de 20 octets et le s a déjà été interprété à une taille de 50 Ko. Quand Python concaténate s + l il crée une nouvelle chaîne avec 50 020 octets et copie 50 Ko de s dans cette nouvelle chaîne. C'est-à-dire, pour chaque nouvelle ligne, le programme déplace 50 KB de mémoire, et se développe. Après avoir lu 100 nouvelles lignes (seulement 2 KO), le snippet a déjà déplacé plus de 5 Mo de mémoire. Pour empirer les choses, après la mission
s += l
la vieille corde est maintenant une poubelle. Après deux cycles de boucle, il y a deux vieilles cordes qui font un total de plus de 100 Ko de déchets. Donc, le compilateur de langue décide de lancer son collecteur de déchets et libère ces 100 Ko. Le problème est que cela se produira tous les deux cycles et le programme exécutera son collecteur d'ordures deux mille fois avant de lire toute la liste. Même avec tout ce travail, son usage de mémoire sera un grand multiple de la taille de la liste.
et, à la fin:
ce problème n'est pas Particulier à Lua: D'autres langues avec de vraies ordures collection, et où les cordes sont immuables les objets, même comportement, Java étant l'exemple le plus célèbre. (Java offre la structure
StringBufferpour améliorer le problème.)
Python les cordes sont également des objets immuables .