Performance boucle for

Version imprimable

Salut à tous

Petite question sur une mesure de performance.

Ce sur quoi je travaille : une liste d'éléments. Sur chacun des éléments, j'ai :
1) un traitement à faire
2) un test pour savoir si je dois appliquer par la suite un autre traitement à cet élément

Donc là tout de suite, 2 possibilités :
Soit je fais une boucle for et pour chaque élément je fais les 2 étapes, soit je fais en 2 passes (donc avec 2 boucles).

Et à mon plus grand étonnement, le code avec 2 boucles est plus performant ! ...
J'ai essayé avec ce code-exemple là :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 from time import time L = 100000 N = 100 def f1(L): liste=list(range(-L,L)) for i in range(len(liste)) : liste[i]*=2 to_treat = [] for elt in liste : if elt > 0 : to_treat.append(elt) return to_treat def f2(L): to_treat = [] liste=list(range(-L,L)) for i in range(len(liste)) : liste[i]*=2 elt = liste[i] if elt > 0 : to_treat.append(elt) return to_treat t0 = time() for _ in range(N): f1(L) t1 = time() for _ in range(N): f2(L) t2 = time() print("--- Exec time ---") print("1 for loop: ", t1-t0) print("2 for loops: ", t2-t1)
Sur ma machine ça donne :
Code:

1 2 3 4 5 6 7 8 9 10 11 --- Exec time --- 1 for loop: 3.3593356609344482 2 for loops: 3.650329828262329 --- Exec time --- 1 for loop: 3.362551689147949 2 for loops: 3.713728666305542 --- Exec time --- 1 for loop: 3.353935480117798 2 for loops: 3.6981289386749268
Sur un compilo en ligne (https://repl.it/languages/python3), la différence est pire meme :
Code:

1 2 3 4 5 6 7 --- Exec time --- 1 for loop: 18.116057634353638 2 for loops: 23.102251768112183 --- Exec time --- 1 for loop: 20.035600185394287 2 for loops: 26.916467428207397
Vu que cela donne pareil chez moi, et en ligne, j'en déduis que cela ne dépends pas de ma machine (mais je vous invite à tester aussi si vous le voulez bien pour confirmer).
Là où est la question, c'est que je me serais attendu à ce qu'un double passage soit plus couteux qu'un simple passage... Une explication ?

Salut,

Citation:

Envoyé par lg_53

Là où est la question, c'est que je me serais attendu à ce qu'un double passage soit plus couteux qu'un simple passage... Une explication ?

La grosse différence est dans la création de la variable locale "elt" et l'assignation de L[i]. Dans un cas, c'est fait dans le code C qui emballe for elt in liste:, dans l'autre, par l'instruction Python elt = liste[i].

Après vous pouvez dire qu'avez une seule boucle vous avez 2*L itérations alors que dans le deuxième cas vous en avez 2*L + 2*L = 4*L et donc "logiquement" 2 fois plus de boulot = 2 fois plus de temps.

Mais, il faut déjà peser le truc à vide:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def f1(L): liste=list(range(-L,L)) ## for i in range(len(liste)) : ## liste[i]*=2 to_treat = [] for elt in liste : ## if elt > 0 : pass ## to_treat.append(elt) return to_treat def f2(L): to_treat = [] liste=list(range(-L,L)) for i in range(len(liste)) : ## liste[i]*=2 elt = liste[i] ## if elt > 0 : ## pass ## to_treat.append(elt) return to_treat
La différence n'est pas de 10% mais de 100%.
Donc une boucle après l'autre, c'est plus lent mais pas assez pour combler le coût de elt = liste[i].

- W

Bonjour,

alors je vais sans doute répondre à coté de la plaque puisque ce code là ne doit être qu'une démo et le traitement doit être moins évident que juste liste[i]*=2 mais pourquoi ne pas construire directement une liste avec les bonne valeurs ? évitant une première itération.

alors cette fois je vais moins être à coté de la plaque (:aie:) mais si le but est la performance pour de l'itération alors la boucle while est bien plus efficace qu'un for
Code:

1 2 3 4 5 6 7 C:\Users\DEVEAUX>python -m timeit -s "n=100000" "for _ in range(n): pass" 200 loops, best of 5: 1.98 msec per loop C:\Users\DEVEAUX>python -m timeit -s "n=100000;i=0" "while i < n-1: i+=1" 5000000 loops, best of 5: 87.8 nsec per loop # sur Python 3.7.1 (v3.7.1:260ec2c36a, Oct 20 2018, 14:57:15) [MSC v.1915 64 bit (AMD64)] on win32
edit: le temps explose à partir de n=1000000 à n=10000000 d'un ordre de grandeur de x10^7, mais est d'exactement x10 quand on passe de n=10000000 à n=100000000 :arf:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 C:\Users\DEVEAUX>python -m timeit -s "n=1000000;i=0" "for _ in range(n): pass" 20 loops, best of 5: 19.8 msec per loop C:\Users\DEVEAUX>python -m timeit -s "n=1000000;i=0" "while i < n-1: i+=1" 1000000 loops, best of 5: 215 nsec per loop C:\Users\DEVEAUX>python -m timeit -s "n=10000000;i=0" "for _ in range(n): pass" 1 loop, best of 5: 198 msec per loop C:\Users\DEVEAUX>python -m timeit -s "n=10000000;i=0" "while i < n-1: i+=1" 1 loop, best of 5: 1.25 sec per loop C:\Users\DEVEAUX>python -m timeit -s "n=100000000;i=0" "while i < n-1: i+=1" 1 loop, best of 5: 12.6 sec per loop
bon histoire de repartir à coté de la plaque pourquoi ne pas utiliser numpy :aie:

Citation:

Envoyé par wiztricks

Après vous pouvez dire qu'avez une seule boucle vous avez 2*L itérations alors que dans le deuxième cas vous en avez 2*L + 2*L = 4*L et donc "logiquement" 2 fois plus de boulot = 2 fois plus de temps.

J'aurais pas forcément dit 2 fois plus de temps car le traitement sur chaque itération est moins couteux si on fait 4*L itérations plutot que 2*L. De prime abord, je me disais le coût des 2*L gros traitements est équivalent au coût des 4*L petits traitements, et donc les 4*L petits traitements vont être plus couteux car il va falloir y ajouter le coût de la boucle for supplémentaire.
D'après ce que je vois, là où je me trompais c'est justement dans l'équivalence des couts des traitements que je supposais au départ, car c'est traitement ne sont finalement pas exactement les mêmes, de par l'instruction elt = liste[i] en effet.

Citation:

Envoyé par wiztricks

Mais, il faut déjà peser le truc à vide:

J'ai plutot testé comme cela pour f1 à vide (avec déjà 2 boucles for)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 def f1(L): liste=list(range(-L,L)) for i in range(len(liste)) : pass ## liste[i]*=2 to_treat = [] for elt in liste : ## if elt > 0 : pass ## to_treat.append(elt) return to_treat
et effectivement on voit bien que le coût de 2 boucles est moins important que 1 boucle + l'instruction elt = liste[i]

Citation:

Envoyé par wiztricks

Donc une boucle après l'autre, c'est plus lent mais pas assez pour combler le coût de elt = liste[i]

Merci, c'est exactement ça l'argument à côté duquel je suis passé.

Citation:

Envoyé par flapili

alors je vais sans doute répondre à coté de la plaque puisque ce code là ne doit être qu'une démo et le traitement doit être moins évident que juste liste[i]*=2 mais pourquoi ne pas construire directement une liste avec les bonne valeurs ? évitant une première itération.

Oui c'est exactement ça. Là c'est un exemple bateau avec une liste d'int. En fait ce que j'ai, c'est une liste d'objet. Le premier traitement modifie un attribut (un réel). Ensuite le second traitement, n'est effectué que si l'attribut modifié par le premier traitement dépasse un certain seuil. A noter que je ne peux pas faire le second traitement sans connaitre l'ensemble des objets à traiter, d'où le passage par une liste to_treat, plutot que d'appliquer directement le second traitement.

Citation:

Envoyé par flapili

alors cette fois je vais moins être à coté de la plaque () mais si le but est la performance pour de l'itération alors la boucle while est bien plus efficace qu'un for

Très bonne précision, car effectivement je ne m'étais jamais posé cette question ! Après là comme je ne sais pas à l'avance combien je vais faire d'itération (ca fait partie des inputs), et que potentiellement ca va être grand, je vais garder mes boucles for, plutot que mettre des whiles. D'autant plus que mes traitements sont assez couteux et que cette amélioration qui me ferait perdre un peu de lisibilité, apporterais un gain de temps de calcul assez négligeable au regards des autres centres de coût. Mais je retiens l'argument, car il me servira c'est sûr.

Citation:

Envoyé par flapili

bon histoire de repartir à coté de la plaque pourquoi ne pas utiliser numpy

J'utilise déjà, à l'intérieur de mes objets. Après pour stocker l'ensemble des objets c'est pas vraiment adapté dans la mesure où des objets sont créés et d'autres détruits au cours de la simulation (donc il faudrait tout le temps changer la taille de l'array)

Merci pour vos retours