avril
2010
Un article de phertzog
Les 2 articles précédents nous ont permis de construire une méthode de recherche d’un équilibrium qui semble fonctionner correctement. Par correctement j’entends qui trouve le bon équilibrium dans tous les cas que nous avons analysé pour l’instant.
Démarche TDD – Une première tentative – Part 1
Démarche TDD – Une première tentative – Part 2
Cette dernière partie va se concentrer sur une autre utilisation des tests unitaires
Contrainte supplémentaire
Notre petite implémentation de l’équilibirum a été adoptée pour être incluse dans un projet en production. Super, il est toujours agréable de voir son travail utilisé. Par contre, dans le cadre de l’application, il est demandé que notre méthode soit capable de trouver l’équilibrium d’un tableau de 25000 éléments en moins de 0.5 secondes. Nous allons donc mettre en place un test unitaire en utilisant l’attribut « TimeOut » du test. Pour jouer la sécurité nous allons nous placer dans une situation un peu plus défavorable :
- Le tableau aura 50000 éléments.
- L’équilibrium sera en fin de tableau (ce qui nous obligera à faire le plus de calculs).
Le test
[TestMethod]
[Timeout(500)]
public void BigArray_TestMustBeFast()
{
//Construire un tableau non symétrique
int total = 0;
int[] bigArray = new int[50002];
for (int i = 0; i<50000; i++)
{
bigArray[i] = 1;
total += 1;
}
bigArray[50000] = 0;
bigArray[50001] = total;
int actual = Problems.Equilibrium.Equilibrium.FindEquilibrium(bigArray);
Assert.AreEqual(50000, actual, "Equilibrium non trouvé. {0} au lieu de la valeur attendue", actual);
}
Plein de confiance nous relançons le test … pour découvrir qu’il échoue en « time out » 
Il va falloir retravailler notre code.
Le code
Allons analyser notre code. Je pense que vous avez tous assez rapidement trouvé la source de notre problème. Notre algorithme naïf à une complexité en O(n2). En effet nous avons imbriqué 2 boucles :
- La boucle principale qui parcoure tous les éléments.
- Les 2 boucles internes qui calculent la somme gauche et la somme droite en parcourant également tout le tableau.
Si nous voulons gagner en performance, il faut trouver un algorithme plus efficace. Je vous laisse un peu de temps?
En fait la solution est relativement simple en prenant un peu de recul. au lieu de repartir de 0 à chaque fois, nous allons tout simplement mettre à jour les sommes gauche et droite. L’algorithme de base est le suivant :
- Etape 1 : i=0, sommeGauche = 0, sommeDroite = Somme(Valeur(1) à Valeur(n) ) ou n est le dernier élément du tableau
- Etape 2 : i=1, sommeGauche = sommeGauche + Valeur(0), sommeDroite = sommeDroite ? Valeur(1)
- Et ainsi de suite jusqu’à avoir trouvé un équilibrium ou avoir atteint la fin du tableau
Avec cet algorithme, la complexité tombe à O(n). En effet le temps d’exécution augmente linéairement avec la taille du tableau. Le code optimisé est le suivant
public static int FindEquilibriumOptimized(int[] inputArray)
{
if ((inputArray == null) || (inputArray.Length == 0))
{
return -1;
}
else
{
long leftSum = 0;
long rightSum = 0;
int equilibrium = 0;
for (int i = 1; i<inputArray.Length; i++)
{
rightSum += inputArray[i];
}
if (leftSum == rightSum)
{
return equilibrium;
}
else
{
for (equilibrium = 1; equilibrium<inputArray.Length; equilibrium++)
{
leftSum += inputArray[equilibrium - 1];
rightSum -= inputArray[equilibrium];
if (leftSum == rightSum)
{
return equilibrium;
}
}
}
return -1;
}
}
On croise les doigts, on relance le test et … le test passe en largement moins de 2 secondes. En fait, si l’on compare les 2 algorithmes on obtient les temps suivants :
- Algorithme long : 11.8950 ms
- Algorithme court : 0.0291 ms
Conclusion
Et voila, c’était la dernière partie de cette mini série sur mes premiers pas dans l’utilisation des tests unitaires avec Visual Studio (et dans la rédaction de billets par la même occasion). J’espère que cela aura pu servir à quelqu’un. Je suis preneur pour d’éventuelle remarques sur le fond ou la forme.
Bonne programmation et vivez heureux et prospère.