4

我定义了一个模块Comp，它的操作成本很高。在大多数情况下，对于 typeComp.t的值，int可以计算出 type 的值，这可以用于加速许多操作。所以我定义了一个类型x如下，它代表 2 种情况：1）整数已经计算出来 2）否则

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

convert: x -> x已经编写了一个函数来尝试计算 a 的整数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成本高昂，并且有许多其他功能lt可能会不时调用它（例如le，ge），我想让转换影响外部价值。例如，我希望lt更改 and 的值x0_o，x1_o以便稍后的函数（例如le）ge接收可能已经转换的参数，从而加快整个块的计算速度。

所以我想应该使用可变记录之类的东西，谁能给我一个例子？另外，一般来说，这样做（允许副作用）来优化计算是一个好主意吗？

4

1 回答 1

2

我认为你想要做的是记忆（ https://en.wikipedia.org/wiki/Memoization）函数 Comp.convert （如果它是纯的）：

这个记忆代码使​​用哈希表来存储结果而不是重新计算它们（用一个非常简单的函数替换了函数 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 回答