1

申し訳ありませんが、この問題の説明は非常に抽象的です。それは私の仕事のためであり、商業上の機密保持上の理由から、現実世界の問題を示すことはできず、単なる抽象化です。

キーと値のペアを含むメッセージを受信するアプリケーションがあります。キーは定義済みの一連のキーワードから取得され、各キーワードには固定のデータ型があります。したがって、「Foo」が整数で「Bar」が日付の場合、次のようなメッセージが表示される可能性があります。

Foo: 234
Bar: 24 September 2011

メッセージには、キーの任意のサブセットが含まれる場合があります。キーの数はかなり多い(数十個)。しかし、今のところ Foo と Bar に固執しましょう。

明らかに、メッセージに対応する次のようなレコードがあります。

data MyRecord {
   foo :: Maybe Integer
   bar :: Maybe UTCTime
   -- ... and so on for several dozen fields.
}

そのフィールドはまだ受信されていない可能性があるため、レコードは「Maybe」タイプを使用します。

現在の値から計算する必要がある多くの派生値もあります (存在する場合)。たとえば、私はしたいです

baz :: MyRecord -> Maybe String
baz r = do -- Maybe monad
   f <- foo r
   b <- bar r
   return $ show f ++ " " ++ show b

これらの関数のいくつかは遅いので、不必要に繰り返したくありません。新しいメッセージごとに baz を再計算し、元の構造にメモすることもできますが、メッセージが foo フィールドと bar フィールドを変更しないままにしておくと、CPU 時間が無駄になります。逆に、必要なときにいつでも baz を再計算できますが、基礎となる引数が前回から変更されていない場合は、CPU 時間が無駄になります。

私が欲しいのは、引数が変更されたときにのみ baz を再計算する、ある種のスマートなメモ化またはプッシュベースの再計算です。baz は foo と bar のみに依存しているため、これらの値を変更するメッセージでのみ再計算することに注意することで、これを手動で検出できますが、エラーが発生しやすい複雑な関数の場合です。

追加の問題は、これらの関数の一部が複数の戦略を持つ可能性があることです。たとえば、「mplus」を使用して Foo または Bar から計算できる値があるとします。

これに対する既存の解​​決策を知っている人はいますか?そうでない場合、どうすればいいですか?

4

3 に答える 3

2

「状態」レコードが 1 つあり、これらのメッセージにはすべて、その更新と設定が含まれていると仮定します。したがって、Foo12である場合、後で になる可能性がある23ため、 の出力bazが変化します。これのいずれかが当てはまらない場合、答えはかなり簡単になります。

baz の「コア」から始めましょう。これは、レコードではなく、必要な値の関数です。

baz :: Int -> Int -> String

では、次のように変換してみましょう。

data Cached a b = Cached (Maybe (a,b)) (a -> b)
getCached :: Eq a => Cached a b -> a -> (b,Cached a b)
getCached c@(Cached (Just (arg,res)) f) x | x == arg = (res,c)
getCached (Cached _ f) x = let ans = f x in (ans,Cached (Just (x,ans) f)

bazC :: Cached (Int,Int) String
bazC = Cached Nothing (uncurry baz)

通常の関数を使用するときはいつでも、代わりにキャッシュ変換された関数を使用し、結果のキャッシュ変換された関数をレコードに置き換えます。これは基本的に、サイズ 1 の手動の記念品です。

あなたが説明する基本的なケースでは、これで問題ありません。

依存関係の動的グラフを含む、より洗練された、より一般化されたソリューションは、「インクリメンタル計算」という名前で呼ばれますが、本格的な製品実装よりも多くの研究論文を見てきました。手始めにこれらを見て、参照トレイルをたどることができます。

  1. http://www.carlssonia.org/ogi/Adaptive/
  2. http://www.andres-loeh.de/Incrementalization/paper_final.pdf

インクリメンタル計算は、実際には関数型リアクティブ プログラミングにも非常に関連しているため、conal の論文を参照したり、Heinrich Apfelmus のリアクティブ バナナ ライブラリで遊んだりできます: http://www.haskell.org/haskellwiki/Reactive-banana

命令型言語では、Python のトレリス: http://pypi.python.org/pypi/Trellisまたは Lisp のセル: http://common-lisp.net/project/cells/をご覧ください。

于 2012-05-18T23:35:40.973 に答える
1

私が欲しいのは、引数が変更されたときにのみ baz を再計算する、ある種のスマートなメモ化またはプッシュベースの再計算です。

一種の不変の変数が必要なように思えますが、「まだ計算されていない」から「計算された」への1回限りの変更が可能です。運がいいです: これはまさに遅延評価が与えるものです! したがって、私が提案する解決策は非常に単純です。計算したい項目ごとにフィールドを使用してレコードを拡張するだけです。これは、CPU を集中的に使用するタスクが暗号化スキームを破っている場合の例です。

data Foo = Foo
    { ciphertext :: String
    , plaintext :: String
    }

-- a smart constructor for Foo's
foo c = Foo { ciphertext = c, plaintext = crack c }

ここでのポイントは、次のfooような費用を持つように呼び出すことです。

  1. 絶対に結果を求めなければplaintext安い。
  2. への最初の呼び出しplaintextで、CPU は長時間チャーンします。
  3. 以降の の呼び出しでplaintextは、以前に計算された答えがすぐに返されます。
于 2012-05-19T00:02:45.470 に答える
1

実行する必要がある計算に対応するステートフル グラフを作成できます。新しい値が表示されたら、これらをグラフにプッシュして再計算し、出力に到達するまでグラフを更新します。(または、入力に値を保存し、オンデマンドで再計算することもできます。) これは非常にステートフルなソリューションですが、機能します。

レートなどのライブ入力から、利回り曲線などの市場データを作成している可能性がありますか?

于 2012-05-18T23:22:04.440 に答える