为什么 F# 比 C# 慢那么多？ （质数基准）
Why is F# so much slower than C#? (prime number benchmark)
我认为 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# 代码在内部 for 循环中有一个 break 语句，但您的 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，它确实会短路：它将根据条件检查序列中的每个输入，如果条件曾经 returns false，它将停止并不再进行检查。 （因为 Seq 模块中的函数是 惰性的 并且不会做比获取输出所绝对需要的更多的工作）。这就像在您的 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 减一（含）的惰性序列。 （或者您可以将其视为从 2 开始并上升到 i，但不包括 i）。然后它检查该序列的 每个 项是否满足特定条件（即 Seq.forall 函数）。而且，作为 Seq.forall 的一个实现细节，因为它是惰性的并且只做它绝对必须做的工作，一旦它找到 false 结果它就会停止并且不再遍历输入序列. （因为一旦你找到一个反例，forall 函数就不再可能 return 为真，所以它一知道结果就停止了。）表达式是什么入住 Seq.forall？是 fun j -> i % j <> 0。所以 j 是内部循环变量， i 是外部变量（在 Seq.filter 部分分配的那个），逻辑与你的 C# 循环相同。
现在，记住我们在 Seq.filter 里面。因此，如果 Seq.forall return 为真，则 Seq.filter 将保留 i 的值。但是，如果 Seq.forall return 为 false，则 Seq.filter 将丢弃 i 的这个值，使其无法进入下一步。
最后，我们将这一行作为下一步（也是最后一步）：
|> Seq.iter (printfn "%i")
这与以下内容几乎完全相同：
for number in inputSoFar do
printfn "%i" number
如果您是 F# 的新手，(printfn "%i") 调用对您来说可能看起来很不寻常。这是 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# 程序速度较慢，以及如何编写遵循与 C# 相同的逻辑但具有等效于 break 语句的 F# 程序在里面。
我知道有一个已经被接受的答案，但只是想添加这个。
这些年来用了很多 C#，但没用多少 F#。以下将更等同于 C# 代码。
open System
open System.Diagnostics
let stopwatch = new Stopwatch()
stopwatch.Start()
let mutable loop = true
for i in 2 .. 100000 do
let mutable j = 2
while loop do
if i <> j && i % j = 0 then
loop <- false
else
j <- j + 1
if j >= i then
printfn "%i" i
loop <- false
loop <- true
stopwatch.Stop()
printfn "Elapsed time: %ims" stopwatch.ElapsedMilliseconds
并且在我对 LinqPad 的测试中，上述方法比 Aaron M. Eshbach 建议的解决方案更快。
它还具有惊人相似的 IL。
如果您想要一个完全等同于 C# 中 for 循环的迭代 F# 函数，您可以使用以下尾递归函数：
let rec isPrimeLoop i j limit =
if i > limit then ()
elif j > i then
stdout.WriteLine (string i)
isPrimeLoop (i + 1) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop (i + 1) 2 limit
else
isPrimeLoop i (j + 1) limit
如您所见，由于它调用自身的方式，不再需要 isPrime 标志。代替嵌套的 for 循环，按如下方式调用它：
let sw = System.Diagnostics.Stopwatch.StartNew ()
isPrimeLoop 2 2 100000
sw.Stop ()
printfn "Elapsed time: %ims" sw.ElapsedMilliseconds
PS：您可以通过只检查 2:
之后的奇数来显着缩短时间
let rec isPrimeLoop i j limit =
let incr x = if x = 2 then 3 else x + 2
if i > limit then ()
elif j > i then
stdout.WriteLine (string i)
isPrimeLoop (incr i) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop (incr i) 2 limit
else
isPrimeLoop i (incr j) limit
正如其他人提到的，代码没有做同样的事情，您需要使用技术来确保在找到素数后停止内部循环。
此外，您正在将值打印到标准输出。当您进行 CPU 性能测试时，通常不需要这样做，因为大量时间可能会 I/O 扭曲测试结果。
无论如何，即使有一个公认的答案，我还是决定稍微修改一下，看看将不同的建议解决方案与我自己的一些解决方案进行比较。
性能 运行 在 .NET 4.7.1 上处于 x64 模式。
我比较了不同的 F# 解决方案以及我自己的一些变体：
Running 'Original(F#)' with 100000 (10512)...
... it took 14533 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Original(C#)' with 100000 (10512)...
... it took 1343 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Aaron' with 100000 (10512)...
... it took 5027 ms with (3, 1, 0) cc and produces 9592 GOOD primes
Running 'SteveJ' with 100000 (10512)...
... it took 1640 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Dumetrulo1' with 100000 (10512)...
... it took 1908 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Dumetrulo2' with 100000 (10512)...
... it took 970 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Simple' with 100000 (10512)...
... it took 621 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'PushStream' with 100000 (10512)...
... it took 1627 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Unstalling' with 100000 (10512)...
... it took 551 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Vectors' with 100000 (10512)...
... it took 1076 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'VectorsUnstalling' with 100000 (10512)...
... it took 1072 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'BestAttempt' with 100000 (10512)...
... it took 4 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Original(F#) - OP 的原始 F# 代码更改为不使用标准输出Original(C#) - OP 的原始 C# 代码更改为不使用 stdoutAaron - 使用 Seq 的惯用方法。正如预期的那样 Seq 和性能通常不能很好地结合在一起。 SteveJ - @SteveJ 试图在 F#Dumetrulo1 - @dumetrulo 在尾递归中实现了算法Dumetrulo2 - @dumetrulo 通过步进 +2 而不是 +1 改进了算法（不需要检查偶数）。Simple - 我尝试使用类似于 Dumetrulo2 的尾递归方法。PushStream - 我尝试使用简单的推送流（Seq 是拉流）Unstalling - 我尝试卸载 CPU 以防使用的指令有延迟 Vectors - 我尝试使用 System.Numerics.Vectors 对每个操作进行多次除法（又名 SIMD）。不幸的是矢量库不支持 mod 所以我不得不模仿它。VectorsUnstalling - 我试图通过卸载 CPU.Vectors
BestAttempt - 与 Simple 类似，但在确定是否为质数时仅检查 sqrt n 以内的数字。
总结
- F# 循环没有
continue 也没有 break。 F# 中的尾递归是 IMO 实现需要 break. 循环的更好方法
- 在比较语言的性能时，应该比较最佳性能还是比较惯用解决方案的性能？我个人认为尽可能最好的性能是正确的方法，但我知道人们不同意我的看法（我为 F# 写了一个 mandelbrot version for benchmark the game，其性能与 C 相当，但它没有被接受，因为这种风格被视为非- F# 的惯用语）。
不幸的是，F# 中的 Seq 增加了大量开销。即使开销无关紧要，我也很难让自己使用它。 - 现代 CPUs 指令具有不同的吞吐量和延迟数。这意味着有时为了提高性能，需要在内部循环中处理多个独立样本，以允许乱序执行单元对程序重新排序以隐藏延迟。如果您的 CPU 有超线程并且您 运行 多线程超线程算法可以减少延迟 "automatically"。
- 缺少
mod 个向量阻止了使用 SIMD 获得优于非 SIMD 解决方案的任何性能的尝试。
- 如果我修改
Unstalling 尝试循环与 C# 代码相同的次数，则最终结果是 F# 中的 1100 ms 与 C# 中的 1343 ms 相比。所以 F# 可以做到 运行 与 C# 非常相似。如果再应用一些技巧，它只需要 4 ms 但对于 C# 也是一样的。无论如何，从几乎 15 sec 到 4 ms. 相当不错
希望有人感兴趣
完整源代码：
module Common =
open System
open System.Diagnostics
let now =
let sw = Stopwatch ()
sw.Start ()
fun () -> sw.ElapsedMilliseconds
let time i a =
let inline cc i = GC.CollectionCount i
let ii = i ()
GC.Collect (2, GCCollectionMode.Forced, true)
let bcc0, bcc1, bcc2 = cc 0, cc 1, cc 2
let b = now ()
let v = a ii
let e = now ()
let ecc0, ecc1, ecc2 = cc 0, cc 1, cc 2
v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2
let limit = 100000
// pi(x) ~= limit/(ln limit - 1)
// Using pi(x) ~= limit/(ln limit - 2) to over-estimate
let estimate = float limit / (log (float limit) - 1.0 - 1.0) |> round |> int
module Original =
let primes limit =
let ra = ResizeArray Common.estimate
let mutable isPrime = true
for i in 2 .. limit do
for j in 2 .. i do
if i <> j && i % j = 0 then
isPrime <- false
if isPrime then
ra.Add i
isPrime <- true
ra.ToArray ()
module SolutionAaron =
let primes limit =
{2 .. limit}
|> Seq.filter (fun i -> {2 .. i-1} |> Seq.forall (fun j -> i % j <> 0))
|> Seq.toArray
module SolutionSteveJ =
let primes limit =
let ra = ResizeArray Common.estimate
let mutable loop = true
for i in 2 .. limit do
let mutable j = 2
while loop do
if i <> j && i % j = 0 then
loop <- false
else
j <- j + 1
if j >= i then
ra.Add i
loop <- false
loop <- true
ra.ToArray ()
module SolutionDumetrulo1 =
let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =
if i > limit then ra.ToArray ()
elif j > i then
ra.Add i
isPrimeLoop ra (i + 1) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop ra (i + 1) 2 limit
else
isPrimeLoop ra i (j + 1) limit
let primes limit =
isPrimeLoop (ResizeArray Common.estimate) 2 2 limit
module SolutionDumetrulo2 =
let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =
let incr x = if x = 2 then 3 else x + 2
if i > limit then ra.ToArray ()
elif j > i then
ra.Add i
isPrimeLoop ra (incr i) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop ra (incr i) 2 limit
else
isPrimeLoop ra i (incr j) limit
let primes limit =
isPrimeLoop (ResizeArray Common.estimate) 2 2 limit
module SolutionSimple =
let rec isPrime i j k =
if i < k then
(j % i) <> 0 && isPrime (i + 2) j k
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime 3 i i then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
isPrimeLoop ra 3 limit
module SolutionPushStream =
type Receiver<'T> = 'T -> bool
type PushStream<'T> = Receiver<'T> -> bool
module Details =
module Loops =
let rec range e r i =
if i <= e then
if r i then
range e r (i + 1)
else
false
else
true
open Details
let range s e : PushStream<int> =
fun r -> Loops.range e r s
let filter p (t : PushStream<'T>) : PushStream<'T> =
fun r -> t (fun v -> if p v then r v else true)
let forall p (t : PushStream<'T>) : bool =
t p
let toArray (t : PushStream<'T>) : _ [] =
let ra = ResizeArray 16
t (fun v -> ra.Add v; true) |> ignore
ra.ToArray ()
let primes limit =
range 2 limit
|> filter (fun i -> range 2 (i - 1) |> forall (fun j -> i % j <> 0))
|> toArray
module SolutionUnstalling =
let rec isPrime i j k =
if i + 6 < k then
(j % i) <> 0 && (j % (i + 2)) <> 0 && (j % (i + 4)) <> 0 && (j % (i + 6)) <> 0 && isPrime (i + 8) j k
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime 3 i i then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
ra.Add 3
ra.Add 5
ra.Add 7
ra.Add 11
ra.Add 13
ra.Add 17
ra.Add 19
ra.Add 23
isPrimeLoop ra 29 limit
module SolutionVectors =
open System.Numerics
assert (Vector<int>.Count = 4)
type I4 = Vector<int>
let inline (%%) (i : I4) (j : I4) : I4 =
i - (j * (i / j))
let init : int [] = Array.zeroCreate 4
let i4 v0 v1 v2 v3 =
init.[0] <- v0
init.[1] <- v1
init.[2] <- v2
init.[3] <- v3
I4 init
let i4_ (v0 : int) =
I4 v0
let zero = I4.Zero
let one = I4.One
let two = one + one
let eight = two*two*two
let step = i4 3 5 7 9
let rec isPrime (i : I4) (j : I4) k l =
if l + 6 < k then
Vector.EqualsAny (j %% i, zero) |> not && isPrime (i + eight) j k (l + 8)
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime step (i4_ i) i 3 then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
ra.Add 3
ra.Add 5
ra.Add 7
ra.Add 11
ra.Add 13
ra.Add 17
ra.Add 19
ra.Add 23
isPrimeLoop ra 29 limit
module SolutionVectorsUnstalling =
open System.Numerics
assert (Vector<int>.Count = 4)
type I4 = Vector<int>
let init : int [] = Array.zeroCreate 4
let i4 v0 v1 v2 v3 =
init.[0] <- v0
init.[1] <- v1
init.[2] <- v2
init.[3] <- v3
I4 init
let i4_ (v0 : int) =
I4 v0
let zero = I4.Zero
let one = I4.One
let two = one + one
let eight = two*two*two
let sixteen = two*eight
let step = i4 3 5 7 9
let rec isPrime (i : I4) (j : I4) k l =
if l + 14 < k then
// i - (j * (i / j))
let i0 = i
let i8 = i + eight
let d0 = j / i0
let d8 = j / i8
let n0 = i0 * d0
let n8 = i8 * d8
let r0 = j - n0
let r8 = j - n8
Vector.EqualsAny (r0, zero) |> not && Vector.EqualsAny (r8, zero) |> not && isPrime (i + sixteen) j k (l + 16)
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime step (i4_ i) i 3 then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
ra.Add 3
ra.Add 5
ra.Add 7
ra.Add 11
ra.Add 13
ra.Add 17
ra.Add 19
ra.Add 23
isPrimeLoop ra 29 limit
module SolutionBestAttempt =
let rec isPrime i j k =
if i < k then
(j % i) <> 0 && isPrime (i + 2) j k
else
true
let inline isqrt i = (i |> float |> sqrt) + 1. |> int
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime 3 i (isqrt i) then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
isPrimeLoop ra 3 limit
[<EntryPoint>]
let main argv =
let testCases =
[|
"Original" , Original.primes
"Aaron" , SolutionAaron.primes
"SteveJ" , SolutionSteveJ.primes
"Dumetrulo1" , SolutionDumetrulo1.primes
"Dumetrulo2" , SolutionDumetrulo2.primes
"Simple" , SolutionSimple.primes
"PushStream" , SolutionPushStream.primes
"Unstalling" , SolutionUnstalling.primes
"Vectors" , SolutionVectors.primes
"VectorsUnstalling" , SolutionVectors.primes
"BestAttempt" , SolutionBestAttempt.primes
|]
do
// Warm-up
printfn "Warm up"
for _, a in testCases do
for i = 0 to 100 do
a 100 |> ignore
do
let init () = Common.limit
let expected = SolutionSimple.primes Common.limit
for testCase, a in testCases do
printfn "Running '%s' with %d (%d)..." testCase Common.limit Common.estimate
let actual, time, cc0, cc1, cc2 = Common.time init a
let result = if expected = actual then "GOOD" else "BAD"
printfn " ... it took %d ms with (%d, %d, %d) cc and produces %d %s primes" time cc0 cc1 cc2 actual.Length result
0
我认为 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# 代码在内部 for 循环中有一个 break 语句，但您的 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，它确实会短路：它将根据条件检查序列中的每个输入，如果条件曾经 returns false，它将停止并不再进行检查。 （因为 Seq 模块中的函数是 惰性的 并且不会做比获取输出所绝对需要的更多的工作）。这就像在您的 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 减一（含）的惰性序列。 （或者您可以将其视为从 2 开始并上升到 i，但不包括 i）。然后它检查该序列的 每个 项是否满足特定条件（即 Seq.forall 函数）。而且，作为 Seq.forall 的一个实现细节，因为它是惰性的并且只做它绝对必须做的工作，一旦它找到 false 结果它就会停止并且不再遍历输入序列. （因为一旦你找到一个反例，forall 函数就不再可能 return 为真，所以它一知道结果就停止了。）表达式是什么入住 Seq.forall？是 fun j -> i % j <> 0。所以 j 是内部循环变量， i 是外部变量（在 Seq.filter 部分分配的那个），逻辑与你的 C# 循环相同。
现在，记住我们在 Seq.filter 里面。因此，如果 Seq.forall return 为真，则 Seq.filter 将保留 i 的值。但是，如果 Seq.forall return 为 false，则 Seq.filter 将丢弃 i 的这个值，使其无法进入下一步。
最后，我们将这一行作为下一步（也是最后一步）：
|> Seq.iter (printfn "%i")
这与以下内容几乎完全相同：
for number in inputSoFar do
printfn "%i" number
如果您是 F# 的新手，(printfn "%i") 调用对您来说可能看起来很不寻常。这是 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# 程序速度较慢，以及如何编写遵循与 C# 相同的逻辑但具有等效于 break 语句的 F# 程序在里面。
我知道有一个已经被接受的答案，但只是想添加这个。
这些年来用了很多 C#，但没用多少 F#。以下将更等同于 C# 代码。
open System
open System.Diagnostics
let stopwatch = new Stopwatch()
stopwatch.Start()
let mutable loop = true
for i in 2 .. 100000 do
let mutable j = 2
while loop do
if i <> j && i % j = 0 then
loop <- false
else
j <- j + 1
if j >= i then
printfn "%i" i
loop <- false
loop <- true
stopwatch.Stop()
printfn "Elapsed time: %ims" stopwatch.ElapsedMilliseconds
并且在我对 LinqPad 的测试中，上述方法比 Aaron M. Eshbach 建议的解决方案更快。
它还具有惊人相似的 IL。
如果您想要一个完全等同于 C# 中 for 循环的迭代 F# 函数，您可以使用以下尾递归函数：
let rec isPrimeLoop i j limit =
if i > limit then ()
elif j > i then
stdout.WriteLine (string i)
isPrimeLoop (i + 1) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop (i + 1) 2 limit
else
isPrimeLoop i (j + 1) limit
如您所见，由于它调用自身的方式，不再需要 isPrime 标志。代替嵌套的 for 循环，按如下方式调用它：
let sw = System.Diagnostics.Stopwatch.StartNew ()
isPrimeLoop 2 2 100000
sw.Stop ()
printfn "Elapsed time: %ims" sw.ElapsedMilliseconds
PS：您可以通过只检查 2:
之后的奇数来显着缩短时间let rec isPrimeLoop i j limit =
let incr x = if x = 2 then 3 else x + 2
if i > limit then ()
elif j > i then
stdout.WriteLine (string i)
isPrimeLoop (incr i) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop (incr i) 2 limit
else
isPrimeLoop i (incr j) limit
正如其他人提到的，代码没有做同样的事情，您需要使用技术来确保在找到素数后停止内部循环。
此外，您正在将值打印到标准输出。当您进行 CPU 性能测试时，通常不需要这样做，因为大量时间可能会 I/O 扭曲测试结果。
无论如何，即使有一个公认的答案，我还是决定稍微修改一下，看看将不同的建议解决方案与我自己的一些解决方案进行比较。
性能 运行 在 .NET 4.7.1 上处于 x64 模式。
我比较了不同的 F# 解决方案以及我自己的一些变体：
Running 'Original(F#)' with 100000 (10512)...
... it took 14533 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Original(C#)' with 100000 (10512)...
... it took 1343 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Aaron' with 100000 (10512)...
... it took 5027 ms with (3, 1, 0) cc and produces 9592 GOOD primes
Running 'SteveJ' with 100000 (10512)...
... it took 1640 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Dumetrulo1' with 100000 (10512)...
... it took 1908 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Dumetrulo2' with 100000 (10512)...
... it took 970 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Simple' with 100000 (10512)...
... it took 621 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'PushStream' with 100000 (10512)...
... it took 1627 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Unstalling' with 100000 (10512)...
... it took 551 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'Vectors' with 100000 (10512)...
... it took 1076 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'VectorsUnstalling' with 100000 (10512)...
... it took 1072 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Running 'BestAttempt' with 100000 (10512)...
... it took 4 ms with (0, 0, 0) cc and produces 9592 GOOD primes
Original(F#)- OP 的原始 F# 代码更改为不使用标准输出Original(C#)- OP 的原始 C# 代码更改为不使用 stdoutAaron- 使用Seq的惯用方法。正如预期的那样Seq和性能通常不能很好地结合在一起。SteveJ- @SteveJ 试图在 F# 中模仿 C# 代码
Dumetrulo1- @dumetrulo 在尾递归中实现了算法Dumetrulo2- @dumetrulo 通过步进 +2 而不是 +1 改进了算法（不需要检查偶数）。Simple- 我尝试使用类似于Dumetrulo2的尾递归方法。PushStream- 我尝试使用简单的推送流（Seq是拉流）Unstalling- 我尝试卸载 CPU 以防使用的指令有延迟Vectors- 我尝试使用System.Numerics.Vectors对每个操作进行多次除法（又名 SIMD）。不幸的是矢量库不支持mod所以我不得不模仿它。VectorsUnstalling- 我试图通过卸载 CPU. 来改进 BestAttempt- 与Simple类似，但在确定是否为质数时仅检查sqrt n以内的数字。
Vectors
总结
- F# 循环没有
continue也没有break。 F# 中的尾递归是 IMO 实现需要break. 循环的更好方法
- 在比较语言的性能时，应该比较最佳性能还是比较惯用解决方案的性能？我个人认为尽可能最好的性能是正确的方法，但我知道人们不同意我的看法（我为 F# 写了一个 mandelbrot version for benchmark the game，其性能与 C 相当，但它没有被接受，因为这种风格被视为非- F# 的惯用语）。 不幸的是，F# 中的
Seq增加了大量开销。即使开销无关紧要，我也很难让自己使用它。- 现代 CPUs 指令具有不同的吞吐量和延迟数。这意味着有时为了提高性能，需要在内部循环中处理多个独立样本，以允许乱序执行单元对程序重新排序以隐藏延迟。如果您的 CPU 有超线程并且您 运行 多线程超线程算法可以减少延迟 "automatically"。
- 缺少
mod个向量阻止了使用 SIMD 获得优于非 SIMD 解决方案的任何性能的尝试。 - 如果我修改
Unstalling尝试循环与 C# 代码相同的次数，则最终结果是 F# 中的1100 ms与 C# 中的1343 ms相比。所以 F# 可以做到 运行 与 C# 非常相似。如果再应用一些技巧，它只需要4 ms但对于 C# 也是一样的。无论如何，从几乎15 sec到4 ms. 相当不错
希望有人感兴趣
完整源代码：
module Common =
open System
open System.Diagnostics
let now =
let sw = Stopwatch ()
sw.Start ()
fun () -> sw.ElapsedMilliseconds
let time i a =
let inline cc i = GC.CollectionCount i
let ii = i ()
GC.Collect (2, GCCollectionMode.Forced, true)
let bcc0, bcc1, bcc2 = cc 0, cc 1, cc 2
let b = now ()
let v = a ii
let e = now ()
let ecc0, ecc1, ecc2 = cc 0, cc 1, cc 2
v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2
let limit = 100000
// pi(x) ~= limit/(ln limit - 1)
// Using pi(x) ~= limit/(ln limit - 2) to over-estimate
let estimate = float limit / (log (float limit) - 1.0 - 1.0) |> round |> int
module Original =
let primes limit =
let ra = ResizeArray Common.estimate
let mutable isPrime = true
for i in 2 .. limit do
for j in 2 .. i do
if i <> j && i % j = 0 then
isPrime <- false
if isPrime then
ra.Add i
isPrime <- true
ra.ToArray ()
module SolutionAaron =
let primes limit =
{2 .. limit}
|> Seq.filter (fun i -> {2 .. i-1} |> Seq.forall (fun j -> i % j <> 0))
|> Seq.toArray
module SolutionSteveJ =
let primes limit =
let ra = ResizeArray Common.estimate
let mutable loop = true
for i in 2 .. limit do
let mutable j = 2
while loop do
if i <> j && i % j = 0 then
loop <- false
else
j <- j + 1
if j >= i then
ra.Add i
loop <- false
loop <- true
ra.ToArray ()
module SolutionDumetrulo1 =
let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =
if i > limit then ra.ToArray ()
elif j > i then
ra.Add i
isPrimeLoop ra (i + 1) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop ra (i + 1) 2 limit
else
isPrimeLoop ra i (j + 1) limit
let primes limit =
isPrimeLoop (ResizeArray Common.estimate) 2 2 limit
module SolutionDumetrulo2 =
let rec isPrimeLoop (ra : ResizeArray<_>) i j limit =
let incr x = if x = 2 then 3 else x + 2
if i > limit then ra.ToArray ()
elif j > i then
ra.Add i
isPrimeLoop ra (incr i) 2 limit
elif i <> j && i % j = 0 then
isPrimeLoop ra (incr i) 2 limit
else
isPrimeLoop ra i (incr j) limit
let primes limit =
isPrimeLoop (ResizeArray Common.estimate) 2 2 limit
module SolutionSimple =
let rec isPrime i j k =
if i < k then
(j % i) <> 0 && isPrime (i + 2) j k
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime 3 i i then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
isPrimeLoop ra 3 limit
module SolutionPushStream =
type Receiver<'T> = 'T -> bool
type PushStream<'T> = Receiver<'T> -> bool
module Details =
module Loops =
let rec range e r i =
if i <= e then
if r i then
range e r (i + 1)
else
false
else
true
open Details
let range s e : PushStream<int> =
fun r -> Loops.range e r s
let filter p (t : PushStream<'T>) : PushStream<'T> =
fun r -> t (fun v -> if p v then r v else true)
let forall p (t : PushStream<'T>) : bool =
t p
let toArray (t : PushStream<'T>) : _ [] =
let ra = ResizeArray 16
t (fun v -> ra.Add v; true) |> ignore
ra.ToArray ()
let primes limit =
range 2 limit
|> filter (fun i -> range 2 (i - 1) |> forall (fun j -> i % j <> 0))
|> toArray
module SolutionUnstalling =
let rec isPrime i j k =
if i + 6 < k then
(j % i) <> 0 && (j % (i + 2)) <> 0 && (j % (i + 4)) <> 0 && (j % (i + 6)) <> 0 && isPrime (i + 8) j k
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime 3 i i then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
ra.Add 3
ra.Add 5
ra.Add 7
ra.Add 11
ra.Add 13
ra.Add 17
ra.Add 19
ra.Add 23
isPrimeLoop ra 29 limit
module SolutionVectors =
open System.Numerics
assert (Vector<int>.Count = 4)
type I4 = Vector<int>
let inline (%%) (i : I4) (j : I4) : I4 =
i - (j * (i / j))
let init : int [] = Array.zeroCreate 4
let i4 v0 v1 v2 v3 =
init.[0] <- v0
init.[1] <- v1
init.[2] <- v2
init.[3] <- v3
I4 init
let i4_ (v0 : int) =
I4 v0
let zero = I4.Zero
let one = I4.One
let two = one + one
let eight = two*two*two
let step = i4 3 5 7 9
let rec isPrime (i : I4) (j : I4) k l =
if l + 6 < k then
Vector.EqualsAny (j %% i, zero) |> not && isPrime (i + eight) j k (l + 8)
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime step (i4_ i) i 3 then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
ra.Add 3
ra.Add 5
ra.Add 7
ra.Add 11
ra.Add 13
ra.Add 17
ra.Add 19
ra.Add 23
isPrimeLoop ra 29 limit
module SolutionVectorsUnstalling =
open System.Numerics
assert (Vector<int>.Count = 4)
type I4 = Vector<int>
let init : int [] = Array.zeroCreate 4
let i4 v0 v1 v2 v3 =
init.[0] <- v0
init.[1] <- v1
init.[2] <- v2
init.[3] <- v3
I4 init
let i4_ (v0 : int) =
I4 v0
let zero = I4.Zero
let one = I4.One
let two = one + one
let eight = two*two*two
let sixteen = two*eight
let step = i4 3 5 7 9
let rec isPrime (i : I4) (j : I4) k l =
if l + 14 < k then
// i - (j * (i / j))
let i0 = i
let i8 = i + eight
let d0 = j / i0
let d8 = j / i8
let n0 = i0 * d0
let n8 = i8 * d8
let r0 = j - n0
let r8 = j - n8
Vector.EqualsAny (r0, zero) |> not && Vector.EqualsAny (r8, zero) |> not && isPrime (i + sixteen) j k (l + 16)
else
true
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime step (i4_ i) i 3 then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
ra.Add 3
ra.Add 5
ra.Add 7
ra.Add 11
ra.Add 13
ra.Add 17
ra.Add 19
ra.Add 23
isPrimeLoop ra 29 limit
module SolutionBestAttempt =
let rec isPrime i j k =
if i < k then
(j % i) <> 0 && isPrime (i + 2) j k
else
true
let inline isqrt i = (i |> float |> sqrt) + 1. |> int
let rec isPrimeLoop (ra : ResizeArray<_>) i limit =
if i < limit then
if isPrime 3 i (isqrt i) then
ra.Add i
isPrimeLoop ra (i + 2) limit
else
ra.ToArray ()
let primes limit =
let ra = ResizeArray Common.estimate
ra.Add 2
isPrimeLoop ra 3 limit
[<EntryPoint>]
let main argv =
let testCases =
[|
"Original" , Original.primes
"Aaron" , SolutionAaron.primes
"SteveJ" , SolutionSteveJ.primes
"Dumetrulo1" , SolutionDumetrulo1.primes
"Dumetrulo2" , SolutionDumetrulo2.primes
"Simple" , SolutionSimple.primes
"PushStream" , SolutionPushStream.primes
"Unstalling" , SolutionUnstalling.primes
"Vectors" , SolutionVectors.primes
"VectorsUnstalling" , SolutionVectors.primes
"BestAttempt" , SolutionBestAttempt.primes
|]
do
// Warm-up
printfn "Warm up"
for _, a in testCases do
for i = 0 to 100 do
a 100 |> ignore
do
let init () = Common.limit
let expected = SolutionSimple.primes Common.limit
for testCase, a in testCases do
printfn "Running '%s' with %d (%d)..." testCase Common.limit Common.estimate
let actual, time, cc0, cc1, cc2 = Common.time init a
let result = if expected = actual then "GOOD" else "BAD"
printfn " ... it took %d ms with (%d, %d, %d) cc and produces %d %s primes" time cc0 cc1 cc2 actual.Length result
0