c# - 为什么 F# 比 C# 慢这么多？ (质数基准)

Question

我认为 F# 应该比 C# 更快，我制作了一个可能很糟糕的基准测试工具，C# 得到了 16239 毫秒，而 F# 在 49583 毫秒时表现更差。有人能解释一下这是为什么吗？我正在考虑离开 F# 并回到 C#。是否可以使用更快的代码在 F# 中获得相同的结果？

这是我使用的代码，我尽可能让它相等。

F#(49583 毫秒)

open System
open System.Diagnostics

let stopwatch = new Stopwatch()
stopwatch.Start()

let mutable isPrime = true

for i in 2 .. 100000 do
    for j in 2 .. i do
        if i <> j && i % j = 0 then
            isPrime <- false
    if isPrime then
        printfn "%i" i
    isPrime <- true

stopwatch.Stop()
printfn "Elapsed time: %ims" stopwatch.ElapsedMilliseconds

Console.ReadKey() |> ignore

C#(16239 毫秒)

using System;
using System.Diagnostics;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();

            bool isPrime = true;

            for (int i = 2; i <= 100000; i++)
            {
                for (int j = 2; j <= i; j++)
                {
                    if (i != j && i % j == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    Console.WriteLine(i);
                }
                isPrime = true;
            }
            stopwatch.Stop();
            Console.WriteLine("Elapsed time: " + stopwatch.ElapsedMilliseconds + "ms");
            Console.ReadKey();
        }
    }
}

Answer 1

F# 程序较慢，因为您的程序不等效。你的 C# 代码有一个 break内部声明 for循环，但您的 F# 程序没有。因此，对于每个偶数，C# 代码将在检查可被 2 整除后停止，而 F# 程序将检查从 2 到 i 的每个数字。 .由于完成的工作有如此大的差异，实际上令人惊讶的是 F# 代码仅慢了三倍!

现在，F# 故意没有 break语句，因此您无法将 C# 代码直接转换为 F#。但是您可以使用包含短路逻辑的函数。例如，在评论中，Aaron M. Eshbach 提出了以下建议:

{2 .. 100000}
|> Seq.filter (fun i -> {2 .. i-1} |> Seq.forall (fun j -> i % j <> 0))
|> Seq.iter (printfn "%i")

这使用 Seq.forall ，它确实做了短路:它会根据条件检查序列中的每个输入，如果条件返回 false ，它将停止并且不再进行检查。 (因为 Seq 模块中的函数是 lazy 并且不会做比获得输出绝对需要的更多的工作)。这就像拥有一个 break在你的 C# 代码中。

我将逐步完成此操作，以便您了解它是如何工作的:

{2 .. 100000}

这将创建一个惰性整数序列，从 2 开始并上升到(并包括)100000。

|> Seq.filter (fun i -> (some expression involving i))

我将下一行分成两部分:外部 Seq.filter部分，以及涉及 i的内在表达. Seq.filter part 获取序列并对其进行过滤:对于序列中的每个项目，将其命名为 i并评估表达式。如果该表达式的计算结果为 true ，然后保留该项目并将其传递到链中的下一步。如果表达式是 false ，然后扔掉那个东西。

现在，涉及 i 的表达式是:

{2 .. i-1} |> Seq.forall (fun j -> i % j <> 0)

这首先构造了一个从 2 开始一直到 i 的惰性序列。减一，包括在内。 (或者你可以把它想象成从 2 开始直到 i ，但不包括 i )。然后检查该序列的每个项目是否满足特定条件(即 Seq.forall 函数)。并且，作为 Seq.forall 的实现细节，因为它很懒惰并且没有做比绝对必须做的更多的工作，所以在它找到 false 的那一刻结果它将停止并且不再通过输入序列。 (因为一旦你找到了一个反例， forall 函数就不可能再返回真了，所以一旦知道它的结果它就会停止。)以及在 Seq.forall 中检查的表达式是什么？ ?它是 fun j -> i % j <> 0 .所以 j是内部循环变量， i是外部变量(在 Seq.filter 部分分配的变量)，逻辑与您的 C# 循环相同。

现在，请记住我们在 Seq.filter 中这里。所以如果 Seq.forall返回真，然后 Seq.filter将保留 i 的值.但如果 Seq.forall返回 false，然后 Seq.filter将丢弃 i 的这个值从通过到下一步。

最后，我们将这一行作为下一步(也是最后一步):

|> Seq.iter (printfn "%i")

这与以下内容几乎完全相同:

for number in inputSoFar do
    printfn "%i" number

(printfn "%i")如果您不熟悉 F#， call 对您来说可能看起来不寻常。这是 currying ，这是一个非常有用的概念，习惯它很重要。所以花点时间思考一下:在F#中，下面两行代码是完全等价的:

(fun y -> someFunctionCall x y)
(someFunctionCall x)

所以 fun item -> printfn "%i" item可以随时替换为 printfn "%i .和 Seq.iter相当于 for环形:

inputSoFar |> Seq.iter (someFunctionCall x)

完全等同于:

for item in inputSoFar do
    someFunctionCall x item

所以你知道了:为什么你的 F# 程序更慢，以及如何编写一个 F# 程序，该程序将遵循与 C# 相同的逻辑，但具有等效的 break其中的声明。