Your F# code is generating and then iterating a lot of IEnumerables that the C# code does not. Every call to isDivOneToTwenty generates a new IEnumerable and then iterates it to find the length, and also iterates the "divisors" sequence as well.

On my machine your F# code takes about 35 seconds. This following version takes 22 seconds. All I changed was generating "divisors" as an array (because arrays are more efficient than lists at storing value types, and because it's faster to get the length of an array than a sequence). I also generated the array in reverse order, rather than generating it and then reversing it, and I cached the count rather than recalculate it every time.

This is faster, but it's still generating and iterating an IEnumerable every time through the loop. It could be made faster yet by making the code more imperative and less functional. This is a strength of F#, in that you have the flexibility to optimize specific functions, while isolating your imperative code in such a way that it doesn't affect the rest of your program.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    let p5BruteForce2 =
        let divisors = [| 20 .. -1 .. 3 |]
        let divisorCount = Array.length divisors
        let isDivOneToTwenty n =
            let dividesBy = 
                divisors |> Seq.takeWhile (fun x -> n % x = 0)
            
            Seq.length dividesBy = divisorCount
        let findNum n =
            let rec loop n = 
                match isDivOneToTwenty n with
                | true -> n
                | false -> loop (n + 2)
            loop n

        findNum 2520
By on 11/11/2014 3:23 PM ()

Thanks to your help I was able to make further optimizations and eliminate the length comparison completely by using List.forall instead (I tried changing the List to an array but this yielded no performance boost on my computer).

Anyhow, this new code finishes in 2500ms on my machine down from 45k ms :).

1
2
3
4
5
6
7
8
9
10
11
let p5BruteForce =
    let divisors = [20..-1..3]
    let isDivOneToTwenty n = divisors |> List.forall (fun x -> n % x = 0)

    let findNum n =
        let rec loop n = 
            match isDivOneToTwenty n with
            | true -> n
            | false -> loop (n + 2)
        loop n
    findNum 2520
By on 11/11/2014 10:40 PM ()

Alternatively (leaving the "brute-force" world) you could note that what is asked is to calculate the least common multiple of the range [ 1 .. 20 ] (or [ 2 .. 20 ] because lcm(1, x) = x)

1
2
3
4
5
6
7
8
9
10
11
let rec gcd x y =
  if y = 0 then abs x
  else gcd y <| x % y

let lcm x y=
  // do division first to limit overflow risk
  x / gcd x y * y

let p5 = [ 2 .. 20 ] |> List.reduce lcm
// alternate version using statement knowledge
let p5' = [ 11 .. 20 ] |> List.fold lcm 2520
By on 11/30/2014 3:15 PM ()
IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy
Built with WebSharper