为什么这个F#代码比C#代码慢？

Question

我正在解决项目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

PS - 我知道我的解决方案可能会更好,在这种情况下,我只是想知道一个更好的蛮力解决方案可能比原始解决方案慢得多.

Answer 1

您可以使用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)