5

この回答とこのwikiページは、Haskellでのメモ化の優れた紹介であることがわかりました。しかし、彼らは私に答えを期待している質問を残しています。

使用されている手法では、メモ化を保存するために使用するデータ構造を「開く」(「内部にアクセスする」など) 必要があるように思えます。たとえば、セクション 3で1はテーブル構造を実装し、 2はツリーを実装します。事前に作成されたデータ構造で同様のことを行うことは可能ですか? たとえば、これは本当に素晴らしいと思い、メモ化された値をそのような .xml ファイルに保存したいとします。構造自体を実装せずに、事前に作成されたものを使用する、このような事前に作成されたデータ構造を使用してメモ化にアプローチできますか?Data.MapMap

うまくいけば、誰かが私に考え方のヒントを与えてくれるか、またはおそらく、機能的なメモ化全般に関する私の誤解を正してくれるでしょう。

編集：私はそれを行う1つの方法を考えることができますが、それはまったくエレガントではありません：もしf :: a -> b、f' :: Map a b -> a -> (Map a b, b)最初の引数がメモ化ストレージであり、出力ペアが潜在的に更新されたストレージと計算値。この状態渡しは確かに私が望んでいるものではありません (モナドでラップすることもできると思いますが、 1と2のアプローチよりも数桁醜いです)。

編集 2:私の現在の (間違った) 考え方を表現するのに役立つかもしれません。現在、私は自分の意志に反して、非解決に自分自身を引き込むことを繰り返しているようです

import qualified Data.Map as Map
memo :: (Ord a) => [a] -> (a -> b) -> (a -> b)
memo domain f = (Map.!) storage
    where
      storage = Map.fromList (zip domain (map f domain))

これを見れば見るほど、基本的なことを誤解していることに気づきます。ほら、 my はmemoizer の1memo [True, False]と同等だと私には思えます。bool

4

1 に答える 1

3

お気づきのように、Data.Memocombinators は実際には「事前に作成された」Data.IntTrie に依存しています。同じコードを使用して、IntTrie の使用を別のデータ構造に置き換えることができると確信していますが、効率的ではない可能性があります。

メモ化の一般的な考え方は、計算結果を保存することです。Haskell でこれを行う最も簡単な方法は、パラメータごとに 1 つの次元を持つテーブルに関数をマップすることです。Haskell は怠惰なので (まあ、Haskell のほとんどのデータ構造はそうです)、指定されたセルの値は、具体的に要求された場合にのみ評価されます。「テーブル」は基本的に「マップ」を意味します。これは、キーから値に移動するためです。

[編集] 例 2 に関する追加の考え

私が間違っていなければ、最初(Map.!) storageに特定のキーの評価が強制され、storage構造が完全に絞り出されます (ただし、f特定のキー以外では計算は行われません)。したがって、最初のルックアップでは追加の O(n) 操作が発生します。n はlength domainです。その後のルックアップでは、このコストは発生しません。

典型的な int インデックス付きリストや IntTrie のような遅延構造も同様に、ルックアップが呼び出されたときに構造を明示する必要がありますが、Map とは異なり、一度にすべてを明示する必要はありません。インデックス付きキーがアクセスされるまで、リストは絞り出されます。IntTries は、目的のキーの「接頭辞」(または接尾辞? どちらの方法でも実装できるかどうかは不明) である整数キーのみを抽出します。インデックス 11、( ) は、1 ( )、2 ( )、5 ( )、および 11 ( )1011を絞り出します。を使用できるように、すべてのキーを単に Int (または「ビット」) に変換します。1101011011Data.MemocombinatorsIntTrie

ps これについて「絞り出す」よりも適切なフレーズはありますか? 「力」、「背骨」、「顕現」という言葉が頭に浮かびますが、これにぴったりの言葉やフレーズが思い浮かびません。

于 2011-04-01T14:48:42.197 に答える