Quelle est la lenteur de la concaténation des chaînes de Python par rapport à str.join?

Question

À la suite des commentaires dans ma réponse sur ce fil de discussion, je voulais savoir quelle est la différence de vitesse entre l'opérateur += et ''.join()

Alors, quelle est la comparaison de vitesse entre les deux ?

Answer 1

J'ai réécrit la dernière réponse, pouvez-vous partager votre opinion sur la façon dont j'ai testé ?

import time

start1 = time.clock()
for x in range (10000000):
    dog1 = ' and '.join(['spam', 'eggs', 'spam', 'spam', 'eggs', 'spam','spam', 'eggs', 'spam', 'spam', 'eggs', 'spam'])

end1 = time.clock()
print("Time to run Joiner = ", end1 - start1, "seconds")


start2 = time.clock()
for x in range (10000000):
    dog2 = 'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'+' and '+'spam'+' and '+'eggs'+' and '+'spam'

end2 = time.clock()
print("Time to run + = ", end2 - start2, "seconds")

NOTE : Cet exemple est écrit en Python 3.5, où range() se comporte comme l'ancien xrange()

Le résultat que j'ai obtenu :

Time to run Joiner =  27.086106206103153 seconds
Time to run + =  69.79100515996426 seconds

Personnellement, je préfère '' .join([]) à 'Plusser way' car il est plus propre et plus lisible.

Answer 2

Si j'attends bien, pour une liste avec k string, avec n caractères au total, la complexité temporelle de join devrait être O(nlogk) alors que la complexité temporelle de la concaténation classique devrait être O(nk).

Ce serait les mêmes coûts relatifs que la fusion de la liste triée k (la méthode efficace est O(nlkg), tandis que la méthode simple, semblable à la concaténation est O(nk) ).