CodeS-SourceS
Rechercher un code, un tuto, une réponse

Optimisation d'algorithme

Avril 2017

Bonjour à tous !

J'ai réalisé une petite étude sur le temps d'exécution de plusieurs fonctions très utilisées du .Net.
Voici tout d'abord la manière dont j'ai procédé pour mes mesures :

Sub Main()
Process.GetCurrentProcess.PriorityClass = ProcessPriorityClass.RealTime
Dim w AsNew System.Diagnostics.Stopwatch
    w.Start()
    Test()
    w.Stop()
    System.Windows.Forms.Clipboard.SetText(Replace(Format(w.ElapsedTicks / 1000000 - 0.009556, "0.000000"), ",", "."))
End Sub

Sub Test()
Dim i AsInteger, a As'Type retourné par la fonction à tester
    For     i = 0 To 1000000
        a = 'Fonction à tester
    Next
End Sub


Vous remarquerez sans doute que j'effectue 1 000 000 de fois la fonction et que je divise le résultat obtenu par 1 000 000 afin de minimiser l'erreur de mesure, et que je soustrait 0.009556 à mon résultat final, ceci étant la tare mesurée, correspondant à l'instruction Next et à l'incrémentation du i.
Voici mon tableau de mesure :


Fonctions
Ticks
Notes
Strings
For - Next
0.009556
Boucle For vide, simplement pour avoir la tare de mes mesures
Len(s)
0.012670
Où s est un String de 10 caractères. Même temps avec 10000.
s.Length
0.005127
Où s est un String de 10 caractères. Même temps avec 10000.
Mid(s, 2, 3)
0.274652
Où s est un String de 10 caractères. Même temps avec 10000.
s.Substring(2, 3)
0.265801
Où s est un String de 10 caractères. Même temps avec 10000.
Replace(s, " ", "a")
10.683268
Où s est un String = Space(10) (-> 10 remplacements).
Replace(s, " ", "a")
5.889826
Où s est un String = Space(5) (-> 5 remplacements).
Replace(s, "b", "a")
1.839295
Où s est un String = Space(10) (-> 0 remplacements).
Replace(s, "b", "a")
1.506057
Où s est un String = Space(5) (-> 0 remplacements).
Instr(s, "b")
1.046385
Où s est un String = « aaaaaaaaaaaaaaaabaaaa ».
s.Contains("b")
1.107969
Où s est un String = « aaaaaaaaaaaaaaaabaaaa ».
s.Contains("bbbbbbbbb")
0.940577
Où s est un String = « aaaaaabbbbbbbbbaaaa ».
s.Insert(4, "yyy")
0.934973
Où s est un String = Space(10).
s.Insert(4, "yyy")
7.735215
Où s est un String = Space(1000).
s.Remove(2, 10)
0.929358
Où s est un String = Space(40).
s.Substring(0, 2) & s.Substring(12, 28)
1.183333
Où s est un String = Space(40). Renvoie la même chose que la précédente, juste pour illustrer l'importance de la précision de la fonction choisie...
s.StartsWith("abc")
1.617434
Où s est un String = `abc' & Space(10).
(InStr(s, "abc") = 1)
0.694170
Même chose que le précédent, beaucoup plus rapide !
s.EndsWith("abs")
1.172057
Où s est un S = Space(10) & `abc'
(InStr(s, "abc") = s.Length - 3)
0.920107
Même chose que le précédent, beaucoup plus rapide !
(InStr(s, "abc") = s.Length - "abc".Length)
0.991431
Toujours plus rapide même si la longueur de la chaine est inconnue
Calculs
b + c
0.004991
b et c as integer
b + c
0.004884
b et c as double
b + c
0.006764
b as double et c as integer
b + c
0.169333
b as double et c as integer mais conversion implicite du résultat -> integer
Int(b + c)
0.726987
b as double et c as integer (Ne pas utiliser Int() pour convertir !)
b + c
0.220982
b et c as double mais conversion implicite du résultat -> integer
b + c
0.015684
b et c as Int16 (Remarquez que c'est plus long que sur les integers !)
b + c
0.003586
b et c as Int32 (Presque le même temps qu'avec des integers...)
b + c
0.011505
b et c as Int64
b + c
0.008947
b et c as Long (Nettement plus rapide qu'avec les Int64 !)
sin(b)
0.225270
b as double
cos(b)
0.248604
b as double
sqrt(b)
0.066458
b as double
tan(b)
0.285205
b as double
pow(b, 20.0)
0.423138
b as double
b ^ 20
0.426442
b as double
max(b, c)
0.016820
b as integer, c as integer
If b > c Then a = b Else a = c
0.010731
b as integer, c as integer
min(b, c)
0.017247
b as integer, c as integer
If b < c Then a = b Else a = c
0.009976
b as integer, c as integer
sqrt(b ^ 2 + c ^ 2)
1.314850b as double, c as double (Fonction distance, b = x1 - x2, c = y1 - y2)
b ^ 2 + c ^ 2
1.233296
b as double, c as double (Fonction distance utilisable pour comparaison, faible avantage)
b
0.003946
b as double (Simple assignement)
b ^ 2
0.481059
b as double
b * b
0.004273
b as double (Ho my god !!!!)
b * b + c * c
0.005938
b as double, c as double (Fonction distance utilisable pour comparaison, énorme avantage)
sqrt(b * b + c * c)
0.045453
b as double, c as double (Voilà comment il faut la faire la fonction distance !!!)
Tableaux
b 0->10 (c 0->10 (a = tab(b, c)))
4.236800
tab(10, 10) as integer (b 0->10(...) signifie For b = 0 to 10 (...) Next)
b 0->121 (a = tab(b))
1.794521
tab(121) as integer (Quand c'est possible privilégiez une seule dimension !)
b 0->10 (c 0->10 (a = tab(b * 10 + c)))
3.420987
tab(121) as integer (Avec transformation depuis 2 dimensions)
b 0->100 (a = tab(b))
1.795740
tab(100) as integer
b 0->100 (a = tab(b))
2.985771
tab as new list(of integer) - Initialisées avec 101 éléments, préférez les tableaux !
tab(50)
0.121390
tab(100) as double, juste pour illustrer la lenteur d'une assignation (Cfr B48)



De manière assez clair, on peut en ressortir les améliorations potentielles suivantes :

- Remplacer Len(s) par s.Length lorsqu'il s'agit de texte bien sûr

- Utiliser les fonctions String.Remove et String.Insert plutôt que des String.Substring ou Mid(String) et de la concaténation

- Remplacer systématiquement S1.StartsWith(S2) par Instr(S1, S2) = 1 (A moins que vous ne voyez une différence mais...)

- Idem pour S1.EndsWith(S2)

- Faire attention aux conversions implicites Integer -> Double (Par contre Double -> Integer ne semble pas poser de problèmes !)

- Ne pas utiliser les Int16 à moins que le but ne soit de gagner de la mémoire et de perdre du temps

- Remplacer les Int64 par des Longs

- Faites vos fonctions Max et Min à la main (Sans fonction mais avec la condition comme dans le tableau)

- Remplacer les ^ par n facteurs de la base quand c'est possible !!! Ne laissez pas de x ^ 2 dans vos programmes, c'est apparemment 100 fois plus lent que d'écrire x * x

- Pour les algorithmes utilisant les distances, si vous ne devez que les comparer, inutile de leur appliquer une racine carrée

- Si possible, utilisez des tableaux à 1 dimension et faites une petite fonction de traduction de 1 paramètre vers x paramètres, par exemple pour un tableau (100,100,100) :

Function Traduction(ByVal x AsInteger, ByVal y AsInteger, ByVal z AsInteger) As Integer
    Return x * 101 * 101 + y * 101 + z
End Function


Attention toutefois à ce que le code reste lisible, je vous conseille d'effectuer certaines transformations uniquement tout à la fin du projet...

N'hésitez pas à faire vos propres tests, le code est tellement simple !

Julien.

A voir également

Publié par Julien237.
Ce document intitulé «  Optimisation d'algorithme  » issu de CodeS-SourceS (codes-sources.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Les expressions rationnelles ("régulières")
Commentaires sans douleur