記憶化列表ocaml的

我有一個遞歸函數，我想在Mémoïsant記憶化列表ocaml的

我的遞歸函數重寫：

let rec sum_cube l = 
    match l with 
    | [] -> 0 
    | x :: s -> (x * x * x) + sum_cube s

，我試圖用這樣的：

let memo = Hashtbl.create 17 
let rec sum_cub_memo l = 
    try 
     Hashtbl.find memo l 
    with Not_found -> 
     let fn = function 
     | [] -> 0 
     | x::s -> (x * x * x) sum_cub_memo s 
     in 
     Hashtbl.add memo l fn 

fn ;;

我有一個錯誤：

此表達式的類型爲int list - > int但預計表達式爲int list !!

來源

2016-12-07 CamlX

這體現在哪裏？ – melpomene

啊。仔細看看'fn'。它是什麼？你怎麼使用它？ – melpomene

@melpomene Hashtbl.add memo l fn – CamlX

你應該memoize的不是功能，而是功能的結果，例如，使用sum_cube你的定義：

let sum_cube_memo xs = 
    try Hashtbl.find memo xs with Not_found -> 
    let res = sum_cube xs in 
    Hashtbl.add memo xs res; 
    res

這將工作，但有一個警告。你正在使用一個整數列表作爲關鍵。這意味着，首先密鑰被轉換爲它的散列（基本上是O（n），並且將花費與計算三次冪基本相同的時間量），其次，如果存在散列衝突，那麼每個列表中的存儲桶將與參數列表進行比較。因此，您的memoized函數與非memoized函數具有相同的複雜性，它的性能更差，同時也會消耗未綁定的內存量。這是否值得？

來源

2016-12-07 18:30:24 ivg

此表達式具有int類型，但表達式類型爲int list！ – CamlX

這是因爲（是的，我是一個oracle），你有兩個定義，一個是你的（不正確的），另一個是我的（正確的）。它們都使用相同的全局變量'備忘錄'。一個定義是試圖在'memo'中存儲'int list - > int'類型的函數，另一個（正確的）試圖存儲計算結果（類型爲「int」）。因此，如果你在頂層工作，清理，你的代碼，刪除錯誤的定義，或重新創建'備忘錄'值。 – ivg

sum_cube without memorization.

let sum_cube l = 
    let cube x =x*x*x in 
    List.fold_left (fun acc x -> acc+cube x) 0 l

sum_cube with memorization and trace.

let sum_cube l = 
    let memo = Hashtbl.create 17 in 
    let cube_memo x = 
    try 
     let xcube= Hashtbl.find memo x in 
     Printf.printf "find %d -> %d\n" x xcube; 
     xcube 
    with Not_found -> 
     let xcube=x*x*x in 
     Printf.printf "add %d -> %d\n" x xcube; 
     Hashtbl.add memo x xcube; 
     xcube 
    in 
    List.fold_left (fun acc x -> acc+cube_memo x) 0 l

測試：

# sum_cube [4;4;2;3;4;2];; 
add 4 -> 64 
find 4 -> 64 
add 2 -> 8 
add 3 -> 27 
find 4 -> 64 
find 2 -> 8 
- : int = 235

來源

2016-12-08 17:51:11

記憶化列表ocaml的

回答

相關問題