Optimisation d'algorithme
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.314850 | b 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.