Ces derniers temps, j'ai recommencé à faire la lecture de plus en plus de code. Certains étaient bien écrit, d'autre moins. J'ai donc décidé de faire ma part et de démontrer ce que j'y ai vu de bien, et de moins bien.
L'un des exemples que j'ai vu, était le calcul de la suite de Fibonacci. Une bonne chose avec le calcul de la suite de Fibonacci, c'est que l'on peut y appliquer les modèles de calcul récursif ou itératif.
Qu'est-ce que la suite de Fibonacci?
La suite de Fibonacci est une suite mathématiques qui, à l'origine, devait répondre à la question:
Un homme met un couple de lapins dans un lieu isolé de tous les côtés par un mur. Combien de couples obtient-on en un an si chaque couple engendre tous les mois un nouveau couple à compter du troisième mois de son existence?
En résumé, chaque nombre, est la somme des 2 nombres précédent, en utilisant 0 et 1 comme point de départ, ce qui nous donne la suite: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Le Calcul Récursif
Le calcul récursif, qui était la méthode de choix de plusieurs de mes professeurs à l'Université, quoique plus compréhensible, est très loin d'être le meilleur choix au niveau des performances.
Le calcul récursif implique d'écrire une fonction qui s'appelle elle même.
public static ulong Fibonacci_Recursive(uint n)
{
if (2 > n)
return n;
return Fibonacci_Recursive(n - 1) + Fibonacci_Recursive(n - 2);
}Le développement de ce calcul, nous montre que la valeur n-2 sera calculé 2 fois, n-3 sera calcul 3 fois, et ainsi de suite.
De ce fait, il est évident qu'il doit y avoir une méthode plus optimisée qui ne fera pas le même calcul plus d'une fois. L'utilisation d'une cache, pour stocker les valeurs déjà calculées, serait un avantage, mais il faudra vérifier si le résultat est déjà stocké. Calculer une valeur très grande demandera plus de temps au départ, mais apportera une grande amélioration comparativement au cas de base. Il faut par contre considérer l'utilisation de la mémoire. Ce n'est pas un problème dans bien des cas, mais il peut arriver qu'une application soit plus rapide si elle n'utilise que la cache du processeur, sans même passer par la mémoire vive. Ce type d'optimisation est plus rare, et est nécessaire seulement dans des cas extrêmes, mais il est bien de le savoir. Il faut aussi prendre en compte que les appels subséquents seront plus rapide, car le résultat est déjà calculé. Tout dépend du nombre d'appel que nous prévoyons pour cette fonction.
static List<ulong> fib = new List<ulong>();
public static ulong Fibonacci_Recursive_buffer(uint n)
{
if (fib.Count > n)
return fib[(int)n];
if (2 > n)
{
for(ulong i = (ulong)fib.Count; i <= n; ++i)
fib.Add(i);
}
else
{
fib.Add(Fibonacci_Recursive_buffer(n - 1) + Fibonacci_Recursive_buffer(n - 2));
}
return fib[(int)n];
}De plus, dans un cas récursif, la pile, qui accumule les appels de fonctions, peut poser un problème dans le cas de très grande valeur. Ce ne sera pas le cas ici, car le résultat ne sera pas bon pour une valeur supérieure à 83.
Le Calcul Itératif
Le calcul itératif est une boucle qui s'exécute plusieurs fois.Donc, plutôt que de s'appeler elle-même est exécute un nombre de ligne de code un certain nombre de fois. Je privilégie cette méthode dans plusieurs cas, elle n'est par contre pas toujours la meilleure solution.
J'ai trouvé sur Internet le code suivant.
public static ulong Fibonacci_Iterative(ulong n)
{
ulong t = 0, i = 0, v = 0, w;
do
{
w = v;
v = t;
t = i < 2 ? i : t + w;
} while (i++ < n);
return t;
}L'auteur disait bien sûr qu'il n'y avait pas moyen de faire plus rapide. Il y a par contre, 2 problèmes dans son code. Le premier problème, c'est que pour le cas $n = 0$, la boucle do{...}while() se fait une fois, même si cela n'est pas nécessaire. Le deuxième problème est plus important, car il touche directement les performances. À l'intérieur de sa boucle, il y a une condition (t = i < 2 ? i : t + w;) qui ralentit le code et qui n'est pas nécessaire pour $i \geq 2$. Il est facile d'éviter ce cas en initialisant correctement t, v et w. La version corrigé est ainsi environ 20% plus rapide.
public static ulong Fibonacci_Iterative_Faster(ulong n)
{
ulong result = 0, f1 = 1, f2, i = 1;
while (i <= n)
{
f2 = f1;
f1 = result;
result = result + f2;
++i;
}
return result;
}L'utilisation ici d'une cache pour stocker les résultats peut aussi être considéré, mais à ce moment, il n'y a pas vraiment d'avantage à utiliser la méthode itérative versus la méthode récursive, car si la cache accélère le premier calcul en récursion, elle le ralentit en itération. Il faut donc considérer le nombre d'appel qui sera fait pour prendre la bonne décision.
Performance et Temps d'exécution
J'ai programmé chacun de ces algorithmes afin de tester la performance dont voici les résultats:
Les temps affichés sont en millisecondes. Le code récursif a été fait avec $n = 40$, les 3 autres ont été exécuter 1000000 de fois avec $n = 80$. Le code récursif ayant une complexité exponentiel est un des problèmes. L'utilisation de la cache permet tout de même de comparer. De plus, pour ce test, j'ai effacé la cache avant chaque calcul de manière à pouvoir le comparer dans le cas d'un seul calcul. Lorsque nous conservons la cache, on obtient un temps inférieur aux calculs itératifs, mais il faut rappeler que la cache occupe de la mémoire qui peut être problématique dans certains cas.
