再帰プリミティブを超えた関数への出発点? Ackermann Peter 関数の実装

スプリングボード手法を検討するとき、私は最初にそれを 1 回だけの再帰 (おそらく原始的な再帰関数の適切なサブセット) で、より単純な状況で使用しました。 しかし、仕事で非常に長い計算を実行する必要が生じました。 私の最初のアイデアは busy beaver 関数でしたが、計算の複雑さに加えて、私は十分に詳しくありませんでした。 次に、よりよく知られている関数である Ackermann-Peter 関数を選択しました。

アッカーマン-ピーター関数

これは、2 つの整数引数を入力として受け取るわかりやすい関数です。

<code class="language-java">int ackermannPeter(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermannPeter(m - 1, 1);
    }
    return ackermannPeter(m - 1, ackermannPeter(m, n - 1));
}</code>

詳細については、WikipediaのページまたはWolframAlphaを参照してください。

関数の使用方法

ackermannPeter(3, 3) をテストしたとき、結果は正しく計算されました。 しかし、ackermannPeter(4, 3)を実行すると、スタック爆発が発生しました。 Ackermann-Peter 関数の再帰呼び出しの深さは非常に深いです。最初の引数を 3 から 4 に変更するだけで、61 だった出力は $2^{2^{65536}} - 3$.

スタック制限の克服

問題は、スタックをすぐに使い果たすアッカーマン-ピーター関数の激しい再帰にあります。 解決策は、継続を使用してスタックの過負荷を回避し、出発点のアイデアを実装することです。

トランポリンを踏むには 3 つの動作が必要です:

• 計算が終了したかどうかを示します。
• 計算された値を返します。
• 1 つのステップを実行し、次の継続を取得します。

私たちの場合 (整数の戻り値):

<code class="language-java">interface Continuation {
    boolean finished();
    int value();
    Continuation step();

    static Continuation found(int v) { /* ... */ }
    static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ }
}</code>

トランポリン自体:

<code class="language-java">static int compute(Continuation c) {
    while (!c.finished()) {
        c = c.step();
    }
    return c.value();
}</code>

Ackermann-Peter 関数への適用: この関数は、基本ケース、単純再帰、二重再帰の 3 つのケースに分けられます。 スプリングボードは 2 回目の再帰の結果を制御する必要があります。 これを行うには、2 番目の引数が Continuation になります。 n がすでに終了している場合、プロセスは通常どおり続行されます。それ以外の場合は、継続でステップが実行され、新しいステップが生成されます。

<code class="language-java">private static Continuation ackermannPeter(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeter(m, next));
        });
    }
    int n = c.value();
    if (m == 0) {
        return Continuation.found(n + 1);
    } else if (n == 0) {
        return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeter(m - 1,
            Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1)
        )))
    );
}</code>

メモ化の追加

メモ化によりパフォーマンスが向上します。 2 つの状況: 1) 結果はすでにメモリ内にあります。 2) 次のステップでは、現在の結果を推測できます。 メモ化は、第 2 引数の継続を解決した後に適用されます。 HashMap キーと long キー (m と n を組み合わせたもの) を使用したメモ化の実装が示され、再帰呼び出しの数が大幅に削減されることが示されています。 最終バージョンでは、グローバル メモリの依存関係が削除され、HashMap が引数として渡されます。

以上が再帰プリミティブを超えた関数への出発点? Ackermann Peter 関数の実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。