16

メモ化および継続渡しスタイル（CPS）関数の例を関数型言語で記述しているときに、両方にフィボナッチの例を使用することになりました。ただし、ループは指数関数的に頻繁に実行する必要があるため、フィボナッチはCPSの恩恵を実際には受けませんが、メモ化では、最初はO（n）のみで、その後は毎回O（1）になります。

CPSとメモ化の両方を組み合わせると、フィボナッチにわずかなメリットがありますが、CPSがスタックの不足を防ぎ、パフォーマンスを向上させる最善の方法であり、メモ化が解決策ではない例はありますか？

または：どちらか一方、または両方をいつ選択するかについてのガイドラインはありますか？

4

2 に答える 2

45

CPSについて

CPS はコンパイラの中間言語として役立ちますが、ソース言語レベルでは、(1) 洗練された制御フロー (実際にはパフォーマンスに関連しない) をエンコードし、(2) 末尾呼び出しを消費しないスタックを変換するためのデバイスであることがほとんどです。ヒープスペースを消費する継続割り当てテールコールにスペースを追加します。たとえば、書くとき（コードはテストされていません）

let rec fib = function
  | 0 | 1 -> 1
  | n -> fib (n-1) + fib (n-2)

let rec fib_cps n k = match n with
  | 0 | 1 -> k 1
  | n -> fib_cps (n-1) (fun a -> fib_cps (n-2) (fun b -> k (a+b)))

fib (n-2)新しいスタック フレームを割り当てた前の non-tail-callはfib (n-2) (fun b -> k (a+b))、クロージャーをfun b -> k (a+b)(ヒープ上に) 割り当てて引数として渡す tail-call に変わります。

これにより、プログラムのメモリ使用量が漸近的に減少するわけではありません (ドメイン固有の最適化がさらに行われる可能性がありますが、それは別の話です) 。スタック スペースをヒープ スペースと交換しているだけです。これは、スタック スペースが OS によって厳しく制限されているシステムでは興味深いものです (SML/NJ などの ML の一部の実装では、代わりにヒープでコール スタックを追跡します)。追加の GC コストと潜在的な局所性の低下により、パフォーマンスが低下する可能性があります。

CPS 変換によってパフォーマンスが大幅に向上する可能性は低く (実装とランタイム システムの詳細によっては改善される可能性があります)、一般的に適用可能な変換であり、呼び出しスタックが深い再帰関数の厄介な「スタック オーバーフロー」を回避できます。

メモ化について

メモ化は、再帰関数のサブコールの共有を導入するのに役立ちます。再帰関数は通常n、問題をすぐに解決できるいくつかの基本ケースを使用して、いくつかの厳密に単純な「サブ問題」(再帰サブコール) に分解することにより、「問題」(「" のフィボナッチを計算する」など) を解決します。

再帰関数 (または問題の再帰定式化) については、部分問題空間の構造を観察できます。結果を返すためFib(k)に必要な のより単純なインスタンスはどれですか? Fib(n)これらのインスタンスが次に必要とする単純なインスタンスはどれですか?

一般に、この部分問題の空間はグラフです (通常、終了目的では非循環です)。複数の親を持つノードがいくつかあります。これは、それらが部分問題であるいくつかの異なる問題です。たとえば、はとFib(n-2)の両方の副問題です。このグラフのノード共有の量は、特定の問題/再帰関数によって異なります。フィボナッチの場合、すべてのノードが 2 つの親の間で共有されるため、多くの共有があります。Fib(n)Fib(n-2)

メモ化なしの直接再帰呼び出しでは、この共有を観察できません。再帰関数の呼び出しの構造は、グラフではなくツリーであり、 のような共有部分問題Fib(n-2)は、完全に数回 (グラフ内の開始ノードから部分問題ノードへのパスが存在するのと同じ数だけ) 訪問されます。メモ化は、一部のサブコールが「このノードを既に計算しており、結果はこちら」で直接返されるようにすることで共有を導入します。共有が多い問題の場合、これにより (無駄な) 計算が劇的に削減される可能性があります: メモ化が導入されると、フィボナッチは指数関数的複雑度から線形複雑度に移行します -- メモ化を使用せずに関数を記述する他の方法があることに注意してください。線形の複雑さを持つために、異なるサブコール構造。

let rec fib_pair = function
  | 0 -> (1,1)
  | n -> let (u,v) = fib_pair (n-1) in (v,u+v)

サブ計算の無用な重複を避けるために何らかの形式の共有 (通常は結果を格納する大きなテーブルを介して) を使用する手法は、アルゴリズム コミュニティではよく知られており、動的プログラミングと呼ばれています。問題がこの処理に適していることを認識した場合 (サブ問題間の共有に気付いた場合)、これによりパフォーマンスが大幅に向上します。

比較に意味はありますか？

この 2 つはほとんど独立しているように見えます。

部分問題のグラフ構造は共有を持たない (木である) ため、メモ化が適用できない問題がたくさんあります。反対に、CPS 変換はすべての再帰関数に適用できますが、それ自体がパフォーマンス上の利点をもたらすわけではありません (使用している特定の実装とランタイム システムによる潜在的な定数要因を除きますが、コードを作成する可能性があります)。速いというよりは遅い）。

末尾以外のコンテキストを検査してパフォーマンスを改善する

再帰関数のパフォーマンスを向上させることができる CPS に関連する最適化手法があります。それらは、再帰呼び出しの後に「行わなければならない」計算 (単純な CPS スタイルの関数に変換されるもの) を調べ、体系的なクロージャの割り当てに至らない代替のより効率的な表現を見つけることで構成されます。たとえば、次のように考えてください。

let rec length = function
  | [] -> 0
  | _::t -> 1 + length t

let rec length_cps li k = match li with
  | [] -> k 0
  | _::t -> length_cps t (fun a -> k (a + 1))

非再帰呼び出しのコンテキスト、つまり[_ + 1]は単純な構造を持っていることに気付くでしょう: 整数を追加します。これを function として表す代わりに、関数の代わりに整数fun a -> k (a+1)を作成して、この関数のいくつかの適用に対応して追加される整数を格納するだけですk。

let rec length_acc li k = match li with
  | [] -> k + 0
  | _::t -> length_acc t (k + 1)

この関数は、線形ではなく一定の空間で実行されます。テール コンテキストの表現を関数から整数に変えることで、メモリ使用量を線形にする割り当て手順を排除しました。

追加が実行される順序を詳しく調べると、それらが異なる方向で実行されていることがわかります。リストの先頭に対応する 1 を最初に追加し、cpsバージョンでは最後に追加していました。は連想演算であるため、この順序反転は有効です_ + 1(複数のネストされたコンテキスト がある場合は、内側または外側foo + 1 + 1 + 1のいずれかから計算を開始することが有効です)。上記の最適化は、末尾呼び出し以外のすべての「連想」コンテキストに使用できます。((foo+1)+1)+1foo+(1+(1+1))

同じアイデアに基づいて利用可能な他の最適化が確かにあり (私はそのような最適化の専門家ではありません)、関連する継続の構造を調べ、ヒープに割り当てられた関数よりも効率的な形式でそれらを表現します。

これは、メモリ消費量を変更せずに、継続の表現を関数からデータ構造に変更する「非機能化」の変換に関連しています (非機能化されたプログラムは、元のプログラムでクロージャが割り当てられている場合にデータ ノードを割り当てます)。ただし、末尾再帰 CPS バージョンを一次言語 (一次関数なし) で表現することができ、データ構造とパターン マッチングがクロージャー割り当てと間接呼び出しよりも効率的なシステムでより効率的になる可能性があります。

type length_cont =
  | Linit
  | Lcons of length_cont

let rec length_cps_defun li k = match li with
  | [] -> length_cont_eval 0 k
  | _::t -> length_cps_defun t (Lcons k)
and length_cont_eval acc = function
  | Linit -> acc
  | Lcons k -> length_cont_eval (acc+1) k

let length li = length_cps_defun li Linit

type fib_cont =
  | Finit
  | Fminus1 of int * fib_cont
  | Fminus2 of fib_cont * int

let rec fib_cps_defun n k = match n with
  | 0 | 1 -> fib_cont_eval 1 k
  | n -> fib_cps_defun (n-1) (Fminus1 (n, k))
and fib_cont_eval acc = function
  | Finit -> acc
  | Fminus1 (n, k) -> fib_cps_defun (n-2) (Fminus2 (k, acc))
  | Fminus2 (k, acc') -> fib_cont_eval (acc+acc') k

let fib n = fib_cps_defun n Finit
于 2013-02-09T12:34:54.533 に答える
2

CPS の利点の 1 つは、エラー処理です。失敗する必要がある場合は、failure メソッドを呼び出すだけです。

最大の状況は、メモ化が優れている計算について話していないときだと思います。代わりに IO やその他の操作について話している場合、CPS の利点はありますが、メモ化は機能しません。

CPS とメモ化の両方が適用可能で、CPS の方が優れている場合については、私はそれらを異なる機能と見なしているため、わかりません。

最後に、F# では末尾再帰によってスタック オーバーフロー全体が問題にならないため、CPS が少し減少しています。

于 2013-02-08T21:54:29.153 に答える