Effiziente asynchrone Fibonacci-Berechnung in JavaScript: Node.js- und Browser-Ansatz

Die Fibonacci-Folge wird häufig in der Programmierung verwendet, und ihre Berechnung ist eine großartige Möglichkeit, Algorithmen, asynchrone Programmierung und Optimierung zu verstehen. In diesem Artikel werden wir uns ansehen, wie man Fibonacci-Zahlen in JavaScript für Node.js asynchron berechnet und diesen Ansatz für Browser anpasst. Wir werden behandeln, wie man Caching verwendet, um die Berechnungen zu beschleunigen, und warum ein asynchroner Ansatz mit Promise und setImmediate für große Zahlen gut geeignet ist. Wir beginnen mit einer Node.js-Implementierung und wechseln dann zu einer browserfreundlichen Version.

1. Eine kurze Einführung in Fibonacci-Zahlen

Fibonacci-Zahlen bilden eine Folge, bei der jede Zahl die Summe der beiden vorhergehenden ist. Die Folge beginnt mit 0 und 1:

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

Mathematisch ist sie definiert als:

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

F(n) = F(n-1) + F(n-2) für n ≥ 2

Für kleine Werte, wie n = 10, ist diese Berechnung mit einfacher Rekursion handhabbar. Aber wenn wir beispielsweise F(1000) berechnen müssen, wird ein einfacher rekursiver Algorithmus sehr langsam. Um dies effizient zu gestalten, müssen wir Caching und asynchrone Funktionen verwenden.

2. Fibonacci-Implementierung für Node.js

Verwendung von Promise, setImmediate und Caching

Node.js bietet setImmediate, das es ermöglicht, die Codeausführung bis zur nächsten Iteration der Ereignisschleife zu verschieben, ohne den Hauptthread zu blockieren. Dies ist besonders hilfreich für rekursive Aufgaben wie die Berechnung von Fibonacci-Zahlen, da es einen Stapelüberlauf verhindert und uns die Verwendung von Promise ermöglicht.

Hier ist eine Implementierung für Node.js:

const cache = new Map();

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

        if (cache.has(n)) {
            return resolve(cache.get(n)); // Aus dem Cache zurückgeben, wenn bereits berechnet
        }

        setImmediate(() => { // Ausführung verschieben, um Blockierung zu vermeiden
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2); // Ergebnis für F(n) im Cache speichern
                resolve(fib1 + fib2);
            }));

            /*
             * sehr zeitaufwendig
             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}, Leistungszeit: ${performance.now().toFixed(2)}`));

Wie diese Funktion funktioniert:

• Caching: Wir verwenden ein Map-Objekt als Cache, um berechnete Fibonacci-Zahlen zu speichern. Wenn die fib-Funktion mit einem neuen n aufgerufen wird, überprüft sie zuerst den Cache und gibt den Wert zurück, wenn er bereits gespeichert ist.
• Asynchrones setImmediate: setImmediate ermöglicht es uns, jeden rekursiven Aufruf auszulagern, ohne den Stapel zu überlaufen. Es fügt die Ausführung der Makroaufgaben-Warteschlange hinzu, sodass JavaScript in der Zwischenzeit andere Aufgaben bearbeiten kann.
• Warum es schnell ist: Diese Methode ist hoch effizient, da Caching redundante Berechnungen verhindert und asynchrone Ausführung Blockierungen vermeidet.

Ergebnis: fib(1000) gibt fast sofort zurück, indem es zwischengespeicherte Werte nutzt und jeden rekursiven Schritt asynchron verarbeitet.

3. Fibonacci-Implementierung für Browser

Browser unterstützen setImmediate nicht, aber wir können ein ähnliches Verhalten mit setTimeout mit einer Verzögerung von 0 erreichen. Dies ermöglicht es der Funktion, die Kontrolle an andere Aufgaben in der Ereignisschleife abzugeben, ähnlich wie setImmediate in Node.js.

Code für Browser

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

        // Verwenden Sie setTimeout anstelle von setImmediate für asynchrone Ausführung
        setTimeout(() => {
            fib(n - 1).then(fib1 => fib(n - 2).then(fib2 => {
                cache.set(n, fib1 + fib2);
                resolve(fib1 + fib2);
            }));
        }, 0); // 0-Verzögerung, um den Hauptthread nicht zu blockieren
    });
}

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

Wie es im Browser funktioniert:

• Caching: Wie in Node.js verwendet die Browserversion Map für das Caching, um doppelte Berechnungen zu verhindern.
• Asynchrones setTimeout: Anstelle von setImmediate verwenden wir setTimeout mit einer Verzögerung von 0. Dies verschiebt die Ausführung und lässt JavaScript andere Aufgaben in der Ereignisschleife bearbeiten, um eine Blockierung des Threads zu vermeiden.
• Leistungsvorteile: Während setTimeout etwas mehr Overhead als setImmediate hat, ist dieser Ansatz dennoch schnell und effektiv für browserbasierte Berechnungen.

4. Warum Promise.all die Dinge verlangsamen kann

Wenn wir die aktuelle Implementierung durch Promise.all ersetzen:

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

werden wir einen Leistungsabfall feststellen. Der Grund ist, dass Promise.all beide rekursiven Aufrufe gleichzeitig startet. Wenn ein Wert noch nicht zwischengespeichert ist, kann dies zu einer großen Anzahl paralleler rekursiver Aufrufe führen, die die Ereignisschleife stark belasten. Die aktuelle Implementierung (mit sequentiellem fib(n - 1) und fib(n - 2)) ist effizienter für zwischengespeicherte Berechnungen.

5. Fazit

Um Fibonacci-Zahlen in JavaScript zu berechnen, umfasst ein effizienter Ansatz:

• Caching: Speichern vorheriger Ergebnisse, um Berechnungen für große n zu beschleunigen.
• Asynchrone Ausführung: Verwendung von setImmediate in Node.js und setTimeout mit 0-Verzögerung in Browsern, um den Hauptthread nicht zu blockieren.
• Optimierte Sequenz: Starten rekursiver Aufrufe nacheinander anstatt parallel nutzt das Caching effektiver aus.

Diese Methoden ermöglichen es, selbst große Werte wie fib(1000) fast sofort zu berechnen.