尾递归和Seq库之间的F#性能差异

Question

我在F#中有这个代码,它找到了最小的正数,它可以被1到20之间的所有数字整除.它需要10秒才能完成.

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|]

所以,我认为我可以使它更优雅,因为我更喜欢更少的代码并写下以下内容.

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

花了10分钟!我无法解释巨大的差异,因为序列是懒惰的.为了调查,我写了一个命令式循环.

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

花了8分钟.因此,它也不是序列的错,对吧？那么,为什么初始函数如此之快？由于尾递归,它不能避免堆积堆栈,可以吗？因为我不希望有相当多的堆栈(如果有的话),也可以在慢速示例中构建.

这对我来说没有多大意义,有人能告诉我吗？

谢谢.

Answer 1

如果我理解正确,你试图找到1到400000000(含)之间的数字可以被1到20之间的所有数字整除.我制作了我自己的原始版本:

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

这个解决方案在我测试的地方运行需要90多秒.但我开始意识到它是Euler第5号问题的一个变体,我们知道2520是第一个可被1到10所有数字整除的数字.利用这个事实,我们可以创建一个2520的倍数序列,仅测试11到19之间的数字,因为保证倍数可以被1到10和20的所有数字整除:

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

该解决方案需要0.191秒.

如果您不了解欧拉问题编号5,您甚至可以通过算法计算具有给定起始值的倍数的元素的序列.我们为算法提供了一系列数字,这些数字可以从2到n - 1的所有数字整除,它计算第一个可被2到n的所有数字整除的数字.这是迭代直到我们有一个第一个数的倍数序列可被我们想要的所有因素整除:

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

该解决方案在0.018秒内运行.

Answer 2

正如 Fyodor Soikin 评论的那样，[|1..20|]为解决方案中的每次迭代创建一个新数组seq是罪魁祸首。如果我定义一次数组并将其传入，我可以在 10 秒内运行它，而递归解决方案则需要 27 秒。与尾部调用优化为 for 循环的递归相比，剩余的差异必须归因于惰性序列所需的额外机制。

使isDivisableByAll内联函数对递归解决方案产生显着影响（缩短至 6 秒）。看来并不影响seq解决。