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.

---

As Fyodor Soikin commented, making a new array [|1..20|] for each iteration in the seq solution is the main culprit. If I define the array once and pass it in, I can run it in 10 seconds, compared to 27 seconds for the recursive solution. The remaining disparity must be down to the extra machinery needed around for a lazy sequence, compared to recursion that is tail-call optimised into a for loop.

Making the isDivisableByAll an inline function makes a significant difference for the recursive solution (down to 6 seconds). It doesn't seem to affect the seq solution.

---

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.

链接地址: http://www.djcxy.com/p/80534.html

上一篇: F＃递归绑定计算表达式和尾递归

下一篇: F＃在尾递归和Seq库之间的性能差异