Rash thoughts about .NET, C#, F# and Dynamics NAV.

"Every solution will only lead to new problems."

Monday, 8. December 2008

Project Euler in F# – Problem 53 – Memoization

Filed under: F#,Theoretische — Steffen Forkmann at 17:16 Uhr

Last time I showed how one can solve the Euler Project – problem 53 with the help of Dynamic Programming and a two-dimensional array. This time I will use another technique called (automatic) memoization.

First of all I need a memoization-function. There are two different approaches, one with a System.Collections.Generic.Dictionary and one with an immutable Map. You can read Don Syme’s blog posting to get more information about the differences.

let memoizeWithMap f =
  let cache = ref Map.empty
  fun x ->
    match (!cache).TryFind(x) with
      | Some res -> res
      | None ->
           let res = f x
           cache := (!cache).Add(x,res)
open System.Collections.Generic

let memoizeWithDictionary f =
  let cache = Dictionary<_, _>()
  fun x ->
    let (found,result) = cache.TryGetValue(x)
    if found then
      let res = f x
      cache.[x] <- res

With the help of one of this generic memoization-functions I can create a recursive function for the binomial coefficients, which memoizes intermediate data:

let rec binomial =
  let f (n,k) =
    if k = 0I || n = k then
      binomial(n - 1I,k) + binomial(n - 1I,k - 1I)
  f |> memoizeWithDictionary

let answer =
      seq { for n in 2I .. 100I do
              for k in 2I .. n -> n,k }
       |> Seq.filter (fun (a,b) -> binomial (a,b) > 1000000I )
       |> Seq.length

answer |> printf "Answer: %A"

It turns out that memoizeWithDictionary is much faster for this problem. But with 160ms it is still slower than the comparable version with a two-dimensional array (45ms).

Tags: , , ,

No Comments »

No comments yet.

RSS feed for comments on this post. | TrackBack URI

Leave a comment

XHTML ( You can use these tags): <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> .