Cálculo assíncrono eficiente de Fibonacci em JavaScript: Abordagem para Node.js e Navegador

A sequência de Fibonacci é amplamente utilizada em programação, e calculá-la é uma ótima maneira de entender algoritmos, programação assíncrona e otimização. Neste artigo, veremos como calcular números de Fibonacci em JavaScript para Node.js assíncronamente e adaptar essa abordagem para navegadores. Cobriremos como usar cache para acelerar os cálculos e por que uma abordagem assíncrona com Promise e setImmediate é adequada para números grandes. Começaremos com uma implementação em Node.js e depois passaremos para uma versão compatível com navegadores.

1. Uma Introdução Rápida aos Números de Fibonacci

Os números de Fibonacci formam uma sequência onde cada número é a soma dos dois anteriores. A sequência começa com 0 e 1:

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

Matematicamente, é definida como:

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

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

Para valores pequenos, como n = 10, esse cálculo é gerenciável com recursão simples. Mas se precisarmos calcular, digamos, F(1000), um algoritmo recursivo básico se torna muito lento. Para tornar isso eficiente, precisamos usar cache e funções assíncronas.

2. Implementação de Fibonacci para Node.js

Usando Promise, setImmediate e Cache

Node.js fornece setImmediate, que permite que a execução do código seja adiada até a próxima iteração do loop de eventos, sem bloquear o thread principal. Isso é particularmente útil para tarefas recursivas como calcular números de Fibonacci, pois evita estouro de pilha e nos permite usar Promise.

Aqui está uma implementação 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)); // Retorna do cache se já calculado
        }

        setImmediate(() => { // Adia a execução para evitar bloqueio
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2); // Armazena resultado no cache para F(n)
                resolve(fib1 + fib2);
            }));

            /*
             * leva muito tempo
             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}, tempo de desempenho: ${performance.now().toFixed(2)}`));

Como Esta Função Funciona:

• Cache: Usamos um objeto Map como cache para armazenar números de Fibonacci calculados. Quando a função fib é chamada com um novo n, ela primeiro verifica o cache e retorna o valor se já estiver armazenado.
• setImmediate Assíncrono: setImmediate nos permite descarregar cada chamada recursiva sem estourar a pilha. Ele adiciona a execução à fila de macrotarefas, permitindo que o JavaScript lide com outras tarefas no meio tempo.
• Por Que É Rápido: Este método é altamente eficiente, pois o cache evita cálculos redundantes e a execução assíncrona evita bloqueios.

Resultado: fib(1000) retorna quase instantaneamente aproveitando os valores em cache e processando cada etapa recursiva de forma assíncrona.

3. Implementação de Fibonacci para Navegadores

Os navegadores não suportam setImmediate, mas podemos alcançar um comportamento semelhante usando setTimeout com um atraso de 0. Isso permite que a função ceda o controle para outras tarefas na fila de eventos, semelhante ao setImmediate no 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));
        }

        // Use setTimeout em vez de setImmediate para execução assíncrona
        setTimeout(() => {
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2);
                resolve(fib1 + fib2);
            }));
        }, 0); // Atraso de 0 para evitar bloqueio do thread principal
    });
}

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

Como Funciona no Navegador:

• Cache: Como no Node.js, a versão para navegador usa Map para cache, prevenindo cálculos duplicados.
• setTimeout Assíncrono: Em vez de setImmediate, usamos setTimeout com um atraso de 0. Isso adia a execução e permite que o JavaScript lide com outras tarefas no loop de eventos, evitando bloqueio de thread.
• Benefícios de Desempenho: Embora setTimeout tenha um pouco mais de sobrecarga do que setImmediate, essa abordagem ainda é rápida e eficaz para cálculos baseados em navegador.

4. Por Que Promise.all Pode Diminuir a Velocidade

Se substituirmos a implementação atual por Promise.all:

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

veremos uma queda de desempenho. A razão é que Promise.all inicia ambas as chamadas recursivas simultaneamente. Se um valor ainda não estiver em cache, isso pode levar a um grande número de chamadas recursivas paralelas, colocando uma carga pesada no loop de eventos. A implementação atual (com fib(n - 1) e fib(n - 2) sequenciais) é mais eficiente para cálculos em cache.

5. Conclusão

Para calcular números de Fibonacci em JavaScript, uma abordagem eficiente inclui:

• Cache: Armazenar resultados anteriores para acelerar cálculos para n grandes.
• Execução Assíncrona: Usar setImmediate no Node.js e setTimeout com atraso de 0 em navegadores para evitar bloqueio do thread principal.
• Sequência Otimizada: Lançar chamadas recursivas sequencialmente em vez de em paralelo aproveita o cache de forma mais eficaz.

Esses métodos tornam possível calcular até mesmo valores grandes, como fib(1000), quase instantaneamente.