Trampolin, Beispiel in Java

Lassen Sie uns ein einfaches Programm schreiben, um Zahlen von n bis 0 zu addieren. Aber warum versuchen Sie es nicht mit einem rekursiven Ansatz, anstatt einen iterativen Ansatz zu verwenden?

Wir nennen dieses Programm sum. Wir wissen sum(0) == 0, also ist dies unser Basisszenario. Wie kommen wir zum Basisfall? sum(n) == n sum(n-1), bis wir endlich sum(0) erreichen. Der Java-Code lautet wie folgt:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Rekursionsproblem?

Rekursion weist einen inhärenten Fehler auf, wenn der Basisfall weit vom Eingabewert entfernt ist ... In den meisten Sprachen verwenden Funktionsaufrufe den Stapel des Programms, um Funktionsaufrufinformationen zu speichern, sodass sehr große Rekursionen einen Stapelüberlauf verursachen können.

Aber gibt es eine Möglichkeit, dies zu vermeiden? Tatsächlich gibt es das. Dies ist eine alte Strategie namens Trampolin.

Sprungbrett

Die Grundidee der Springboard-Strategie besteht darin, dass ein Teil des Programms einen „Wert“ oder eine „Fortsetzung“ zurückgibt. Was ist Fortsetzung? Eine Funktion, die die Verarbeitung fortsetzt.

Es ist ungefähr so:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Was ist die Fortsetzung von

sum?

Lassen Sie uns sum das Programm wie folgt modellieren: Anstatt einfach zu rekursieren, verwenden Sie Fortsetzungen. Eine Möglichkeit besteht darin, acc als Objekt zu verwenden, das über eine Fortsetzung übergeben wird. Wenn also sum_trampoline(0, acc) erreicht ist, kehren wir zu acc zurück. Wie geht es weiter?

Gehen wir von sum_trampoline(n, acc) zu sum_trampoline(n-1, acc n). Die erste Eingabe ist sum_trampoline(n, 0).

Der Code lautet also wie folgt:

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Verwenden Sie Typen, um Sprungbretter zu beschreiben

Das Sprungbrett muss ungefähr die folgende Form haben:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Aber das gibt viel Codierungsfreiheit und ist für die Java-Welt nicht sehr intuitiv. Wir können überprüfen, ob es sich um eine Fortsetzung handelt, indem wir das Objekt fragen. Was wäre, wenn wir fragen würden: „Wurde der Wert gefunden?“ Da Java keine Summentypen hat, gibt return trampolim tatsächlich den Typ trampolim zurück, anstatt den Wert zurückzugeben. Wir können zu trampolim.value() zurückkehren.

Ein wichtiger Punkt ist schließlich das Bootstrapping des Sprungbretts. Dazu können wir eine Funktion verwenden, um die Eingabe in den entsprechenden Pogo-Rückgabewert umzuwandeln. Eingaben und Ergebnisse können zur besseren Nutzung verallgemeinert werden:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

TrampolineStep<r></r>Was ist mit der Schnittstelle?

Es definiert drei Methoden:

• gotValue: Fragt, ob der Wert gefunden wurde
• value: Gibt den gefundenen Wert
zurück
• runNextStep: Gibt einen Wert oder eine Fortsetzung zurück

Es gibt grundsätzlich zwei Zustände:

• Wert gefunden
• Es ist eine Fortsetzung

Daher können wir statische Methoden verwenden, um es zu initialisieren. In Fällen, in denen der Wert gefunden wurde, muss der Wert übergeben werden:

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

Im Falle einer Fortsetzung müssen Sie angeben, wie Sie zum nächsten Element der Fortsetzung gelangen:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sum_trampolineWie wird dies erreicht?

Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}

Tail Call Fibonacci

Die klassische Implementierung von Fibonacci folgt der rekursiven Definition:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

Es gibt auch eine iterative Version, die die Fibonacci-Definition nicht rekursiv, sondern vorwärts erweitert: beginnend bei 0 und 1, bis die entsprechenden Werte erreicht sind:

public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}

Es gibt eine Vorwärtsversion dieser Implementierung, die „Tail Call Recursion“ verwendet:

static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}

Hier trenne ich die Eingabeschnittstelle, die die Zahlen vorbereitet, die im rekursiven Fibonacci-Endaufruf verwendet werden. Im weiteren Verlauf beginnen wir mit der Zuordnung fib[0] => 0, fib[1] => 1 und navigieren von Index 0 bis wir Index n erreichen.

Fibonacci: Vom Tail Call zum Sprungbrett

Das Beispiel von

fib_tc veranschaulicht das Fibonacci-Sprungbrett gut:

static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}

Bitte beachten Sie, dass dies nur ein Grundgerüst ist und eine vollständige Implementierung der TrampolineStep-Schnittstelle und eine vollständige Implementierung der trampoline-Funktionen zum Kompilieren und Ausführen erfordert. Darüber hinaus muss IN durch einen bestimmten Eingabetyp ersetzt werden.

Das obige ist der detaillierte Inhalt vonTrampolin, Beispiel in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!