Python. Mesurer la vitesse d'exécution de deux codes
par
, 08/12/2019 à 22h02 (1724 Affichages)
Dans le commentaire d'un billet précédent : Python. PGCD de n nombres entiers, @bistouille a écritAu 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.Ce script est beaucoup trop lent, normal, car tu calcules tous les diviseurs de chaque nombres [...]
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 '''