Back to Questions
3.8k
views3
comments
Why is this F# code so much slower than C# equivalent?
f#c#project euler

I'm very new to functional programming coming from C#. I'm tackling the Project Euler problems again (did the 23 first ones before when I was learning C#) and I'm quite baffled at the subpar performance of my solution to problem 5.

It reads as follow:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Now my incredibly primitive brute-force solution of C# tugs through this problem in roughly 25 seconds.

1
2
3
4
5
6
7
8
9
10
11
12

var numbers = Enumerable.Range(1, 20);
int start = 1;
int result;
while (true)
{
   if (numbers.All(n => start % n == 0))
   {
       result = start;
       break;
   }
   start++;
}

Now my F# solution uses brute forcing as well but at least it does a bit more discrimination and such so that it "should" in my mind run faster but it clocks out at ~45 secs so it's nearly twice as slow as the C# one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

let p5BruteForce =
    let divisors = List.toSeq ([3..20] |> List.rev)
    let isDivOneToTwenty n =
        let dividesBy = 
            divisors |> Seq.takeWhile(fun x -> n % x = 0)
            
        Seq.length dividesBy = Seq.length divisors
    let findNum n =
        let rec loop n = 
            match isDivOneToTwenty n with
            | true -> n
            | false -> loop (n + 2)
        loop n
    findNum 2520
.

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 ()

    Topic tags

    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