Question

I have defined a module Comp whose operations are quite costly. In most of the cases, for a value of type Comp.t, a value of type int can be calculated, which can be used to accelarate many operations. So I define a type x as follows which represents 2 cases: 1) the integer has been calculated 2) otherwise

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

A function convert: x -> x has been written to try to calculate the integer for a Comp.t, it is possible that this integer does not exist, this function is costly as well:

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". 

Initially, a comparaison function less than can be written like this:

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 *)
...

As convert is costly, and there are many other functions than lt which may call it from time to time (e.g. le, ge), I would like to make the conversion impact the value outside. For instance, I want the lt to change the value of x0_o and x1_o, so that the functions later (e.g. le, ge) receive arguments which probably have already been converted, that results in a faster computation for the whole block.

So I guess something like mutable record should be used, could anyone give me an example? Also, in general, is it a good idea to do this (permitting side effects) to optimise the computation?

Was it helpful?

Solution

I think what you want to do is memoize (https://en.wikipedia.org/wiki/Memoization) the function Comp.convert (if it's pure):

This memoization code uses a hashtable to store the results instead of recalculating them (replaced the function Comp.convert with a very simple one to test the code):

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
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top