为什么这个F#代码比等价的C#代码慢

本文关键字：代码 为什么 | 更新日期: 2023-09-27 18:30:06

我又在处理Project Euler问题了（之前我在学习C#时做了23个第一个问题），我对问题5的解决方案的糟糕性能感到非常困惑。

其内容如下：

2520是可以除以每个数字的最小数字从1到10，没有任何余数。

能被所有整除的最小正数是多少从1到20的数字？

现在，我的C#的原始蛮力解决方案在大约25秒内就解决了这个问题。

var numbers = Enumerable.Range(1, 20);
int start = 1;
int result;
while (true)
{
   if (numbers.All(n => start % n == 0))
   {
       result = start;
       break;
   }
   start++;
}

现在我的F#解决方案也使用暴力强制，但至少它做了更多的区分，所以在我看来它"应该"运行得更快，但它的时钟大约为45秒，所以它的速度几乎是C#的两倍。

let p5BruteForce =
    let divisors = List.toSeq ([3..20] |> List.rev)
    let isDivOneToTwenty n =
        let dividesBy = 
            divisors |> Seq.takeWhile(fun x -> n % x = 0)                
        Seq.length dividesBy = Seq.length divisors
    let findNum n =
        let rec loop n = 
            match isDivOneToTwenty n with
            | true -> n
            | false -> loop (n + 2)
        loop n
    findNum 2520

p.S-我知道我的解决方案可能会更好，在这种情况下，我只是想知道一个更好的暴力解决方案怎么会比原始解决方案慢得多。

为什么这个F#代码比等价的C#代码慢

您可以使用List.forall，而不是转换为seq，然后执行Seq.length:

let divisors = [3..20] |> List.rev
let isDivOneToTwenty n = divisors |> List.forall (fun d -> n % d = 0)

Seq.length需要遍历整个序列来确定元素的数量，而forall可以在元素未通过谓词时立即返回。

也可以将findNum写成：

let rec findNum n = if isDivOneToTwenty n then n else findNum (n + 2)

即使是更直接的翻译，如

let numbers = { 1..20 }
let rec loop start =
    if numbers |> Seq.forall (fun n -> start % n = 0) 
    then start
    else loop (start + 1)
loop 1

需要一分半钟（你的C#版本在我的机器上也需要25秒）。数字序列似乎是罪魁祸首，因为将其更改为数组（[| 1..20 |]）并使用Array.forall会将其缩短到8秒。使用数组的C#版本需要20秒（使用我自己的数组专用ForAll方法而不是Enumerable.All需要17秒）。

编辑：在看到李的答案后，我尝试了List.forall，它甚至比数组快（~5秒）。

好吧，它一定是这个位

            divisors |> Seq.takeWhile(fun x -> n % x = 0)                
    Seq.length dividesBy = Seq.length divisors

我认为您可以将其重写为一个更简单的递归函数，它将更类似于您最初的c#实现。

相关文章：