尾递归和 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

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

使 isDivisableByAll 成为内联函数对递归解决方案有显着影响（缩短至 6 秒）。它似乎不会影响 seq 解决方案。

Answer 2

如果我没理解错的话，你是想找出 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 秒内运行秒。

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

F# performance difference between tail recursion and Seq library

performance

f#

tail-recursion

seq