speed La chaîne Python 'rejoindre' est plus rapide(?) Que '+', mais qu'est-ce qui ne va pas ici?




speed up python code execution (9)

J'ai demandé la méthode la plus efficace pour la concaténation de chaînes dynamiques de masse dans un article précédent et j'ai suggéré d'utiliser la méthode de jointure , la méthode la meilleure, la plus simple et la plus rapide (comme tout le monde le disait). Mais pendant que je jouais avec des concaténations de cordes, j'ai trouvé des résultats bizarres (?). Je suis sûr que quelque chose se passe mais je ne peux pas le comprendre. Voici ce que j'ai fait:

J'ai défini ces fonctions:

import timeit
def x():
    s=[]
    for i in range(100):
        # Other codes here...
        s.append("abcdefg"[i%7])
    return ''.join(s)

def y():
    s=''
    for i in range(100):
        # Other codes here...
        s+="abcdefg"[i%7]
    return s

def z():
    s=''
    for i in range(100):
        # Other codes here...
        s=s+"abcdefg"[i%7]
    return s

def p():
    s=[]
    for i in range(100):
        # Other codes here...
        s+="abcdefg"[i%7]
    return ''.join(s)

def q():
    s=[]
    for i in range(100):
        # Other codes here...
        s = s + ["abcdefg"[i%7]]
    return ''.join(s)

J'ai essayé de garder d'autres choses (sauf la concaténation) presque identiques dans toutes les fonctions. Ensuite, j'ai testé avec les résultats suivants dans les commentaires (en utilisant Python 3.1.1 IDLE sur une machine Windows 32 bits):

timeit.timeit(x) # 31.54912480500002
timeit.timeit(y) # 23.533029429999942 
timeit.timeit(z) # 22.116181330000018
timeit.timeit(p) # 37.718607439999914
timeit.timeit(q) # 108.60377576499991

Cela signifie que strng = strng + dyn_strng est le plus rapide. Bien que la différence de temps ne soit pas si importante (sauf la dernière), je veux savoir pourquoi cela se produit. Est-ce parce que j'utilise Python 3.1.1 et que «+» est le plus efficace? Dois-je utiliser «+» comme alternative pour rejoindre ? Ou ai-je fait quelque chose d'extrêmement stupide? Ou quoi? S'il vous plaît expliquer clairement.


Je pense que certains d'entre nous, en particulier Rigo et Hettinger, se sont mis en quatre pour tenter d'optimiser certains cas particuliers de ce qui se passait trop souvent. a été prouvé que les débutants ne seront jamais convaincus que ''.join est la bonne voie à suivre et la lenteur horrible du += pourrait donner un mauvais nom à Python. D'autres d'entre nous n'étaient pas si chauds, car ils ne pouvaient tout simplement pas optimiser chaque événement (ou même la majorité d'entre eux) pour obtenir des performances décentes; mais nous ne nous sommes pas sentis assez en forme pour essayer de les bloquer activement.

Je crois que ce fil prouve que nous aurions dû les opposer plus sévèrement. Comme c'est le cas actuellement, ils ont optimisé += dans un certain sous-ensemble de cas difficiles à prédire, où il peut être 20% plus rapide pour des cas stupides particuliers que la manière correcte (qui est toujours ''.join ) - juste un moyen idéal pour piéger les débutants dans la poursuite de ces gains non pertinents de 20% en utilisant le mauvais idiome ... au prix d'une perte de performance de 200% (de temps en temps et de leur point de vue) , étant donné que le comportement non linéaire se cache toujours à l'extérieur des coins que Hettinger et Rigo ont mis en place et y ont mis des fleurs ;-) - un que QUESTIONS, un qui les rendra misérable. Cela va à l'encontre du principe de Python, "idéalement, une seule façon évidente de le faire" et il me semble que, collectivement, nous avons piégé les débutants - le meilleur aussi ... ceux qui n'acceptent pas seulement ce qu'ils racontent par leurs "parieurs", mais irrésistiblement aller interroger et explorer.

Ah bien - j'abandonne. OP, @ mshsayem, allez-y, utilisez + = partout, profitez de vos accélérations inutiles de 20% dans des cas insignifiants, minuscules et sans importance, et vous feriez mieux de les apprécier au maximum - parce qu'un jour, quand vous ne pouvez pas le voir À venir, lors d'une opération importante et de grande envergure, vous serez frappé de plein fouet par le camion de remorquage venant en sens inverse d'un ralentissement de 200% (à moins que vous ne soyez malchanceux et qu'il soit de 2000% ;-). Rappelez-vous simplement: si vous sentez que "Python est terriblement lent", RAPPELEZ-VOUS, plus probable que ce serait une de vos boucles bien-aimées de += se retourner et mordre la main qui le nourrit.

Pour nous tous - ceux qui comprennent ce que cela signifie de dire Nous devrions oublier les petites efficacités, disons environ 97% du temps , je continuerai à recommander avec enthousiasme. SACHEZ que nous ne serons pas frappés par un ralentissement superlinéaire lorsque nous nous y attendons le moins et que le moins que nous pouvons nous permettre. Mais pour vous, Armin Rigo et Raymond Hettinger (les deux derniers, chers amis personnels, BTW, pas seulement les co-responsables ;-) - que votre += soit lisse et que vos big-O ne soient jamais pire que N! - )

Donc, pour le reste d'entre nous, voici un ensemble de mesures plus significatives et intéressantes:

$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 's="".join(r)'
1000 loops, best of 3: 319 usec per loop

900 chaînes de 297 caractères chacune, rejoindre directement la liste est bien sûr plus rapide, mais l'OP est terrifié à l'idée de devoir faire des ajouts avant cette date. Mais:

$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 's=""' 'for x in r: s+=x'
1000 loops, best of 3: 779 usec per loop
$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 'z=[]' 'for x in r: z.append(x)' '"".join(z)'
1000 loops, best of 3: 538 usec per loop

... avec une quantité de données semi-importante (très peu de 100 Ko - en prenant une fraction mesurable d'une milliseconde), même un bon vieux .append est déjà supérieur. De plus, il est évident et facile à optimiser:

$ python -mtimeit -s'r=[str(x)*99 for x in xrange(100,1000)]' 'z=[]; zap=z.append' 'for x in r: zap(x)' '"".join(z)'
1000 loops, best of 3: 438 usec per loop

raser un dixième de milliseconde sur le temps de bouclage moyen. Tout le monde (au moins tous ceux qui sont totalement obsédés par la performance) sait évidemment que HOISTING (en sortant OUT de la boucle interne un calcul répétitif qui serait effectué de manière répétée) est une technique cruciale dans l'optimisation - Python ne hisserait pas pour vous , vous devez donc faire votre propre levage dans les rares occasions où chaque microseconde compte.


Quant à pourquoi q est beaucoup plus lent: quand vous dites

l += "a"

vous ajoutez la chaîne "a" à la fin de l , mais quand vous dites

l = l + ["a"]

vous créez une nouvelle liste avec le contenu de l et ["a"] , puis vous réaffectez les résultats à l . Ainsi, de nouvelles listes sont constamment générées.


La concaténation de chaînes était beaucoup plus lente avant Python 2.5, quand elle créait toujours une nouvelle copie pour chaque concaténation de chaîne plutôt que de l'ajouter à l'original, ce qui conduisait à rejoindre ().

Voici un ancien benchmark démontrant l'ancien problème: http://www.skymind.com/~ocrow/python_string/


Il y a déjà beaucoup de bons résumés, mais juste pour plus de preuves.

Source: J'ai regardé le code source de python pendant une heure et calculé les complexités!

Mes conclusions

Pour 2 cordes. (Supposons que n soit la longueur des deux chaînes)

Concat (+) - O(n)
Join       - O(n+k)  effectively O(n)
Format     - O(2n+k) effectively O(n)

Pour plus de 2 cordes. (Supposons que n soit la longueur de toutes les chaînes)

Concat (+) - O(n^2)
Join       - O(n+k)  effectively O(n)
Format     - O(2n+k) effectively O(n)

RÉSULTAT:

Si vous avez deux chaînes techniquement, la concaténation (+) est meilleure, bien qu'elle soit identique à la jointure et au format.

Si vous avez plus de deux cordes, concat devient terrible et la jointure et le format sont effectivement les mêmes, même si techniquement, rejoindre est un peu mieux.

RÉSUMÉ:

Si vous ne vous souciez pas de l'efficacité, utilisez l'un des éléments ci-dessus. (Bien que depuis que vous avez posé la question, je suppose que vous vous en souciez)

Donc -

Si vous avez 2 chaînes, utilisez concat (quand vous n'êtes pas en boucle!)

Si vous avez plus de deux chaînes (toutes les chaînes) (ou en boucle), utilisez

Si vous n'avez rien, les chaînes utilisent le format, parce que duh.

J'espère que cela t'aides!


J'ai trouvé la réponse à partir des réponses publiées ici par des experts. La concaténation de chaînes de Python (et les mesures de synchronisation) en dépend (pour autant que je sache):

  • Nombre de concaténations
  • Longueur moyenne des cordes
  • Nombre d'appels de fonction

J'ai construit un nouveau code qui les relie. Merci à Peter S Magnusson, à sepp2k, à hughdbrown, à David Wolever et à d'autres pour avoir indiqué des points importants que j'avais manqués plus tôt. En outre, dans ce code, j'ai peut-être manqué quelque chose. Donc, j'apprécie énormément les réponses indiquant nos erreurs, suggestions, critiques, etc. Après tout, je suis ici pour apprendre. Voici mon nouveau code:

from timeit import timeit

noc = 100
tocat = "a"
def f_call():
    pass

def loop_only():
    for i in range(noc):
        pass

def concat_method():
    s = ''
    for i in range(noc):
        s = s + tocat

def list_append():
    s=[]
    for i in range(noc):
        s.append(tocat)
    ''.join(s)

def list_append_opt():
    s = []
    zap = s.append
    for i in range(noc):
        zap(tocat)
    ''.join(s)

def list_comp():
    ''.join(tocat for i in range(noc))

def concat_method_buildup():
    s=''

def list_append_buildup():
    s=[]

def list_append_opt_buildup():
    s=[]
    zap = s.append

def function_time(f):
    return timeit(f,number=1000)*1000

f_callt = function_time(f_call)

def measure(ftuple,n,tc):
    global noc,tocat
    noc = n
    tocat = tc
    loopt = function_time(loop_only) - f_callt
    buildup_time = function_time(ftuple[1]) -f_callt if ftuple[1] else 0
    total_time = function_time(ftuple[0])
    return total_time, total_time - f_callt - buildup_time - loopt*ftuple[2]

functions ={'Concat Method\t\t':(concat_method,concat_method_buildup,True),
            'List append\t\t\t':(list_append,list_append_buildup,True),
            'Optimized list append':(list_append_opt,list_append_opt_buildup,True),
            'List comp\t\t\t':(list_comp,0,False)}

for i in range(5):
    print("\n\n%d concatenation\t\t\t\t10'a'\t\t\t\t 100'a'\t\t\t1000'a'"%10**i)
    print('-'*80)
    for (f,ft) in functions.items():
        print(f,"\t|",end="\t")
        for j in range(3):
            t = measure(ft,10**i,'a'*10**j)
            print("%.3f %.3f |" % t,end="\t")
        print()

Et voici ce que j'ai. [Dans la colonne d'heure, deux fois (mise à l'échelle) sont affichées: la première est la durée d'exécution totale de la fonction et la seconde est la concaténation réelle (?). J'ai déduit le temps d'appel de la fonction, le temps d'accumulation de la fonction (temps d'initialisation) et le temps d'itération. Ici, je considère un cas où il ne peut pas être fait sans boucle (dire plus de déclaration à l'intérieur).]

1 concatenation                 1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   2.310 2.168       |  2.298 2.156       |  2.304 2.162
Optimized list append   |   1.069 0.439       |  1.098 0.456       |  1.071 0.413
Concat Method           |   0.552 0.034       |  0.541 0.025       |  0.565 0.048
List append             |   1.099 0.557       |  1.099 0.552       |  1.094 0.552


10 concatenations                1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   3.366 3.224       |  3.473 3.331       |  4.058 3.916
Optimized list append   |   2.778 2.003       |  2.956 2.186       |  3.417 2.639
Concat Method           |   1.602 0.943       |  1.910 1.259       |  3.381 2.724
List append             |   3.290 2.612       |  3.378 2.699       |  3.959 3.282


100 concatenations               1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   15.900 15.758     |  17.086 16.944     |  20.260 20.118
Optimized list append   |   15.178 12.585     |  16.203 13.527     |  19.336 16.703
Concat Method           |   10.937 8.482      |  25.731 23.263     |  29.390 26.934
List append             |   20.515 18.031     |  21.599 19.115     |  24.487 22.003


1000 concatenations               1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   134.507 134.365   |  143.913 143.771   |  201.062 200.920
Optimized list append   |   112.018 77.525    |  121.487 87.419    |  151.063 117.059
Concat Method           |   214.329 180.093   |  290.380 256.515   |  324.572 290.720
List append             |   167.625 133.619   |  176.241 142.267   |  205.259 171.313


10000 concatenations              1'a'                  10'a'               100'a'
-------------------     ----------------------  -------------------  ----------------
List comp               |   1309.702 1309.560 |  1404.191 1404.049 |  2912.483 2912.341
Optimized list append   |   1042.271 668.696  |  1134.404 761.036  |  2628.882 2255.804
Concat Method           |   2310.204 1941.096 |  2923.805 2550.803 |  STUCK    STUCK
List append             |   1624.795 1251.589 |  1717.501 1345.137 |  3182.347 2809.233

En résumé, j'ai pris ces décisions pour moi:

  1. Si vous avez une liste de chaînes disponible, la méthode de "jointure" de chaînes est la meilleure et la plus rapide.
  2. Si vous pouvez utiliser la compréhension de la liste, c'est le plus simple et le plus rapide.
  3. Si vous avez besoin de 1 à 10 concaténations (moyenne) avec des longueurs comprises entre 1 et 100, list append (ajouter une liste), «+» prend la même chose (presque, notez que les temps sont mis à l'échelle).
  4. L’ajout d’une liste optimisée semble très bon dans la plupart des cas.
  5. Lorsque #concatenation ou la longueur de la chaîne augmente, "+" prend de plus en plus de temps. Notez que, pour 10000 concaténations avec 100'a, mon PC est bloqué!
  6. Si vous utilisez list append et 'join' toujours, vous êtes en sécurité tout le temps (pointé par Alex Martelli).
  7. Mais dans certaines situations, par exemple, lorsque vous devez saisir des entrées utilisateur et imprimer le mot "Hello user's world!", Il est plus simple d'utiliser "+". Je pense que construire une liste et joindre pour ce cas comme x = input ("Entrez le nom d'utilisateur:") et x.join (["Hello", "le monde!"]) Est plus laid que "Hello% s's world!" "% x ou" Hello "+ x +" le monde "
  8. Python 3.1 a amélioré les performances de concaténation. Mais dans certaines implémentations comme Jython, «+» est moins efficace.
  9. L'optimisation prématurée est la racine de tous les maux (dire des experts). La plupart du temps, vous n'avez pas besoin d'optimisation. Donc, ne perdez pas de temps à aspirer à l'optimisation (à moins que vous n'écriviez un projet volumineux ou informatique où chaque micro / millième de seconde compte.
  10. Utilisez ces informations et écrivez de la manière qui vous plait en prenant les circonstances en considération.
  11. Si vous avez vraiment besoin d'optimisation, utilisez un profileur, trouvez les goulots d'étranglement et essayez de les optimiser.

Enfin, j'essaie d'apprendre plus profondément le python. Donc, il n'est pas rare qu'il y ait des erreurs (erreurs) dans mes observations. Alors, commentez cela et suggérez-moi si je prends une mauvaise route. Merci à tous d'avoir participé.


Intéressant: j'ai fait des tests où la taille de la chaîne change, et c'est ce que j'ai trouvé:

def x():
    x = "a" * 100
    s=[]
    for i in range(100):
        # Other codes here...
        s.append(x)
    return ''.join(s)

def z():
    x = "a" * 100
    s=''
    for i in xrange(100):
        # Other codes here...
        s=s+x
    return s

from timeit import timeit
print "x:", timeit(x, number=1000000)
print "z:", timeit(z, number=1000000)

Pour les chaînes de longueur 1 ( x = "a" * 1 ):

x: 27.2318270206
z: 14.4046051502

Pour les chaînes de longueur 100:

x: 30.0796670914
z: 21.5891489983

Et pour les chaînes de longueur 1000, exécutez le temps 100 000 fois au lieu de 1 000 000

x: 14.1769361496
z: 31.4864079952

Lequel, si ma lecture de Objects/stringobject.c est correcte, a du sens.

Il apparaît, en première lecture, que l'algorithme String.join (de côté) est:

def join(sep, sequence):
    size = 0
    for string in sequence:
        size += len(string) + len(sep)

    result = malloc(size)

    for string in sequence:
        copy string into result
        copy sep into result

    return result

Donc, cela nécessitera plus ou moins de pas O(S) (où S est la somme des longueurs de toutes les chaînes à joindre).


Cette question concerne vraiment les coûts. Nous allons jouer un peu vite et en vrac, en soustrayant les résultats dans des cas similaires. Vous pouvez décider vous-même s'il s'agit d'une méthode valide. Voici quelques cas de test de base:

import timeit
def append_to_list_with_join():
    s=[]
    for i in xrange(100):
        s.append("abcdefg"[i%7])
    return ''.join(s)

def append_to_list_with_join_opt():
    s=[]
    x = s.append
    for i in xrange(100):
        x("abcdefg"[i%7])
    return ''.join(s)

def plus_equals_string():
    s=''
    for i in xrange(100):
        s+="abcdefg"[i%7]
    return s

def plus_assign_string():
    s=''
    for i in xrange(100):
        s=s+"abcdefg"[i%7]
    return s

def list_comp_join():
    return ''.join(["abcdefg"[i%7] for i in xrange(100)])

def list_comp():
    return ["abcdefg"[i%7] for i in xrange(100)]

def empty_loop():
    for i in xrange(100):
        pass

def loop_mod():
    for i in xrange(100):
        a = "abcdefg"[i%7]

def fast_list_join():
    return "".join(["0"] * 100)

for f in [append_to_list_with_join, append_to_list_with_join_opt, plus_equals_string,plus_assign_string,list_comp_join, list_comp, empty_loop,loop_mod, fast_list_join]:
    print f.func_name, timeit.timeit(f)

Et voici ce qu'ils coûtent:

append_to_list_with_join 25.4540209021
append_to_list_with_join_opt 19.9999782794
plus_equals_string 16.7842428996
plus_assign_string 14.8312124167
list_comp_join 16.329590353
list_comp 14.6934344309
empty_loop 2.3819276612
loop_mod 10.1424356308
fast_list_join 2.58149394686

Tout d'abord, beaucoup de choses ont des coûts inattendus en python. append_to_list_with_join versus append_to_list_with_join_opt montre que même rechercher une méthode sur un objet a un coût non négligeable. Dans ce cas, la recherche de l'appendice est un quart du temps.

Ensuite, list_comp_join versus list_comp montre que join () est assez rapide: il faut environ 1,7 ou seulement 10% de l’heure de list_comp_join.

loop_mod montre que la plus grande partie de ce test consiste à configurer les données, quelle que soit la méthode de construction de chaîne utilisée. Par inférence, le temps pris pour "string = string +", "string + =" et la compréhension de la liste sont les suivants:

plus_equals_string = 16.78 - 10.14 = 6.64
plus_assign_string = 14.83 - 10.14 = 4.69
list_comp = 14.69 - 10.14 = 4.55

Donc, en ce qui concerne la question des OP, join () est rapide mais le temps de créer la liste sous-jacente, que ce soit avec des primitives de liste ou de compréhension de liste, est comparable à la création de chaîne avec des primitives de chaîne. Si vous avez déjà une liste, convertissez-la en chaîne avec join () - ce sera rapide.

Les timings que présente le PO indiquent que la construction de listes à l'aide d'opérateurs concaténés est lente. En revanche, l'utilisation de la compréhension de liste est rapide. Si vous devez créer une liste, utilisez une liste de compréhension.

Enfin, prenons trois des fonctions les plus proches de l'OP: quelle est la différence entre x, p et q? Simplifions un peu:

import timeit
def x():
    s=[]
    for i in range(100):
        s.append("c")

def p():
    s=[]
    for i in range(100):
        s += "c"

def q():
    s=[]
    for i in range(100):
        s = s + ["c"]

for f in [x,p,q]:
    print f.func_name, timeit.timeit(f)

Voici les résultats:

x 16.0757342064
p 87.1533697719
q 85.0999698984

Et voici le disassembly :

>>> import dis
>>> dis.dis(x)
  2           0 BUILD_LIST               0
              3 STORE_FAST               0 (s)

  3           6 SETUP_LOOP              33 (to 42)
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_CONST               1 (100)
             15 CALL_FUNCTION            1
             18 GET_ITER
        >>   19 FOR_ITER                19 (to 41)
             22 STORE_FAST               1 (i)

  4          25 LOAD_FAST                0 (s)
             28 LOAD_ATTR                1 (append)
             31 LOAD_CONST               2 ('c')
             34 CALL_FUNCTION            1
             37 POP_TOP
             38 JUMP_ABSOLUTE           19
        >>   41 POP_BLOCK
        >>   42 LOAD_CONST               0 (None)
             45 RETURN_VALUE
>>> dis.dis(p)
  2           0 BUILD_LIST               0
              3 STORE_FAST               0 (s)

  3           6 SETUP_LOOP              30 (to 39)
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_CONST               1 (100)
             15 CALL_FUNCTION            1
             18 GET_ITER
        >>   19 FOR_ITER                16 (to 38)
             22 STORE_FAST               1 (i)

  4          25 LOAD_FAST                0 (s)
             28 LOAD_CONST               2 ('c')
             31 INPLACE_ADD
             32 STORE_FAST               0 (s)
             35 JUMP_ABSOLUTE           19
        >>   38 POP_BLOCK
        >>   39 LOAD_CONST               0 (None)
             42 RETURN_VALUE
>>> dis.dis(q)
  2           0 BUILD_LIST               0
              3 STORE_FAST               0 (s)

  3           6 SETUP_LOOP              33 (to 42)
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_CONST               1 (100)
             15 CALL_FUNCTION            1
             18 GET_ITER
        >>   19 FOR_ITER                19 (to 41)
             22 STORE_FAST               1 (i)

  4          25 LOAD_FAST                0 (s)
             28 LOAD_CONST               2 ('c')
             31 BUILD_LIST               1
             34 BINARY_ADD
             35 STORE_FAST               0 (s)
             38 JUMP_ABSOLUTE           19
        >>   41 POP_BLOCK
        >>   42 LOAD_CONST               0 (None)
             45 RETURN_VALUE

Les boucles sont presque identiques. La comparaison revient à CALL_FUNCTION + POP_TOP vs. INPLACE_ADD + STORE_FAST vs. BUILD_LIST + BINARY_ADD + STORE_FAST. Cependant, je ne peux pas donner une explication de plus bas niveau que cela - je ne peux tout simplement pas trouver les coûts des bytecodes de python sur le Net. Cependant, vous pourrez peut-être vous inspirer de l'affichage du module Python de la semaine de Doug Hellmann sur dis .


En plus de ce que les autres ont dit, 100 chaînes à 1 caractère sont vraiment petites . (Je suis un peu surpris que vous obteniez une séparation des résultats.) C'est le type de jeu de données qui rentre dans le cache de votre processeur. Vous n'allez pas voir une performance asymptotique sur un microbenchmark.


Je suppose que x () est plus lent parce que vous construisez d'abord le tableau et que vous le rejoignez ensuite. Donc, vous ne mesurez pas seulement le temps que prend la jointure, mais aussi le temps que vous prenez pour construire le tableau.

Dans un scénario où vous avez déjà un tableau et que vous souhaitez créer une chaîne à partir de ses éléments, la jointure doit être plus rapide que l'itération dans le tableau et la construction pas à pas de la chaîne.





performance