Calcul de Fibonacci asynchrone efficace en JavaScript : Approche Node.js et Navigateur

La suite de Fibonacci est largement utilisée en programmation, et la calculer est un excellent moyen de comprendre les algorithmes, la programmation asynchrone et l’optimisation. Dans cet article, nous verrons comment calculer les nombres de Fibonacci en JavaScript pour Node.js asynchrone et adapter cette approche pour les navigateurs. Nous couvrirons comment utiliser la mise en cache pour accélérer les calculs et pourquoi une approche asynchrone avec Promise et setImmediate est bien adaptée pour les grands nombres. Nous commencerons par une implémentation Node.js puis passerons à une version compatible avec les navigateurs.

1. Une brève introduction aux nombres de Fibonacci

Les nombres de Fibonacci forment une suite où chaque nombre est la somme des deux précédents. La suite commence par 0 et 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Mathématiquement, elle est définie comme suit :

F(0) = 0, F(1) = 1

F(n) = F(n-1) + F(n-2) pour n ≥ 2

Pour de petites valeurs, telles que n = 10, ce calcul est gérable avec une simple récursion. Mais si nous devons calculer, disons, F(1000), un algorithme récursif de base devient très lent. Pour rendre cela efficace, nous devons utiliser la mise en cache et les fonctions asynchrones.

2. Implémentation de Fibonacci pour Node.js

Utilisation de Promise, setImmediate, et mise en cache

Node.js fournit setImmediate, qui permet de différer l’exécution du code jusqu’à la prochaine itération de la boucle d’événements, sans bloquer le thread principal. Cela est particulièrement utile pour les tâches récursives comme le calcul des nombres de Fibonacci, car cela empêche le débordement de pile et nous permet d’utiliser Promise.

Voici une implémentation pour Node.js :

const cache = new Map();

function fib(n) {
    return new Promise((resolve, reject) => {
        if (n === 0 || n === 1) {
            return resolve(n); // Cas de base : F(0) = 0, F(1) = 1
        }

        if (cache.has(n)) {
            return resolve(cache.get(n)); // Retourner depuis le cache si déjà calculé
        }

        setImmediate(() => { // Différer l'exécution pour éviter le blocage
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2); // Mettre en cache le résultat pour F(n)
                resolve(fib1 + fib2);
            }));

            /*
             * prend beaucoup de temps
             Promise.all([fib(n - 1), fib(n - 2)]).then(([fib1, fib2]) => {
             cache.set(n, fib1 + fib2);
             resolve(fib1 + fib2);
             });
             * 
             */

        });
    });
}

fib(1000).then(res => console.log(`F(1000) = ${res}, temps de performance : ${performance.now().toFixed(2)}`));

Comment cette fonction fonctionne :

• Mise en cache : Nous utilisons un objet Map comme cache pour stocker les nombres de Fibonacci calculés. Lorsque la fonction fib est appelée avec un nouveau n, elle vérifie d’abord le cache et retourne la valeur si elle est déjà stockée.
• setImmediate asynchrone : setImmediate nous permet de décharger chaque appel récursif sans déborder la pile. Il ajoute l’exécution à la file d’attente des macrotâches, permettant à JavaScript de gérer d’autres tâches entre-temps.
• Pourquoi c’est rapide : Cette méthode est très efficace car la mise en cache empêche les calculs redondants, et l’exécution asynchrone évite le blocage.

Résultat : fib(1000) retourne presque instantanément en tirant parti des valeurs mises en cache et en traitant chaque étape récursive de manière asynchrone.

3. Implémentation de Fibonacci pour les navigateurs

Les navigateurs ne supportent pas setImmediate, mais nous pouvons obtenir un comportement similaire en utilisant setTimeout avec un délai de 0. Cela permet à la fonction de céder le contrôle à d’autres tâches dans la file d’attente d’événements, similaire à setImmediate dans Node.js.

Code pour les navigateurs

const cache = new Map();

function fib(n) {
    return new Promise((resolve, reject) => {
        if (n === 0 || n === 1) {
            return resolve(n);
        }

        if (cache.has(n)) {
            return resolve(cache.get(n));
        }

        // Utiliser setTimeout au lieu de setImmediate pour l'exécution asynchrone
        setTimeout(() => {
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2);
                resolve(fib1 + fib2);
            }));
        }, 0); // Délai de 0 pour éviter de bloquer le thread principal
    });
}

fib(1000).then(result => console.log(`F(1000) = ${result}`));

Comment cela fonctionne dans le navigateur :

• Mise en cache : Comme dans Node.js, la version navigateur utilise Map pour la mise en cache, évitant les calculs en double.
• setTimeout asynchrone : Au lieu de setImmediate, nous utilisons setTimeout avec un délai de 0. Cela diffère l’exécution et permet à JavaScript de gérer d’autres tâches dans la boucle d’événements, évitant le blocage du thread.
• Avantages de performance : Bien que setTimeout ait un peu plus de surcharge que setImmediate, cette approche est toujours rapide et efficace pour les calculs basés sur le navigateur.

4. Pourquoi Promise.all peut ralentir les choses

Si nous remplaçons l’implémentation actuelle par Promise.all :

Promise.all([fib(n - 1), fib(n - 2)]).then(([fib1, fib2]) => {
    cache.set(n, fib1 + fib2);
    resolve(fib1 + fib2);
});

nous verrons une baisse de performance. La raison est que Promise.all démarre les deux appels récursifs simultanément. Si une valeur n’est pas encore mise en cache, cela peut entraîner un grand nombre d’appels récursifs parallèles, mettant une lourde charge sur la boucle d’événements. L’implémentation actuelle (avec fib(n - 1) et fib(n - 2) séquentiels) est plus efficace pour les calculs mis en cache.

5. Conclusion

Pour calculer les nombres de Fibonacci en JavaScript, une approche efficace inclut :

• Mise en cache : Stocker les résultats précédents pour accélérer les calculs pour de grands n.
• Exécution asynchrone : Utiliser setImmediate dans Node.js et setTimeout avec un délai de 0 dans les navigateurs pour éviter de bloquer le thread principal.
• Séquence optimisée : Lancer les appels récursifs séquentiellement plutôt qu’en parallèle exploite plus efficacement la mise en cache.

Ces méthodes permettent de calculer même de grandes valeurs, comme fib(1000), presque instantanément.