Skip to content

Instantly share code, notes, and snippets.

@cannorin cannorin/memo.fs
Created Mar 29, 2017

Embed
What would you like to do?
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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.