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

我认为 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();
        }
    }
}

最佳答案

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 并且不会做比获得输出绝对需要的更多的工作)。这就像在您的 C# 代码中有一个 break。

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

{2 .. 100000}

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

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

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

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

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

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

现在，请记住我们在 Seq.forall 中。因此，如果 Seq.filter 返回 true，则 i 将保留 Seq.forall 的值。但是如果 Seq.filter 返回 false，那么 i 将丢弃 (printfn "%i") 的这个值，从传递到下一步。

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

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

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

for number in inputSoFar do
    printfn "%i" number

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

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

所以 printfn "%i 总是可以替换为 Seq.iter 。而 for 相当于一个 break 循环:

inputSoFar |> Seq.iter (someFunctionCall x)

完全等同于:

for item in inputSoFar do
    someFunctionCall x item

所以你知道了:为什么你的 F# 程序更慢，以及如何编写一个 F# 程序，该程序将遵循与 C# 程序相同的逻辑，但其中将包含 0x251812231343141 语句。

关于c# - 为什么 F# 比 C# 慢这么多？ (质数基准)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51482302/