script - speed up python code execution




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

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 .

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.


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.


Il y a une différence entre + = et + avec des chaînes - s'il n'y a pas d'autres références à "x", x + = y peut simplement être ajouté à x, plutôt que d'avoir à prendre une copie de la chaîne à ajouter - qui est la même avantage que vous obtenez en utilisant "" .join ().

Le principal avantage de "" .join () sur + ou + = est que join () doit toujours donner une performance linéaire, alors que dans de nombreux cas, + / + = donnera une performance quadratique (c.-à-d. quadrupler la quantité de temps pris). Mais cela ne sera important qu'avec beaucoup de texte, pas seulement 100 octets, et je pense que cela ne se déclenchera pas si vous n'avez qu'une seule référence à la chaîne à laquelle vous ajoutez.

En détail:

Votre meilleure performance en cas de concaténation de chaînes consiste à examiner chaque caractère de la chaîne finale une fois. "" .join () le fait naturellement - il a toutes les informations nécessaires dès le début.

Cependant, un + = b peut fonctionner de deux manières, il peut soit ajouter simplement "b" à une chaîne existante, auquel cas il suffit de regarder les caractères dans "b", ou il doit regarder les caractères " a "aussi.

En C, strcat () regarde toujours tous les caractères des deux chaînes, donc ça fonctionne toujours mal. En Python, cependant, la longueur de la chaîne est stockée, donc la chaîne peut être étendue tant qu’elle n’est pas référencée ailleurs - et vous obtenez de bonnes performances en ne copiant que les caractères dans "b". S'il est référencé ailleurs, python fera d'abord une copie de "a", puis ajoutera "b" à la fin, ce qui vous donnera de mauvaises performances. Si vous ajoutez cinq cordes de cette manière, votre temps sera:

ab = a+b       # Time is a + b
abc = ab+c     # Time is (a+b) + c
abcd = abc+d   # Time is (a+b+c) + d
abcde = abcd+e # Time is (a+b+c+d) + e

qui si a, b, c, d, e ont tous à peu près la même taille, disons n, est n * (n-1) / opérations 2-1, ou essentiellement n-carré.

Pour obtenir le mauvais comportement de x + = y, essayez:

def a(n=100):
    res = ""
    for k in xrange(n):
        v=res
        res += "foobar"
    return res

Même si v n'est pas réellement utilisé, il suffit de déclencher le chemin plus lent pour + = et d'obtenir le mauvais comportement qui inquiète les gens.

Je crois que + = n'a pas été introduit jusqu'à Python 2.0, il n'était donc pas possible d'ajouter efficacement sans utiliser quelque chose comme "" .join () dans Python 1.6 et versions antérieures.


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).


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.


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.


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.


Vous mesurez deux opérations distinctes: la création d'un tableau de chaînes et la concaténation de chaînes.

    import timeit
    def x():
        s = []
        for i in range(100):
            s.append("abcdefg"[i%7])
        return ''.join(s)
    def y():
        s = ''
        for i in range(100):
            s += "abcdefgh"[i%7]

    # timeit.timeit(x) returns about 32s
    # timeit.timeit(y) returns about 23s

De ce qui précède, il semblerait en effet que «+» est une opération plus rapide que la jointure. Mais considérez:

    src = []
    def c():
        global src
        s = []
        for i in range(100):
            s.append("abcdefg"[i%7])
        src = s
    def x2():
        return ''.join(src)
    def y2():
        s = ''
        for i in range(len(src)):
            s += src[i]
        return s

    # timeit.timeit(c) returns about 30s
    # timeit.timeit(x2) returns about 1.5s
    # timeit.timeit(y2) returns about 14s

En d'autres termes, en chronométrant x () vs y (), votre résultat est pollué par la construction de votre tableau source. Si vous annulez cela, vous trouvez que la jointure est plus rapide.

De plus, vous travaillez avec de petits tableaux, et vos numéros de synchronisation coïncident. Si vous augmentez la taille du tableau et la longueur de chaque chaîne de manière significative, les différences sont plus claires:

   def c2():
       global src
       s = []
       for i in range(10000):
           s.append("abcdefghijklmnopqrstuvwxyz0123456789"
       src = s

   # timeit.timeit(x2, number=10000) returns about 1s
   # timeit.timeit(y2, number=10000) returns about 80s




performance