10

私のアプリケーションは、FFT を使用した (コストのかかる) 変換後にベクトルを乗算します。その結果、私が書くとき

f :: (Num a) => a -> [a] -> [a]
f c xs = map (c*) xs

cのすべての要素ではなく、一度だけの FFT を計算したいxs。cプログラム全体の FFT をローカル スコープに保存する必要はまったくありません。

私は自分のNumインスタンスを次のように定義しようとしました:

data Foo = Scalar c
         | Vec Bool v -- the bool indicates which domain v is in

instance Num Foo where
    (*) (Scalar c) = \x -> case x of
                         Scalar d -> Scalar (c*d)
                         Vec b v-> Vec b $ map (c*) v
    (*) v1 = let Vec True v = fft v1
             in \x -> case x of
                    Scalar d -> Vec True $ map (c*) v
                    v2 -> Vec True $ zipWith (*) v (fft v2)

次に、アプリケーションでf(任意Numの s で動作する) wherec=Vec False vに似た関数を呼び出しますf。

g :: Foo -> [Foo] -> [Foo]
g c xs = let c' = fft c
         in map (c'*) xs

この関数gはメモ化をfft c発生させ、呼び出しよりもはるかに高速ですf(どのように定義しても(*))。の何が問題なのかわかりませんf。インスタンス(*)内の私の定義ですか？Numそれはf、すべての Nums を処理することと関係があり、したがって GHC は を部分的に計算する方法を理解できません(*)か?

注: Num インスタンスのコア出力を確認したところ、(*) は実際には、最上位のラムダで FFT 変換を使用してネストされたラムダとして表されます。したがって、これは少なくともメモ化できるようです。また、バング パターンの賢明な使用と無謀な使用の両方を試みて、評価を強制的に無効にしようとしました。

補足として、最初の引数を memoize にする方法を理解できたとしても、(*)その定義方法には別の問題があります。 Foo データ型を使用したいプログラマーは、このメモ化機能について知っておく必要があります。彼女が書いたら

map (*c) xs

メモ化は発生しません。（考えてみると、私はカリー化したので(map (c*) xs))GHCがバージョンをどのように書き換えるか完全にはわかりません.しかし、両方を確認するために簡単なテストを行い、期待どおりに動作することを確認しました.最初の引数を, whileは2 番目の引数を にします. したがって問題は, メモ化を確実にするためにどのように乗算を記述すべきかが明らかでないことです. これは単に中置記法 (および への引数が対称であるという暗黙の仮定) に固有の欠点ですか?(*c)(*)(*c)(c*)(c*)c*(*c)c**

2 つ目のあまり重要でない問題は、 (v*) をスカラーのリストにマップする場合です。この場合、他の被乗数がスカラーであるため不要ですが、(うまくいけば) v の fft が計算されて格納されます。これを回避する方法はありますか？

ありがとう

4

2 に答える 2

2

私は、 stable-memoパッケージがあなたの問題を解決できると信じています。等価性を使用するのではなく、参照 ID によって値を記憶します。

ほとんどのメモコンビネータは等価性に基づいてメモ化しますが、stable-memo は以前にまったく同じ引数が関数に渡されたかどうかに基づいてメモ化します (つまり、メモリ内の同じ引数です)。

また、キーがガベージ コレクションされると、メモ化された値が自動的に削除されます。

stable-memo はこれまでに確認したキーを保持しないため、キーが使用されなくなった場合にガベージ コレクションを実行できます。これが発生した場合、メモ テーブルから対応するエントリを削除するファイナライザーが配置されます。

したがって、次のようなものを定義すると

fft = memo fft'
  where fft' = ... -- your old definition

必要なものはほとんど得られます: を呼び出すmap (c *) xsと、 への最初の呼び出し内で fft の計算がメモ化(*)され、その後の への呼び出しで再利用されます(c *)。cがガベージ コレクションされている場合は、 もそうですfft' c。

How to add fields that only cache something to ADT? へのこの回答も参照してください。

于 2013-02-26T08:11:24.093 に答える
1

メモ化を妨げる可能性のある 2 つの問題を確認できます。

まず、fオーバーロードされた型を持ち、すべてのNumインスタンスで機能します。そのfため、特殊化 (通常はSPECIALIZEプラグマが必要) またはインライン化 (自動的に行われる可能性がありますが、INLINEプラグマを使用するとより信頼性が高くなります) でない限り、メモ化を使用できません。

(*)第 2 に、 forの定義はFoo最初の引数でパターン マッチングを実行しますがf、未知数で乗算しcます。したがってf、たとえ特殊化されていても、メモ化は発生しません。f繰り返しますが、これはインライン化されていることと、具体的な引数が提供されることに大きく依存しているcため、インライン化が実際に表示されます。

だから私はあなたがどのように正確に電話をかけているのかを知るのに役立つと思いますf. が 2 つの引数を使用して定義されている場合fは、2 つの引数を指定する必要があることに注意してください。そうしないと、インライン化できません。Fooさらに、あなたが言及cしvているものであり、範囲外のものとして、の実際の定義を確認すると役立ちます。

于 2013-02-26T07:57:48.253 に答える