Optimiser le code ->Systeme de combinaison

Version imprimable

Voici le 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
35
36
37
38
39
40
41
42
43
 
Dim total1 As String
 
Public Function Komb1(ByVal tableau, ByVal Prefixe As String, ByVal min As Integer, ByVal max As Integer, ByVal n As Integer) As String
    Dim i As Integer
    Dim Resultat As String
 
    For i = min To max - n + 1
        If Prefixe = "-1" Then
            Resultat = tableau(i)
        Else
            Resultat = Prefixe & "*" & tableau(i)
        End If
 
        If n > 1 Then
            Komb1 tableau, Resultat, i + 1, max, n - 1
        Else
            If total1 = vbNullString Then
                total1 = Resultat
            Else
                total1 = total1 & "+" & Resultat
            End If
        End If
    Next
 
    Komb1 = total1
End Function
 
Sub Main()
 
    Dim tableau() As Variant
    Dim max As Integer
    Dim min As Integer
    max =4 
    min = 3
 
    ReDim tableau(0 To max - 1)
    For i = 1 To max
        tableau(i - 1) = Chr(64 + i)
    Next i
 
    MsgBox Komb1(tableau, -1, 0, max - 1, min)
end sub

Le resultat final est : A*B*C+A*B*D+A*B*E+A*C*D+A*C*E+A*D*E+B*C*D+B*C*E+B*D*E+C*D*E
donc 10 combinaisons

Mon probleme est que si je demande combinaison de 6/16 j'ai 8008 combinaisons, cela met beaucoup trop de temps.

Comment puis je optimiser mon code ? Au maxi j'aurais 16 elements

Merci de votre aide.

01/10/2006, 01h02
Delbeke

J'ai un peu de mal a suivre, Kom1 est recurent. Ce que je sais, c'est que tu as utilisé les types de variable lel plus lent que vb puisse traiter : les variants et pire encore les strings.
Je ne sais si ton algo pourrait fonctionner avec des entiers, mais si oui, aucun doute ca ira beaucoup,beaucoup plus vite.
01/10/2006, 10h36
enibris

J'ai la meme pour les nombres, elle est tres rapide, je l'utilise que tout a la fin du programme pour donner le gain maxi et mini.

C'est un peu complique ce que j'ai fais, j'explique.

Partons d'un cas simple:

le calcul des toutes les combinaisons qui se repete pas avec a(2/3)=3=>K=A*B+A*C+B*C

Quand j'ai des sous-ensemble de A {A1,A2}, je redevelopper: K=A1*B+A2*B+A1*C+A2*C+B*C la j'ai 5 combinaisons

Voila pourquoi j'ai besoins de string, c'est pour trouver le nombre de combinaisons lorsque j'ai des sous ensembles.

Au maxi je peux avoir 3 elements dans A {A1,A2,A3} et au mini 1 element A

Merci de votre aide
10/10/2006, 10h03
Vld44

Citation:

Envoyé par Delbeke

c'est que tu as utilisé les types de variable lel plus lent que vb puisse traiter : les variants et pire encore les strings.

c'est faux, le traitement des variants est plus long que les strings.
10/10/2006, 13h13
ced600

Je trouve que le sujet n'est pas tres clair. Je ne comprends pas vraiment ce que tu veux calculer, est ce que tu peut expliquer un peu ?
Parce que pour optimiser un code il faut souvent changer l'algo, et la je ne peut pas réfléchir à un autre algo si je ne sais pas ce que tu veux obtenir.
Ha et est ce que tu pourrais commenter ton code ? Parce que tu le comprends peut être parfaitement, mais pour nous c'est pas forcement évident de le comprendre, surtout lorsque c'est recursif.
10/10/2006, 13h27
Vld44

J'ai deux remarques :

1) est-tu sur du "Komb1(ByVal tableau() ..." ? n'est-ce pas plutôt un byref ? Tu dupliques systématiquement le contenu de ton tableau ...

2) chez moi ton code met 5 secondes à s'exécuter (6/16), c'est "long" pour toi ?
10/10/2006, 14h31
hpfx

Citation:

Envoyé par Vld44

c'est faux, le traitement des variants est plus long que les strings.

Une question, qui n'a pas grand chose a voir avec le sujet, mais qui est relatif à l'optimisation en VB6 :
J'ai lu il y a tres longtemps que si on souhaite utiliser des entier, il valais mieux utiliser des Long (8 oct)plutot que des Integer (4 oct).
bien que le long est 2 fois plus long, mais il paraitrait que le temps de chargement ne soit pas plus long (mettre le nombre dans le registre) alors que certaines operation sont plus rapide sur du long...

qu'en pensez-vous ?

PS : moi depuis tous mes entiers sont des Long :)
10/10/2006, 15h33
Vld44

aucune idée.
Si c'est le cas, je pense qu'un rechercher remplacer dans mon prog me renverrais 1548569 occurences ... :)

edit : (msdn)

Citation:

Performance
Les opérations arithmétiques sont plus rapides avec les types intégraux qu'avec les autres types de données. Elles sont plus rapides avec les types Integer et UInteger dans Visual Basic.

Grands entiers
Si vous devez placer un entier plus grand que le type de données Integer ne peut contenir, vous pouvez utiliser à la place le type de données Long. Les variables Long peuvent contenir des nombres compris entre -9 223 372 036 854 775 808 et 9 223 372 036 854 775 807. Les opérations avec Long sont légèrement plus lentes qu'avec Integer.
10/10/2006, 15h56
hpfx

Merci Vld44,
Bon j'ai plus que 1212133212 occurences de Long a changer en Integer moi maintenant ;)

Si j'ai le temps je ferai un bench (a base de l'algo des tours de hanoi) et je vous dirait le pourcentage d'ecart.... 'tain j'aurai du poser la question avant :)
10/10/2006, 19h39
ced600

Apres une vérification sur le net, un registre en assembleur est de 8, 16, 32, ou 64 bits. Soit je pense que cela dépend de la machine que l'on a. Un long 8 octets devraient représenter 64 bits et un integer 4 octets -> 32 bits. Donc sur une machine 32 bits Long -> nescessite 2 registres, integer -> nescessite 1 registre. Je vous laisse en tirer les conclusions.

PS : sur les machines 64 bits je crois que les long et integer doubles, ou devraient doubler. Je ne suis plus sur.

Ca y est, je viens de faire un benchmark entre integer et Long.
voici l'algo que j'ai utilisé :
=> tours de Hanoi avec 15 plateaux en version Integer
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 Sub AlgoHanoi1() ' Algo avec des Integer Call Hanoi1(1, 3, 2, 15) ' lacement de hanoi avec 15 plateaux End Sub Sub Hanoi1(ByVal dep As Integer, ByVal dest As Integer, ByVal temp As Integer, ByVal i As Integer) If i = 1 Then ' Debug.Print "on déplace de la pile " & dep & " vers la pile " & dest Else Call Hanoi1(dep, temp, dest, i - 1) Call Hanoi1(dep, dest, temp, 1) Call Hanoi1(temp, dest, dep, i - 1) End If End Sub
=> même algo en version Long :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 Sub AlgoHanoi2() ' algo avec des Long Call Hanoi2(1, 3, 2, 15) ' lacement de hanoi avec 15 plateaux End Sub Sub Hanoi2(ByVal dep As Long, ByVal dest As Long, ByVal temp As Long, ByVal i As Long) If i = 1 Then ' Debug.Print "on déplace de la pile " & dep & " vers la pile " & dest Else Call Hanoi2(dep, temp, dest, i - 1) Call Hanoi2(dep, dest, temp, 1) Call Hanoi2(temp, dest, dep, i - 1) End If End Sub
Maintenant le code pour le benchmark
a mettre dans un module (API) :
Code:

1 2 3 4 5 6 7 Declare Function QueryPerformanceCounter Lib "kernel32" _ (lpPerformanceCount As Currency) As Long Declare Function QueryPerformanceFrequency Lib "kernel32" _ (lpFrequency As Currency) As Long ' Ref: ' http://support.microsoft.com/kb/q172338/ ' et http://vdev.net/vbprofiler/perfcount1.htm
Le bench en lui même :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 Sub bench() Dim i As Currency, i2 As Currency, temps1 As Currency, temps2 As Currency Call QueryPerformanceCounter(i) AlgoHanoi1 Call QueryPerformanceCounter(i2) temps1 = i2 - i Call QueryPerformanceCounter(i) AlgoHanoi2 Call QueryPerformanceCounter(i2) temps2 = i2 - i MsgBox "en Integer :" & temps1 & vbCrLf & "en Long : " & temps2 End Sub
je mets un bouton dans un form :
Code:

1 2 3 4 5 6 Private Sub Command1_Click() ' je lance un coups de chaque dans le vide... Call AlgoHanoi1 Call AlgoHanoi2 bench End Sub
Et les resultats...

et Bien a noter que la difference est assez minime.
sauf dans l'IDE ou sur une 10aine de tests je trouve le Long plus rapide que l'integer (en moyenne : 3.94 pour Integer et 3.87 pour le Long)

une fois compilé, je trouve les difference plus faible (en pourcentage)
Je suis passé a 20 plateaux (32 fois plus d'operations)
J'obtiens alors les resultats suivants : integer :22.83 et Long : 23.17 donc l'Integer plus rapide que le long.

mais bon, ca fait 1.5% plus rapide...

mais bon avec l'algo Hanoi je teste surtout le passage d'Integer/Long mais pas trop les operation arithmetique...

voilà.