danielhagnoul

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
'''