[Toutes versions] amelioré une boucle de calcule

[kevin123]

Bonjour le forum,
pouvez vous m'aide a trouve une formule ou une methode pour rendre cette boucle plus rapide,merci d'avance pour vos reponses.

Code :

1
2
3
4
5
6
7
 nx=1530259 
p1 = 211876: p2 = 17296: p3 = 1081: p4 = 46 
s1 = 1: s2 = 2: s3 = 3: s4 = 4: s5 = 4 
st1: If nx > p1 Then nx = nx - p1: p1 = p1 - p2: p2 = p2 - p3: p3 = p3 - p4: p4 = p4 - 1: s1 = s1 + 1: s2 = s2 + 1: s3 = s3 + 1: s4 = s4 + 1: s5 = s5 + 1: GoTo st1
 st2: If nx > p2 Then nx = nx - p2: p2 = p2 - p3: p3 = p3 - p4: p4 = p4 - 1: s2 = s2 + 1: s3 = s3 + 1: s4 = s4 + 1: s5 = s5 + 1: GoTo st2
 st3: If nx > p3 Then nx = nx - p3: p3 = p3 - p4: p4 = p4 - 1: s3 = s3 + 1: s4 = s4 + 1: s5 = s5 + 1: GoTo st3
 st4: If nx > p4 Then nx = nx - p4: p4 = p4 - 1: s4 = s4 + 1: s5 = s5 + 1: GoTo st4

[jfontaine]

Bonjour,

J'utiliserais une boucle do While plutôt que des goto
Et pour une meilleur lisibilité, travail la mise en forme du code

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
nx = 1530259
p1 = 211876
p2 = 17296
p3 = 1081
p4 = 46
s1 = 1
s2 = 2
s3 = 3
s4 = 4
s5 = 4
 
Do While nx > p1
    nx = nx - p1
    p1 = p1 - p2
    p2 = p2 - p3
    p3 = p3 - p4
    p4 = p4 - 1
    s1 = s1 + 1
    s2 = s2 + 1
    s3 = s3 + 1
    s4 = s4 + 1
    s5 = s5 + 1
Loop
 
Do While nx > p2
    nx = nx - p2
    p2 = p2 - p3
    p3 = p3 - p4
    p4 = p4 - 1
    s2 = s2 + 1
    s3 = s3 + 1
    s4 = s4 + 1
    s5 = s5 + 1
Loop

[kevin123]

merci beaucoup pour votre reactivité,mais j'ai dejas essayé cette methode.
en terme de vitesse c'est pas encore ça!

[orpheu]

Bonjour,

Comme le suggère jlfontaine, le fait de 'boucler' au lieu de revenir par goto rend le code plus intelligible... mais malheureusement ne risque pas d'améliorer le temps d'exécution .

Le temps d'exécution va dépendre essentiellement du nombre d'opérations et d'affectations réalisées, et je ne vois pas trop où se situerait le gain.

Il faudrait essayer de transformer la logique de ton traitement et le choix des variables. Tu es le mieux placé pour ça.

A priori, tu pourrais essayer de ne faire que compter le nombre de fois où tu reviens sur chacun des tests, puis ensuite faire les soustractions en une seule opération, du moins pour les si. Pour le reste, c'est un peu un casse-tête, mais, il faudrait voir si les décrémentations successives de p1,p2,etc ne peuvent pas être traduites globalement par une formule sur les résultats (on a des suites récurrentes, en fait).

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
n=0
Do While nx > p1
    nx = nx - p1
    p1 = p1 - p2
    p2 = p2 - p3
    p3 = p3 - p4
    p4 = p4 - 1
   n=n+1
Loop
s1=s1+n
s2=s2+n
s3=s3+n
s4=s4+n
s4=s4+n

[orpheu]

Je continue: dans le précédent post j'indiquais comment supprimer les incrémentations des si

si tu conserves les valeurs initiales des Pi, par exemple Q1,Q2,Q3,Q4
tu admets facilement qu' à la fin de la boucle, P4 =Q4-n

sous la forme d'un suite: P4(0)=Q4, P4(1)=P4(0)-1=Q4-1, P4(2)=P4(1)-1=Q4-2, ...
on peut écrire P4(n)=p4(0)-n et donc P4=Q4-n
( pour tester ton algorithme, tu conserves le calcul initial afin de comparer à la sortie, et dans un premier temps on utilise Q4 tant que P4 varie)

donc en fin de boucle on peut calculer P4...
A ce stade on ne peut pas enlever la ligne P4=P4-1 car tu t'en sers dans les autres calculs (P3=P3-P4)

Mais si on peut calculer P3 sans calculer P4 à chaque fois, tu peux supprimer une instruction dans la boucle.

P3(n)=p3(n-1)-P4(n-1)
p3(n)=p3(n-2)-p4(n-2)-p4(n-1)
à la fin de la boucle:
p3(n)=p3(0) - Somme(i=1 à n-1)[p4(i)]

Somme(i=1 à n-1) [P4(i)]= p4(1) + ... P4(n-1)
= (p4(0)-1) + (p4(0)-2) + (p4(0)-3) + ... + (p4(0) - (n-1))
= n*p4(0) - (1 +2+...+(n-1))

On peut calculer en une instruction la somme (1+2+...+n):
si n est pair, c'est n*(n+1)/2
sinon c'est n+ (n*(n-1)/2)

donc ici, en allant jusqu'à (n-1):
P3(n)= p3(0) - (n-1)*p4(0) + S
si n= est pair : S= n*(n-1)/2
sinon: S= (n-1)+ (n-1)*(n-2)/2

Je crois donc que tu peux calculer P1,P2,P3,P4 à tout moment, selon n

Finalement: dans ta boucle tu conserves simplement le calcul de n, puis de P1(n), puis de nx, afin de pouvoir faire le test... et à la sortie tu calcules tous les autres paramètres.

J'ai voulu tester le calcul de P3 mais il y a une petite erreur : il faut certainement réfléchir un peu à la position de (n=n+1) dans la boucle (avant ou après les calculs), pour savoir de façon rigoureuse si c'est n ou n-1 la limite des sommes récurrentes... En tout cas le principe est d'écrire ça sous forme de suites et de transformer les 'Sommes de 1 à n' en formules ...

[orpheu]

Je pensais m'arrêter là, mais je suis vraiment un vrai malade. Ton problème m'excite... j'ai donc voulu finir le premier test.

En fait la formule pour calculer P3 est bien:
si n est pair:
P3=Q3 - n*Q4 + n*(n-1)/2
si n est impair:
P3=Q3 - n*Q4 +(n-1)+ (n-1)*(n-2)/2

Je te donne le code de mon test, pour la première boucle: sur la ligne 4 les résultats du calcul intitial, sur la ligne 5 les résultats du calcul, en sortant l'instruction P4=P4-1 et en remplaçant P3=P3-P4 par le calcul direct de P3 selon n

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
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
71
72
73
74
75
76
77
78
 
Public Sub test()
nx = 1530259
p1 = 211876: p2 = 17296: p3 = 1081: p4 = 46
q1 = 211876: q2 = 17296: q3 = 1081: q4 = 46
s1 = 1: s2 = 2: s3 = 3: s4 = 4: s5 = 4
Cells.Clear
 
Cells(1, 1) = "Nx"
Cells(1, 2) = "P1"
Cells(1, 3) = "P2"
Cells(1, 4) = "P3"
Cells(1, 5) = "P4"
Cells(1, 6) = "s1"
Cells(1, 7) = "s2"
Cells(1, 8) = "s3"
Cells(1, 9) = "s4"
Cells(1, 10) = "s5"
 
' le calcul initial
Do While nx > p1
    nx = nx - p1
    p1 = p1 - p2
    p2 = p2 - p3
    p3 = p3 - p4
    p4 = p4 - 1
    s1 = s1 + 1
    s2 = s2 + 1
    s3 = s3 + 1
    s4 = s4 + 1
    s5 = s5 + 1
Loop
Cells(4, 1) = nx
Cells(4, 2) = p1
Cells(4, 3) = p2
Cells(4, 4) = p3
Cells(4, 5) = p4
Cells(4, 6) = s1
Cells(4, 7) = s2
Cells(4, 8) = s3
Cells(4, 9) = s4
Cells(4, 10) = s5
 
' Le calcul réduit à P3
n=0
Do While nx > p1
    n = n + 1
    nx = nx - p1
    p1 = p1 - p2
    p2 = p2 - p3
'    p3 = p3 - p4
    If n Mod 2 = 0 Then
        p3 = q3 - n * q4 + (n * (n - 1) / 2)
    Else
        p3 = q3 - n * q4 + (n - 1) + ((n - 1) * (n - 2) / 2)
    End If
Loop
 
Cells(5, 1) = nx
Cells(5, 2) = p1
Cells(5, 3) = p2
Cells(5, 4) = p3
p4 = q4 - n
Cells(5, 5) = p4
s1 = s1 + n
s2 = s2 + n
s3 = s3 + n
s4 = s4 + n
s5 = s5 + n
Cells(5, 6) = s1
Cells(5, 7) = s2
Cells(5, 8) = s3
Cells(5, 9) = s4
Cells(5, 10) = s5
 
'... on obtient bien la même chose
 
End Sub

Voila, essaie de faire pareil avec P2, et ainsi de suite...

[kevin123]

bonjour orpheu,
merci beaucoup pour ton investissement ,j'ai pas tous bien comprie mais cela marche tres bien cordialement kevin.

[orpheu]

J'accepte tes remerciements, car c'est vrai que j'y ai consacré pas mal de temps... mais ce sont les joies de notre métier: des problèmes à régler... et le plaisir de trouver.

Tu me dis que ça marche, mais que tu n'as pas tout compris. Mais attention, tu n'auras des résultats sur le temps d'exécution final que si tu poursuis la démarche.

Dans la programmation, il faut parfois investir beaucoup de temps au départ pour en regagner à l'exécution.. à condition que le programme soit destiné à être exécuté, car sinon, il vaut mieux ne pas trop se casser la tête et laisser l'ordinateur travailler, le temps qu'il faut.

Donc, si tu souhaites poursuivre, et que tu n'y arrives pas, n'hésite pas à te manifester ici...