Эффективный асинхронный расчет чисел Фибоначчи на JavaScript: подход для Node.js и браузера

Последовательность Фибоначчи широко используется в программировании, и её вычисление — отличный способ понять алгоритмы, асинхронное программирование и оптимизацию. В этой статье мы рассмотрим, как вычислять числа Фибоначчи в JavaScript для Node.js асинхронно и адаптировать этот подход для браузеров. Мы обсудим, как использовать кэширование для ускорения вычислений и почему асинхронный подход с Promise и setImmediate хорошо подходит для больших чисел. Мы начнем с реализации для Node.js, а затем перейдем к версии, совместимой с браузерами.

1. Краткое введение в числа Фибоначчи

Числа Фибоначчи образуют последовательность, в которой каждое число является суммой двух предыдущих. Последовательность начинается с 0 и 1:

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

Математически это определяется как:

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

F(n) = F(n-1) + F(n-2) для n ≥ 2

Для небольших значений, таких как n = 10, это вычисление управляемо с помощью простой рекурсии. Но если нам нужно вычислить, скажем, F(1000), базовый рекурсивный алгоритм становится очень медленным. Чтобы сделать это эффективно, нам нужно использовать кэширование и асинхронные функции.

2. Реализация Фибоначчи для Node.js

Использование Promise, setImmediate и кэширования

Node.js предоставляет setImmediate, который позволяет отложить выполнение кода до следующей итерации цикла событий, не блокируя основной поток. Это особенно полезно для рекурсивных задач, таких как вычисление чисел Фибоначчи, так как это предотвращает переполнение стека и позволяет использовать Promise.

Вот реализация для Node.js:

const cache = new Map();

function fib(n) {
    return new Promise((resolve, reject) => {
        if (n === 0 || n === 1) {
            return resolve(n); // Базовые случаи: F(0) = 0, F(1) = 1
        }

        if (cache.has(n)) {
            return resolve(cache.get(n)); // Возвращаем из кэша, если уже вычислено
        }

        setImmediate(() => { // Откладываем выполнение, чтобы избежать блокировки
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2); // Кэшируем результат для F(n)
                resolve(fib1 + fib2);
            }));

            /*
             * занимает много времени
             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}, время выполнения: ${performance.now().toFixed(2)}`));

Как работает эта функция:

• Кэширование: Мы используем объект Map в качестве кэша для хранения вычисленных чисел Фибоначчи. Когда функция fib вызывается с новым n, она сначала проверяет кэш и возвращает значение, если оно уже сохранено.
• Асинхронный setImmediate: setImmediate позволяет разгрузить каждый рекурсивный вызов без переполнения стека. Он добавляет выполнение в очередь макрозадач, позволяя JavaScript обрабатывать другие задачи в это время.
• Почему это быстро: Этот метод очень эффективен, так как кэширование предотвращает избыточные вычисления, а асинхронное выполнение избегает блокировки.

Результат: fib(1000) возвращает результат почти мгновенно, используя кэшированные значения и обрабатывая каждый рекурсивный шаг асинхронно.

3. Реализация Фибоначчи для браузеров

Браузеры не поддерживают setImmediate, но мы можем добиться аналогичного поведения, используя setTimeout с задержкой 0. Это позволяет функции уступать управление другим задачам в очереди событий, аналогично setImmediate в Node.js.

Код для браузеров

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

        // Используем setTimeout вместо setImmediate для асинхронного выполнения
        setTimeout(() => {
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2);
                resolve(fib1 + fib2);
            }));
        }, 0); // Задержка 0, чтобы избежать блокировки основного потока
    });
}

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

Как это работает в браузере:

• Кэширование: Как и в Node.js, версия для браузера использует Map для кэширования, предотвращая дублирование вычислений.
• Асинхронный setTimeout: Вместо setImmediate мы используем setTimeout с задержкой 0. Это откладывает выполнение и позволяет JavaScript обрабатывать другие задачи в цикле событий, избегая блокировки потока.
• Преимущества производительности: Хотя setTimeout имеет немного больше накладных расходов, чем setImmediate, этот подход все равно быстрый и эффективный для вычислений в браузере.

4. Почему Promise.all может замедлить выполнение

Если мы заменим текущую реализацию на Promise.all:

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

мы увидим падение производительности. Причина в том, что Promise.all запускает оба рекурсивных вызова одновременно. Если значение еще не закэшировано, это может привести к большому количеству параллельных рекурсивных вызовов, создавая большую нагрузку на цикл событий. Текущая реализация (с последовательными fib(n - 1) и fib(n - 2)) более эффективна для вычислений с использованием кэша.

5. Заключение

Для вычисления чисел Фибоначчи в JavaScript эффективный подход включает:

• Кэширование: Хранение предыдущих результатов для ускорения вычислений для больших n.
• Асинхронное выполнение: Использование setImmediate в Node.js и setTimeout с задержкой 0 в браузерах, чтобы избежать блокировки основного потока.
• Оптимизированная последовательность: Запуск рекурсивных вызовов последовательно, а не параллельно, более эффективно использует кэширование.

Эти методы позволяют вычислять даже большие значения, такие как fib(1000), почти мгновенно.