メモ化リストOCamlの

Question

私は、再帰関数を持っていると私はMémoïsant

マイ再帰関数で書き換えたい：

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リストです！

Answer 1

あなたは機能が、関数の結果をない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）に変換され、基本的には3の累乗を計算するのと同じ時間量がかかります）、次に、ハッシュの衝突がある場合は、バケットは引数リストと比較されます。その結果、あなたのメモされた機能は、あなたのメモされていない機能と同じ複雑さを持ち、パフォーマンスが悪くなり、またメモリの量も消費されます。それは価値がありますか？

Answer 2

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