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

Question

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

7

我有一段 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分钟，因此，也不是序列的问题，对吧？那么，为什么初始函数会如此快呢？它不可能通过尾递归避免建立堆栈，是吗？因为我也不指望在慢的示例中建立任何可观的堆栈。

这对我来说没有太多意义，有人能告诉我原因吗？

谢谢。

- chr1st0scli

4

第二个例子中，每次迭代都会分配一个新的数组。在这么多次迭代中，这些开销需要累加起来。尝试先创建数组，然后再运行迭代。 - Fyodor Soikin

1

懒惰 = 不快速 :-) - s952163

1

当然，有一种更简单的方法可以通过算法改变来实现这个。 - John Palmer

2

迭代循环仍会生成大量的数组 - 如果你将 [|1..20|] 移到循环外面，我认为速度会更快。 - John Palmer

2个回答

4

正如Fyodor Soikin所评论的那样，在“seq”解决方案中，为每次迭代制作一个新数组“[|1..20|]”是主要问题。如果我定义一次数组并将其传递进去，我可以在10秒内运行它，而递归解决方案需要27秒。剩下的差异必须是由于惰性序列周围需要额外的机制，而递归则是尾调用优化成for循环。

使“isDivisableByAll”成为内联函数对递归解决方案有显着影响（降至6秒）。似乎对“seq”解决方案没有影响。

- TheQuickBrownFox

天啊，我以为我已经尝试将数组推导式移出去了，但显然我没有。谢谢你。 - chr1st0scli

1

可以想象F#会为“Seq”表达式创建一个有效的循环，但目前它并没有这样做。相反，创建了一个Seq，正如@TheQuickBrownFox所说，枚举它的开销可能解释了差异（2个虚拟调用和F#Seq实现似乎不如LINQ有效）。话虽如此，通过改变计算答案的方式，您可以使用“Seq”，并在不到1毫秒内生成答案。 - Just another metaprogrammer

3

你可以尝试使用Nessos的“Streams”并查看其效果如何。 - Just another metaprogrammer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dumetrulo · Accepted Answer

如果我理解正确，你正在尝试找出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秒。