Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- open System
- open System.Collections.Generic
- let memoize_rec (f : ('a -> 'b) -> 'a -> 'b) =
- let m = Dictionary<'a, 'b> () in
- let rec g x =
- try
- m.[x]
- with
- | :? KeyNotFoundException ->
- let y = f g x in
- m.Add(x, y);
- y
- in
- g
- let rec fib_n = function
- 0 -> 0
- | 1 -> 1
- | n -> fib_n (n - 1) + fib_n (n - 2)
- let rec fib_s self = function
- 0 -> 0
- | 1 -> 1
- | n -> self (n - 1) + self (n - 2)
- let fib_memo = memoize_rec fib_s
- printfn "Naive."
- print_duration (fun () -> fib_n 40) |> printfn "%i"
- // Elapsed Time: 5900[ms]
- printfn "Memoized."
- print_duration (fun () -> fib_memo 40) |> printfn "%i"
- // Elapsed Time: 5[ms]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement