Why is this F# code slower than the C# equivalent?

Question

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.

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.

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

P.S - I know that my solution could be better, in this case I am simply wondering how it could be that a better brute-force solution can be so much slower than a primitive one.

Note that the solution has to be a multiple of 2520 as well. Your increment can therefore be 2520 and you will be testing far fewer numbers. Even with a simple brute force solution it will go quickly. Also, you wouldn't need to test for divisibility of 1 to 10. — Mike Zboray, Nov 11 '14 at 22:34
Not an exact duplicate of [C# / F# Performance comparison](http://stackoverflow.com/questions/144227/c-sharp-f-performance-comparison). But it explains why F# is slower than C# — Black Frog, Nov 11 '14 at 22:51
@L.B Really now? You are going to come here and make a rude remark about the performance? I never claimed that it was a particularly good solution. Not everyone is born with great coding talents, maybe that's why I'm trying to learn? — Overly Excessive, Nov 12 '14 at 06:22

score 11 · Accepted Answer · answered Nov 11 '14 at 22:16

11

You can use List.forall instead of converting to a seq and then doing Seq.length:

let divisors = [3..20] |> List.rev
let isDivOneToTwenty n = divisors |> List.forall (fun d -> n % d = 0)

Seq.length will need to traverse the entire sequence to determine the number of elements, while forall can return as soon as an element fails the predicate.

you can also write findNum as:

let rec findNum n = if isDivOneToTwenty n then n else findNum (n + 2)

answered Nov 11 '14 at 22:16

Lee

142,018
20
234
287

This is it. Actually, `List.forall` makes a huge difference over `Seq.forall` in my tests. Like 100s vs 10s. – Mike Zboray Nov 11 '14 at 22:22
@mikez - Yes `takeWhile` will break early, that count is being compared to the length of the entire divisor sequence each time, so it's traversing it between one and two times on each call. – Lee Nov 11 '14 at 22:38
Yea I realized that right after I wrote my comment, so I deleted it. – Mike Zboray Nov 11 '14 at 22:50
+1. This simple change reduced running time to about 2,5seconds on my machine. This was exactly what I was looking for. – Overly Excessive Nov 12 '14 at 06:30

Daniel · Answer 2 · 2014-11-11T22:40:38.780

Even a more direct translation such as

let numbers = { 1..20 }
let rec loop start =
    if numbers |> Seq.forall (fun n -> start % n = 0) 
    then start
    else loop (start + 1)
loop 1

takes a minute and a half (your C# version takes 25 seconds on my machine too). The numeric sequence seems to be the culprit as changing it to an array ([| 1..20 |]) and using Array.forall drops it to 8 secs. The C# version using an array takes 20 secs (using my own array-specialized ForAll method instead of Enumerable.All takes 17 secs).

EDIT: After seeing Lee's answer, I tried List.forall and it's even faster than array (~5 secs).

score 0 · Answer 3 · answered Nov 11 '14 at 22:12

well it's gotta be this bit

            divisors |> Seq.takeWhile(fun x -> n % x = 0)                
    Seq.length dividesBy = Seq.length divisors

I think you could rewrite this as a simpler recursive function which would be more similar to your original c# implementation.

Why is this F# code slower than the C# equivalent?

3 Answers3