11

Haskell で配列を使用したキャッシング (メモ化) の実装について質問があります。次のパターンが機能します。

f = (fA !)
  where fA = listArray...

しかし、これはそうではありません（プログラムの速度は、呼び出しごとに配列が再作成されていることを示唆しています）：

f n = (fA ! n)
  where fA = listArray...

where句の外側（「グローバルスコープ」内）でfAを定義することも、どちらのパターンでも機能します。

上記の 2 つのパターンの違いについて、誰かが技術的な説明をしてくれることを期待していました。

私は最新の GHC を使用していることに注意してください。これが単なるコンパイラの特性なのか、それとも言語自体の一部なのかはわかりません。

編集： ！は配列アクセスに使用されるため、 fA ! 5 は、C++ 構文の fA[5] を意味します。Haskell についての私の理解では、(fA !) n は (fA ! n) と同じであるということです...また、"fn = fA ! n" (括弧なし) と書く方がより一般的でした。とにかく、どのように括弧を付けても同じ動作になります。

4

3 に答える 3

8

動作の違いは、Haskell 標準では指定されていません。言わなければならないのは、機能が同じであるということだけです（同じ入力が与えられた場合、同じ出力になります）。

ただし、この場合、ほとんどのコンパイラが準拠している時間とメモリ パフォーマンスを予測する簡単な方法があります。繰り返しますが、これは必須ではなく、ほとんどのコンパイラが行っていることだけを強調します。

まず、セクションを展開して、2 つの例を純粋なラムダ式として書き直します。

f = let fA = listArray ... in \n -> fA ! n
f' = \n -> let fA = listArray ... in fA ! n

コンパイラは let バインディングを使用して共有を示します。保証は、特定の環境 (ローカル変数のセット、ラムダ本体など) では、パラメーターのない let バインディングの右側が最大 1 回評価されることです。前者の fA の環境はラムダの下にないためプログラム全体ですが、後者の環境はラムダの下にあるため小さくなります。

これが意味することは、後者では fAが異なる n ごとに 1 回評価される可能性があるのに対し、前者ではこれが禁止されているということです 。

このパターンは、多引数関数でも有効であることがわかります。

g x y = (a ! y) where a = [ x ^ y' | y' <- [0..] ]
g' x = (\y -> a ! y) where a = [ x ^ y' | y' <- [0..] ]

次に:

let k = g 2 in k 100 + k 100

2^100 を複数回計算する場合がありますが、次のようになります。

let k = g' 2 in k 100 + k 100

一度だけ計算します。

メモ化の作業をしている場合は、Hackage の data-memocombinators をお勧めします。これは、さまざまな形状のメモ テーブルのライブラリであり、独自に作成する必要はありません。

于 2008-11-21T12:01:39.350 に答える
5

何が起こっているかを見つける最良の方法は、コンパイラに中間表現をで出力するように指示すること-v4です。出力は膨大で読みにくいですが、生成されたコードの違いと、コンパイラーがどのようにそこに到達したかを正確に知ることができるはずです。

fA最初の例では、それが関数の外（「グローバルスコープ」）に移動されていることに気付くでしょう。2番目の例では、おそらくそうではありません（つまり、呼び出しごとに再作成されます）。

関数の外に移動されない理由の1つは、コンパイラーが。の値に依存すると考えているためですn。あなたの実際の例では、依存する必要はありませnんfA。

fAしかし、コンパイラが2番目の例で外部への移動を回避していると思う理由は、スペースリークを回避しようとしているためです。配列の代わりに、（演算子fAを使用した）無限のリストである場合にどうなるかを考えてみてください。!!一度大きな番号（たとえばf 10000）で呼び出し、後で小さな番号（、、 ...）でのみ呼び出したとf 2想像しf 3てください。f 12以前の呼び出しからの10000要素はまだメモリ上にあり、スペースを浪費しています。したがって、これを回避するために、fA関数を呼び出すたびにコンパイラが再度作成します。

スペースリークの回避は、最初の例ではおそらく発生しません。その場合f、実際には1回だけ呼び出され、クロージャが返されます（現在、純粋関数と命令型の世界の最前線にいるため、状況はもう少し微妙になります） 。このクロージャーは、元の関数を置き換えます。元の関数は二度と呼び出されないため、fA一度だけ呼び出されます（したがって、オプティマイザーは関数の外に自由に移動できます）。2番目の例では、fはクロージャに置き換えられません（その値は引数に依存するため）。したがって、再び呼び出されます。

これについてもっと理解したい場合は（-v4出力を読むのに役立ちます）、Spineless Tagless G-Machineの論文（citeseer link）を参照してください。

最後の質問ですが、これはコンパイラの特性だと思います（しかし、私は間違っている可能性があります）。ただし、言語の一部でなくても、すべてのコンパイラが同じことを行ったとしても、私は驚かないでしょう。

于 2008-11-21T00:26:28.237 に答える
0

かっこいい、たくさん助けてくれたあなたの答えに感謝します、そして私は間違いなくHackageのデータメモコンビネーターをチェックします。私はC++を多用するバックグラウンドから来て、特定のプログラムでHaskellが（主に複雑さの観点から）何をするかを正確に理解するのに苦労してきました。

于 2008-11-21T19:02:21.810 に答える