performance - 尾递归和 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 秒才能在我测试过的地方运行。但我开始意识到这是欧拉问题 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 秒。