再帰プリミティブを超えた関数への出発点? Ackermann Peter 関数の実装
スプリングボード手法を検討するとき、私は最初にそれを 1 回だけの再帰 (おそらく原始的な再帰関数の適切なサブセット) で、より単純な状況で使用しました。 しかし、仕事で非常に長い計算を実行する必要が生じました。 私の最初のアイデアは busy beaver 関数でしたが、計算の複雑さに加えて、私は十分に詳しくありませんでした。 次に、よりよく知られている関数である Ackermann-Peter 関数を選択しました。
アッカーマン-ピーター関数
これは、2 つの整数引数を入力として受け取るわかりやすい関数です。
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)); }
詳細については、WikipediaのページまたはWolframAlphaを参照してください。
関数の使用方法
ackermannPeter(3, 3)
をテストしたとき、結果は正しく計算されました。 しかし、ackermannPeter(4, 3)
を実行すると、スタック爆発が発生しました。 Ackermann-Peter 関数の再帰呼び出しの深さは非常に深いです。最初の引数を 3 から 4 に変更するだけで、61 だった出力は .
スタック制限の克服
問題は、スタックをすぐに使い果たすアッカーマン-ピーター関数の激しい再帰にあります。 解決策は、継続を使用してスタックの過負荷を回避し、出発点のアイデアを実装することです。
トランポリンを踏むには 3 つの動作が必要です:
- 計算が終了したかどうかを示します。
- 計算された値を返します。
- 1 つのステップを実行し、次の継続を取得します。
私たちの場合 (整数の戻り値):
interface Continuation { boolean finished(); int value(); Continuation step(); static Continuation found(int v) { /* ... */ } static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ } }
トランポリン自体:
static int compute(Continuation c) { while (!c.finished()) { c = c.step(); } return c.value(); }
Ackermann-Peter 関数への適用: この関数は、基本ケース、単純再帰、二重再帰の 3 つのケースに分けられます。 スプリングボードは 2 回目の再帰の結果を制御する必要があります。 これを行うには、2 番目の引数が Continuation
になります。 n
がすでに終了している場合、プロセスは通常どおり続行されます。それ以外の場合は、継続でステップが実行され、新しいステップが生成されます。
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) ))) ); }
メモ化の追加
メモ化によりパフォーマンスが向上します。 2 つの状況: 1) 結果はすでにメモリ内にあります。 2) 次のステップでは、現在の結果を推測できます。 メモ化は、第 2 引数の継続を解決した後に適用されます。 HashMap
キーと long
キー (m
と n
を組み合わせたもの) を使用したメモ化の実装が示され、再帰呼び出しの数が大幅に削減されることが示されています。 最終バージョンでは、グローバル メモリの依存関係が削除され、HashMap
が引数として渡されます。
以上が再帰プリミティブを超えた関数への出発点? Ackermann Peter 関数の実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











一部のアプリケーションが適切に機能しないようにする会社のセキュリティソフトウェアのトラブルシューティングとソリューション。多くの企業は、内部ネットワークセキュリティを確保するためにセキュリティソフトウェアを展開します。 ...

多くのアプリケーションシナリオでソートを実装するために名前を数値に変換するソリューションでは、ユーザーはグループ、特に1つでソートする必要がある場合があります...

システムドッキングでのフィールドマッピング処理は、システムドッキングを実行する際に難しい問題に遭遇することがよくあります。システムのインターフェイスフィールドを効果的にマッピングする方法A ...

データベース操作にMyBatis-Plusまたはその他のORMフレームワークを使用する場合、エンティティクラスの属性名に基づいてクエリ条件を構築する必要があることがよくあります。あなたが毎回手動で...

intellijideaultimatiateバージョンを使用してスプリングを開始します...

Javaオブジェクトと配列の変換:リスクの詳細な議論と鋳造タイプ変換の正しい方法多くのJava初心者は、オブジェクトのアレイへの変換に遭遇します...

eコマースプラットフォーム上のSKUおよびSPUテーブルの設計の詳細な説明この記事では、eコマースプラットフォームでのSKUとSPUのデータベース設計の問題、特にユーザー定義の販売を扱う方法について説明します。

Redisキャッシュソリューションは、製品ランキングリストの要件をどのように実現しますか?開発プロセス中に、多くの場合、ランキングの要件に対処する必要があります。
