4

Comp操作にかなりのコストがかかるモジュールを定義しました。ほとんどの場合、 typeComp.tの値に対して type の値をint計算でき、これを使用して多くの操作を高速化できます。そこで、x2 つのケースを表す型を次のように定義します。1) 整数が計算されている 2) そうでない場合

type x = A of (Comp.t, int) | B of Comp.t

a の整数を計算しようとする関数convert: x -> xが作成されましたComp.t。この整数が存在しない可能性があります。この関数もコストがかかります。

let convert (v: x): x =
  match v with
  | A _ -> v
  | B c -> 
    try to calculate the integer "i" from "c", 
    return "A (c, i)" if the integer is found; otherwise, return "B c".

最初に、比較関数は次のless thanように記述できます。

open Comp

let lt (x0: x) (x1: x): bool =
  let x0, x1 = Comp.convert x0, Comp.convert x1 in
  match x0, x1 with
    | A (c0, i0), A (c1, i1) -> 
      i0 < i1 (* which is very fast *)
    | A (c0, _), B c1 | B c0, A (c1, _) | B c0, B c1 -> 
      Comp.lt c0 c1 (* which is quite slow *)

...
let b0 = lt x0_o x1_o in
let b1 = le x0_o x1_o in (* "le" call "convert" too *) 
let b2 = ge x0_o x1_o in (* "ge" call "convert" too *)
...

コストがかかり、時々呼び出す可能性のあるconvert関数以外にも多くの関数があるため(たとえば、)、変換が値に影響を与えるようにしたいと考えています。たとえば、 と の値を変更して、後で関数 (たとえば 、 ) がおそらく既に変換された引数を受け取るようにしたいので、ブロック全体の計算が高速になります。ltlegeltx0_ox1_olege

変更可能なレコードのようなものを使用する必要があると思いますが、誰かに例を教えてもらえますか? また、一般的に、計算を最適化するためにこれを行う (副作用を許容する) ことは良い考えですか?

4

1 に答える 1

2

あなたがやりたいことは、関数 Comp.convert (純粋な場合) を memoize ( https://en.wikipedia.org/wiki/Memoization ) することだと思います:

このメモ化コードは、結果を再計算するのではなく、ハッシュテーブルを使用して結果を保存します (関数 Comp.convert を非常に単純なものに置き換えて、コードをテストします)。

let convert x = x +  3

let convert_m' () = 
  let tbl = Hashtbl.create 100 in
  (fun x -> if Hashtbl.mem tbl x then Hashtbl.find tbl x else 
      begin 
        let n = convert x in
        Hashtbl.add tbl x n;
        n 
      end
  )

let convert_m = convert_m' ()
let b = convert_m 6
于 2013-06-25T20:01:27.550 に答える