Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

F# performance difference between tail recursion and Seq library

I have this code in F# which finds the smallest positive number that is evenly divisible by all of the numbers from 1 to 20. It takes 10 seconds to complete.

let isDivisableByAll num (divisors: int[]) = Array.forall (fun div -> num % div = 0) divisors

let minNumDividedBy (divisors: int[]) =  
    let rec minNumDividedByAll stopAt acc = 
        if acc >= stopAt then 0
        else if isDivisableByAll acc divisors then acc
        else minNumDividedByAll stopAt (acc + 1)
    minNumDividedByAll 400000000 1

minNumDividedBy [|1..20|]

So, I thought I could make it more elegant, because I prefer less code and wrote the following.

let answer = { 1..400000000 } 
            |> Seq.tryFind (fun el -> isDivisableByAll el [|1..20|])

It took 10 minutes! I couldn't explain the huge difference, since sequences are lazy. In an effort to investigate, I wrote an imperative loop.

let mutable i = 1
while i < 232792561 do
    if isDivisableByAll i [|1..20|] then
        printfn "%d" i
    i <- i + 1

It took 8 minutes. Therefore, it's not the sequence's fault either, right? So, why is the initial function so fast? It can't be avoiding building up the stack, due to tail recursion, can it? Because I wouldn't expect a considerable stack if any, being built in the slow examples either.

It doesn't make much sense to me, can someone tell me?

Thank you.

like image 594
chr1st0scli Avatar asked Jun 20 '16 09:06

chr1st0scli


1 Answers

If I understand correctly, you are trying to find how many numbers between 1 and 400000000 (inclusive) are divisible by all the numbers from 1 to 20. I made my own crude version of it:

let factors = Array.rev [| 2 .. 20 |]

let divisible f n =
    Array.forall (fun x -> n % x = 0) f

let solution () =
    {1 .. 400000000}
    |> Seq.filter (divisible factors)
    |> Seq.length

This solution takes over 90 seconds to run where I tested it. But I came to realize that it is a variation of Euler problem number 5, where we learn that 2520 is the first number divisible by all the numbers from 1 to 10. Using this fact, we can create a sequence of multiples of 2520, and test only the numbers from 11 to 19, as the multiples are guaranteed to be divisible by all the numbers from 1 to 10, and 20 as well:

let factors = Array.rev [| 11 .. 19 |]

let divisible f n =
    Array.forall (fun x -> n % x = 0) f

let solution () =
    Seq.initInfinite (fun i -> (i + 1) * 2520)
    |> Seq.takeWhile (fun i -> i <= 400000000)
    |> Seq.filter (divisible factors)
    |> Seq.length

This solution takes 0.191 seconds.

If you don't know about Euler problem number 5, you can even algorithmically compute sequences with elements that are multiples of a given starting value. We feed the algorithm a sequence of numbers divisible by all numbers from 2 to n - 1, and it computes the first number divisible by all numbers from 2 to n. This is iterated through until we have a sequence of multiples of the first number divisible by all the factors we want:

let narrowDown m n s =
    (s, {m .. n})
    ||> Seq.fold (fun a i ->
            let j = Seq.find (fun x -> x % i = 0) a
            Seq.initInfinite (fun i -> (i + 1) * j))

let solution () =
    Seq.initInfinite (fun i -> i + 1)
    |> narrowDown 2 20
    |> Seq.takeWhile (fun i -> i <= 400000000)
    |> Seq.length

This solution runs in 0.018 seconds.

like image 162
dumetrulo Avatar answered Sep 22 '22 02:09

dumetrulo