Voir le flux RSS

danielhagnoul

Python. Mesurer la vitesse d'exécution de deux codes

Noter ce billet
par , 08/12/2019 à 23h02 (526 Affichages)
Dans le commentaire d'un billet précédent : Python. PGCD de n nombres entiers, @bistouille a écrit
Ce script est beaucoup trop lent, normal, car tu calcules tous les diviseurs de chaque nombres [...]
Au premier abord, je me suis dit qu'il avait raison, car j'avais eu besoin de la fonction diviseurs() et je n'avais abouti à la fonction pgcd_n() qu'après, comme un bonus. N'ayant jamais mesuré la vitesse d'un code, je me suis dit que c'était le bon moment. Bien m'en a pris, pgcd_n() est plus rapide.

Le test consiste à tirer au sort, avec sample(), une liste de 50 chiffres entiers compris entre 100 et 1000. Pour cette liste, on répète 500 fois le calcul du PGCD par les deux méthodes. Je répète le test 50 fois avec une liste de 50 chiffres entiers différents. Je mesure le temps écoulé avec timeit(), on calcule mean() et stdev() avec le module statistics.

Malgré que pgcd_n() utilise diviseurs(), il n'y a pas photo sur le résultat.

Code Python : 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#! python3
# coding: utf-8
 
from termcolor import cprint
from typing import List
from random import sample
from itertools import combinations
from timeit import timeit
from statistics import mean, stdev
 
 
def pgcd(*values):
    def _pgcd(a, b):
        m = a % b
        while m:
            a, b = b, m
            m = a % b
        return b
    return min(_pgcd(a, b) for a, b in combinations(values, 2))
 
 
def diviseurs(a: int = 2, b: int = 2) -> List[int]:
    """Liste des diviseurs des nombres entiers a et b"""
    if a > 1 and b > 1:
        lst = []
        for n in range(min(a, b), 0, -1):
            if (a % n == 0) and (b % n == 0):
                lst.append(n)
        return lst
    else:
        raise Exception(
            'a et b doivent être des entiers supérieurs à 1')
 
 
def pgcd_n(int_list: List[int] = [40, 20]) -> int:
    """PGCD de 2..n nombres entiers supérieurs à 1"""
    if len(int_list) < 2:
        raise Exception('Il doit y avoir un minimum de deux nombres entiers')
    pgcd = 2
    while True:
        if len(int_list) >= 2 and pgcd > 1:
            a, b, *rest = int_list
            pgcd = diviseurs(a, b)[0]
            int_list = [pgcd, *rest]
        else:
            break
    return pgcd
 
 
if __name__ == "__main__":
    pgcd_list = []
    pgcd_n_list = []
 
    for _ in range(0, 50):
        lst = sample(range(100, 1001), 50)
        pgcd_list.append(
            timeit("pgcd(*lst)", setup="from __main__ import pgcd, lst", number=500))
        pgcd_n_list.append(
            timeit('pgcd_n(lst)', setup="from __main__ import pgcd_n, lst", number=500))
 
    cprint('''pgcd(), mean = {}, stdev = {}'''.format(
        mean(pgcd_list), stdev(pgcd_list)), 'green')
    cprint('''pgcd_n(), mean = {}, stdev = {}'''.format(
        mean(pgcd_n_list), stdev(pgcd_n_list)), 'green')
 
'''
PS F:\test-python> & C:/Users/User/AppData/Local/Programs/Python/Python37-32/python.exe f:/test-python/Tests/forum_dvp/a_test.py
pgcd(), mean = 0.37607896000000013, stdev = 0.00993170676340615
pgcd_n(), mean = 0.016110195999999945, stdev = 0.009435904633312115
'''

Bien entendu, si on transforme pgcd_n() pour calculer directement le PGCD sans passer par diviseurs(), c'est encore plus rapide.

Code Python : 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#! python3
# coding: utf-8
 
from termcolor import cprint
from typing import List
from random import sample
from itertools import combinations
from timeit import timeit
from statistics import mean, stdev
 
 
def pgcd(*values):
    def _pgcd(a, b):
        m = a % b
        while m:
            a, b = b, m
            m = a % b
        return b
    return min(_pgcd(a, b) for a, b in combinations(values, 2))
 
 
def pgcd_n(int_list):
    def _pgcd(a, b):
        m = a % b
        while m:
            a, b = b, m
            m = a % b
        return b
    pgcd = 2
    while True:
        if len(int_list) >= 2 and pgcd > 1:
            a, b, *rest = int_list
            pgcd = _pgcd(a, b)
            int_list = [pgcd, *rest]
        else:
            break
    return pgcd
 
 
if __name__ == "__main__":
    pgcd_list = []
    pgcd_n_list = []
 
    for _ in range(0, 50):
        lst = sample(range(100, 1001), 50)
        pgcd_list.append(
            timeit("pgcd(*lst)", setup="from __main__ import pgcd, lst", number=500))
        pgcd_n_list.append(
            timeit('pgcd_n(lst)', setup="from __main__ import pgcd_n, lst", number=500))
 
    cprint('''pgcd(), mean = {}, stdev = {}'''.format(mean(pgcd_list), stdev(pgcd_list)), 'green')
    cprint('''pgcd_n(), mean = {}, stdev = {}'''.format(mean(pgcd_n_list), stdev(pgcd_n_list)), 'green')
 
'''
PS F:\test-python> & C:/Users/User/AppData/Local/Programs/Python/Python37-32/python.exe f:/test-python/Tests/forum_dvp/b_test.py
pgcd(), mean = 0.37859707199999976, stdev = 0.01150420466413487
pgcd_n(), mean = 0.0013121060000002172, stdev = 0.0006107369691393413
'''

Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog Viadeo Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog Twitter Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog Google Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog Facebook Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog Digg Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog Delicious Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog MySpace Envoyer le billet « Python. Mesurer la vitesse d'exécution de deux codes » dans le blog Yahoo

Commentaires

  1. Avatar de bistouille
    • |
    • permalink
    Salut.

    Tu triches

    Déjà le fait de faire un test en passant 50 valeurs à la fonction désavantage évidemment combinations qui va faire 1225 appels à _pgcd. Puis faire des tests sur de petits nombres avantage aussi grandement ta fonction

    Il suffit de tester avec moins de nombres, des nombres plus grand et impairs.
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    lst = sample(range(10_001, 100_001, 2), 5)
    Et voilà malgré toutes les combinaisons c'est déjà beaucoup plus rapide qu'avec la fonction diviseurs. Et encore plus efficient en utilisant des nombres premiers.

    Ce qui est lent, c'est de tester autant de fois qu'il y a de combinaisons, O(n-1) vs O(2^n) (euh... si je ne me goure pas), alors il suffit de changer itertools.permutation par itertools.accumulate dans pgcd.
    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    return tuple(accumulate(values, _pgcd))[-1]

    Et là, c'est assez proche de ton second script avec le while