F＃在尾递归和Seq库之间的性能差异
我在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分钟。 因此，这也不是序列的错，对吧？ 那么，为什么最初的功能如此之快呢？ 由于尾递归，它不能避免构建堆栈，可以吗？ 因为我不希望有相当多的堆栈，如果有的话，也可以用慢速的例子来构建。
对我来说这没什么意义，有人能告诉我吗？
谢谢。
正如Fyodor Soikin评论的那样，在seq解决方案中为每个迭代创建一个新数组[|1..20|] 1..20 [|1..20|]是主要的罪魁祸首。 如果我定义数组并将其传入，我可以在10秒内运行它，而递归解决方案的时间为27秒。 剩余的不一致必须归结为一个懒惰序列所需的额外机制，相比于tail-call优化为for循环的递归。
使isDivisableByAll内联函数对递归解决方案（下降到6秒）产生显着差异。 它似乎不影响seq解决方案。
如果我理解正确，你试图找出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秒内运行。
链接地址: http://www.djcxy.com/p/80533.html上一篇: F# performance difference between tail recursion and Seq library