1

以下でこの循環依存を解消しようとしていますが、最善の方法がわかりません。

let cashOpeningBalance t =
if t = 1 then
    0.0
else
    cashClosingBalance (t - 1)

let cashInterest t = 
    cashOpeningBalance t * 0.03 

let accumulatedCash t =
    cashOpeningBalance t + cashInterest t

// let moreComplicatedLogic t = ...

let cashClosingBalance t =
    accumulatedCash t

この回答からいくつかのロジックを使用して、次の解決策を思いつきましたが、パフォーマンスが非常に悪いです。

let cashOpeningBalance t cashClosingBalance =
if t = 1 then
    10.0
else
    cashClosingBalance (t - 1)

let cashInterest t cashClosingBalance = 
    (cashOpeningBalance t cashClosingBalance) * 0.03 

let accumulatedCash t cashClosingBalance =
    (cashOpeningBalance t cashClosingBalance) + (cashInterest t cashClosingBalance)

// let moreComplicatedLogic t cashClosingBalance = ...

let rec cashClosingBalance t =
    //accumulatedCash t cashClosingBalance
    let temp = accumulatedCash t cashClosingBalance
    printfn "Cash Closing Balance = %f Where t = %i" temp t
    temp

cashClosingBalance 3
(*
> 
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.609000 Where t = 2
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.609000 Where t = 2
Cash Closing Balance = 10.927270 Where t = 3
val it : float = 10.92727
*)

cashClosingBalance 50
(*
Takes a really long time 
*)

以下の出力に見られるように、cashClosingBalance 関数を書き直して過度の再帰呼び出しを停止する方法はありますか? 最大 400 の t の値を入力できるようにする必要があり、それでも数秒で実行されます。

4

1 に答える 1

4

問題は、実際moreComplicatedLogicには真ん中にあるという事実ではありません (そのため、大きく書くのは不便let recです)。問題は、コードが非効率的な方法で動的プログラミング アルゴリズムを実装していることです。

再帰呼び出しcashClosingBalanceは、同じ引数で複数回呼び出すことになります (1 回だけ呼び出して結果をローカル キャッシュに保存するのではなく)。関数型プログラミングでは、メモ化のかなり一般的な概念を使用してこれを解決できますが、アルゴリズムを別の方法で書き直して、より効率的にすることができる場合があります。

メモ化を使用する場合は、次のようなものが必要です。次のヘルパーは、関数を受け取り、以前の呼び出しの結果をキャッシュする同じタイプの関数を作成します。

let memoize f = 
  let dict = System.Collections.Generic.Dictionary<_, _>() 
  fun v ->
    match dict.TryGetValue(v) with
    | true, res -> res
    | _ -> 
        let res = f v 
        dict.Add(v, res)
        res

次に、次のようにコードを書き直すことができますmemoize(すべての関数定義を単純にラップしmemoize、引数の順序を変更して、それtが最後になるようにしました):

let cashOpeningBalance cashClosingBalance = memoize (fun t ->
  if t = 1 then
    10.0
  else
    cashClosingBalance (t - 1))

let cashInterest cashClosingBalance = memoize (fun t -> 
    (cashOpeningBalance cashClosingBalance t) * 0.03 )

let accumulatedCash cashClosingBalance = memoize (fun t ->
    (cashOpeningBalance cashClosingBalance t) + (cashInterest cashClosingBalance t))

// let moreComplicatedLogic t cashClosingBalance = ...

let rec cashClosingBalance = memoize (fun t -> 
    //accumulatedCash t cashClosingBalance
    let temp = accumulatedCash cashClosingBalance t
    printfn "Cash Closing Balance = %f Where t = %i" temp t
    temp)
于 2013-09-25T00:09:37.207 に答える