F#でメモ化(ConditionalWeakTable)
プログラムの高速化のため、一度計算した値を再利用することはしばしばあります。
しかし結果を状態として保存する必要があるため、F#では少し扱いにくいです。
そこで、ある関数を結果を再利用する関数に変換する、memoize関数を定義してみたいと思います。
memoize関数
入力と結果をDictionaryに保存しておく関数に変換しています。
またConditionalWeakTableを利用することにより、selectKeyで寿命を共にするオブジェクトを指定できるようになっています。
let memoize (f : 'Args -> 'Result) (selectKey : 'Args -> 'Key) = let table = ConditionalWeakTable<'Key, Dictionary<'Args, 'Result>>() fun (args : 'Args) -> let key = selectKey args let dictionary = table.GetOrCreateValue(key) if dictionary.ContainsKey(args) = false then dictionary.[args] <- f args dictionary.[args]
利用しやすいように、複数入力に対応した関数を用意しておきます。(寿命は第一引数と同じになります。)
let memoize1 (f : 'Arg -> 'Result) = memoize f id let memoize2 (f : 'Arg1 -> 'Arg2 -> 'Result) = let tupled = memoize (fun (x1, x2) -> f x1 x2) fst fun x1 x2 -> tupled (x1, x2) let memoize3 (f : 'Arg1 -> 'Arg2 -> 'Arg3 -> 'Result) = let tupled = memoize (fun (x1, x2, x3) -> f x1 x2 x3) (fun (x, _, _) -> x) fun x1 x2 x3 -> tupled (x1, x2, x3)
実際の利用
下記のようなNameレコードを例にしてみます。
フルネームを作成するfull関数は、二度目以降は結果を再利用しています。
また計算結果はNameオブジェクトと寿命が同じになります。
type Name = { First : string Last : string } module Name = let full = memoize1 (fun name -> printf "called\n" name.First + name.Last)
let name = { First = "John"; Last = "Smith" } let full = Name.full name // called let full2 = Name.full name
入力に参照型がない場合
今回はConditionalWeakTableを利用したため、寿命を共にする参照型の入力が必要となります。
寿命がなく、入力と結果が共にサイズが小さいのであれば、Dictionaryで管理してもいいと思われます。