帶有商店的模塊

從某個值計算屬性的成本很高。所以一旦計算出來，最好能夠存儲這個屬性。我想知道如何正確編碼。帶有商店的模塊

舉個例子吧。假設我們有一個整數類型，很多時候，我們需要計算這種類型的值的主要因素（假設負整數的首要因素是None）：

module I = 
struct 
    type t = C of int 
    type pf = (int list) option 

    let calculate_prime_factors (x: t) : pf = 
    (* a costly function to calculate prime factors *) 
    ... ... 

    let get_prime_factors (x: t) : pf = 
    calculate_prime_factors x 
end 

let() = 
    let v = I.C 100 in 
    let pf_1 = I.get_prime_factors v in 
    let pf_2 = I.get_prime_factors v in 
    let pf_3 = I.get_prime_factors v in 
    ...

目前，get_prime_factors只是調用calculate_prime_factors，因此，所有pf_1,pf_2,pf_3的計算是耗時的。我希望有一種機制來啓用在模塊內部存儲素數因子，以便只要整數不變，第二次和第三次只讀取已存儲的內容。

有誰知道如何修改模塊I來達到這個目的？

有可能我們需要引用來使此機制成爲可能（例如，let vr = ref (I.C 100) in ...）。我可以使用引用。但是，如果保持值（即!vr）發生變化，我不知道如何自動觸發calculate_prime_factors。

來源

2016-03-11 SoftTimur

的樣子，你正在尋找這種解決方案：

module I = struct 
    type t = { 
    c : int; 
    mutable result : int option; 
    } 

    let create c = {c; result = None} 

    let calculate_prime_factors t = match t.result with 
    | Some r -> r 
    | None -> 
     let r = do_calculate t.c in 
     t.result <- Some r; 
     r 
end

這就是所謂的memoizing。通過Lazy的計算，這個特殊的例子可以更容易地解決。

module I = struct 
    type t = int Lazy.t 
    let create c = lazy (do_calculate c) 
    let calculate_prime_factors = Lazy.force 
    end

來源

2016-03-11 13:16:37 ivg

我會做到以下幾點：

let get_prime_factors x = 
    match get x with 
    | None -> 
    let res = calculate_prime_factors x 
    in 
    begin 
     set x res ; 
     res 
    end 
    | Some res -> res 
;;

您需要通過get和set訪問的可變數據結構。例如，對於名單上的引用（但你可能更喜歡一個哈希表）：

let my_storage = ref [] (* or something mutable *) 

let get x = 
    if List.mem_assoc x !my_storage 
    then Some (List.assoc x !my_storage) 
    else None 

let set x r = 
    my_storage := (x,r) :: !my_storage ;;

您還可以使用異常，而不是在option類型（None和Some _）。

來源

2016-03-11 12:18:08

感謝您的解決方案，它存儲了一對整數及其主要因素外。它應該工作，但我寧願尋找一種機制，將結果存儲在模塊內... – SoftTimur

我不明白你的意思。你可以把'my_storage'放在模塊中。 –

我試圖找出一個記錄類型爲「{v：t; pf：pf}'在模塊'I'內。因此，整數'v'及其素數因子'pf'總是一起存儲。這就是我所說的「模塊內部」... – SoftTimur

你想要做的是memoization，不是嗎？

你可以試試這個：

module I = 
    struct 

    type t = C of int 
    type pf = (int list) option 

    let calculate_prime_factors (x: t) : pf = 
    (* a costly function to calculate prime factors *) 
    ... ... 

    module HI = Hashtbl.Make (struct 
    type t = C of int 
    let equal = (=) 
    let hash (C x) = x 
    end) 

    let get_prime_factors = 
    let h = Hashtbl.create 17 in 
    fun x -> 
     try Hashtbl.find h x 
    with 
     Not_found -> let pf = calculate_prime_factors x in 
        Hashtbl.add h x pf; 
        pf 
end 

let() = 
    let v = I.C 100 in 
    let pf_1 = I.get_prime_factors v in 
    let pf_2 = I.get_prime_factors v in 
    let pf_3 = I.get_prime_factors v in 
    ...

你能適應它的負整數（有例外，例如，這比選擇更好），但我希望你的想法。

來源

2016-03-11 13:14:46 Lhooq

帶有商店的模塊

回答

相關問題