c# - 为什么此 F# 代码比等效的 C# 代码慢？

Question

我正在再次解决 Project Euler 问题(在我学习 C# 之前解决了前 23 个问题)，我对问题 5 的解决方案表现不佳感到非常困惑。

内容如下:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 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 - 我知道我的解决方案可能会更好，在这种情况下，我只是想知道为什么更好的蛮力解决方案会比原始解决方案慢得多。

Answer 1

您可以使用 List.forall 而不是转换为序列然后执行 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)