Discussion :

[lg_53]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

[wiztricks]

Salut,

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[flapili]

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 () mais si le but est la performance pour de l'itération alors la boucle while est bien plus efficace qu'un for

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[lg_53]

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.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]

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

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.

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.

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