Cálculo eficiente de Fibonacci asíncrono en JavaScript: Enfoque para Node.js y navegador

La secuencia de Fibonacci se utiliza ampliamente en programación, y calcularla es una excelente manera de entender algoritmos, programación asíncrona y optimización. En este artículo, veremos cómo calcular números de Fibonacci en JavaScript para Node.js asíncronamente y adaptar este enfoque para navegadores. Cubriremos cómo usar el almacenamiento en caché para acelerar los cálculos y por qué un enfoque asíncrono con Promise y setImmediate es adecuado para números grandes. Comenzaremos con una implementación en Node.js y luego pasaremos a una versión compatible con navegadores.

1. Una Introducción Rápida a los Números de Fibonacci

Los números de Fibonacci forman una secuencia donde cada número es la suma de los dos anteriores. La secuencia comienza con 0 y 1:

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

Matemáticamente, se define como:

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

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

Para valores pequeños, como n = 10, este cálculo es manejable con recursión simple. Pero si necesitamos calcular, por ejemplo, F(1000), un algoritmo recursivo básico se vuelve muy lento. Para hacer esto eficiente, necesitamos usar almacenamiento en caché y funciones asíncronas.

2. Implementación de Fibonacci para Node.js

Usando Promise, setImmediate y Almacenamiento en Caché

Node.js proporciona setImmediate, que permite que la ejecución del código se posponga hasta la siguiente iteración del bucle de eventos, sin bloquear el hilo principal. Esto es particularmente útil para tareas recursivas como calcular números de Fibonacci, ya que previene el desbordamiento de pila y nos permite usar Promise.

Aquí hay una implementación para Node.js:

const cache = new Map();

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

        if (cache.has(n)) {
            return resolve(cache.get(n)); // Retornar desde caché si ya está calculado
        }

        setImmediate(() => { // Posponer ejecución para evitar bloqueo
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2); // Almacenar resultado en caché para F(n)
                resolve(fib1 + fib2);
            }));

            /*
             * toma mucho tiempo
             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}, tiempo de rendimiento: ${performance.now().toFixed(2)}`));

Cómo Funciona Esta Función:

• Almacenamiento en Caché: Usamos un objeto Map como caché para almacenar números de Fibonacci calculados. Cuando se llama a la función fib con un nuevo n, primero verifica la caché y devuelve el valor si ya está almacenado.
• setImmediate Asíncrono: setImmediate nos permite descargar cada llamada recursiva sin desbordar la pila. Agrega la ejecución a la cola de macrotareas, permitiendo que JavaScript maneje otras tareas mientras tanto.
• Por Qué Es Rápido: Este método es altamente eficiente ya que el almacenamiento en caché previene cálculos redundantes, y la ejecución asíncrona evita el bloqueo.

Resultado: fib(1000) devuelve casi instantáneamente aprovechando los valores en caché y procesando cada paso recursivo de manera asíncrona.

3. Implementación de Fibonacci para Navegadores

Los navegadores no soportan setImmediate, pero podemos lograr un comportamiento similar usando setTimeout con un retraso de 0. Esto permite que la función ceda el control a otras tareas en la cola de eventos, similar a setImmediate en Node.js.

Código para Navegadores

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));
        }

        // Usar setTimeout en lugar de setImmediate para ejecución asíncrona
        setTimeout(() => {
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2);
                resolve(fib1 + fib2);
            }));
        }, 0); // 0 de retraso para evitar bloquear el hilo principal
    });
}

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

Cómo Funciona en el Navegador:

• Almacenamiento en Caché: Como en Node.js, la versión para navegadores usa Map para el almacenamiento en caché, previniendo cálculos duplicados.
• setTimeout Asíncrono: En lugar de setImmediate, usamos setTimeout con un retraso de 0. Esto difiere la ejecución y permite que JavaScript maneje otras tareas en el bucle de eventos, evitando el bloqueo del hilo.
• Beneficios de Rendimiento: Aunque setTimeout tiene un poco más de sobrecarga que setImmediate, este enfoque sigue siendo rápido y efectivo para cálculos basados en navegadores.

4. Por Qué Promise.all Puede Ralentizar las Cosas

Si reemplazamos la implementación actual con Promise.all:

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

veremos una caída en el rendimiento. La razón es que Promise.all inicia ambas llamadas recursivas simultáneamente. Si un valor aún no está en caché, esto puede llevar a un gran número de llamadas recursivas paralelas, poniendo una carga pesada en el bucle de eventos. La implementación actual (con fib(n - 1) y fib(n - 2) secuenciales) es más eficiente para cálculos en caché.

5. Conclusión

Para calcular números de Fibonacci en JavaScript, un enfoque eficiente incluye:

• Almacenamiento en Caché: Almacenar resultados previos para acelerar los cálculos para n grandes.
• Ejecución Asíncrona: Usar setImmediate en Node.js y setTimeout con 0 de retraso en navegadores para evitar bloquear el hilo principal.
• Secuencia Optimizada: Lanzar llamadas recursivas secuencialmente en lugar de en paralelo aprovecha el almacenamiento en caché de manera más efectiva.

Estos métodos hacen posible calcular incluso valores grandes, como fib(1000), casi instantáneamente.