Ефективний асинхронний розрахунок Фібоначчі в 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), майже миттєво.