c++ - F# 性能 : What is making this code so slow?

Question

这个 F# 代码试图解决 Project Euler problem #58 :

let inc = function
| n -> n + 1
let is_prime = function
| 2 -> true
| n when n < 2 || n%2=0-> false 
| n -> 
       [3..2..(int (sqrt (float n)))] 
       |> List.tryFind (fun i -> n%i=0)
       |> Option.isNone
let spir = Seq.initInfinite (fun i -> 
    let n = i%4
    let a = 2 * (i/4 + 1)
    (a*n) + a + (a-1)*(a-1))
let rec accum se p n = 
   match se with
   | x when p*10 < n && p <> 0 -> 2*(n/4) + 1
   | x when is_prime (Seq.head x) -> accum (Seq.tail x) (inc p) (inc n)
   | x -> accum (Seq.tail x) p (inc n)
   | _ -> 0
printfn "%d" (accum spir 0 1)

我不知道这个程序的运行时间，因为我拒绝等待它完成。相反，我用 C++ 命令式地编写了这段代码:

#include "stdafx.h"
#include "math.h"
#include <iostream>

using namespace std;

int is_prime(int n)
{
    if (n % 2 == 0) return 0;
    for (int i = 3; i <= sqrt(n); i+=2)
    {
        if (n%i == 0)
        {
            return 0;
        }
    }
    return 1;
}

int spir(int i)
{
    int n = i % 4;
    int a = 2 * (i / 4 + 1);
    return (a*n) + a + ((a - 1)*(a - 1));
}

int main()
{
    int n = 1, p = 0, i = 0;
    cout << "start" << endl;
    while (p*10 >= n || p == 0)
    {
        p += is_prime(spir(i));
        n++; i++;
    }
    cout << 2*(i/4) + 1;

    return 0;
}

上面的代码运行不到2秒就得到了正确答案。

是什么让 F# 代码运行如此缓慢？即使在使用了 an old Stackoverflow post 中提到的一些分析工具之后，我仍然无法弄清楚正在发生什么昂贵的操作。

编辑#1

通过 rmunn 的帖子，我能够想出一个不同的实现，它可以在不到 30 秒的时间内得到答案:

let inc = function
| n -> n + 1
let is_prime = function
| 2 -> true
| n when n < 2 || n%2=0-> false 
| n -> 
       [3..2..(int (sqrt (float n)))] 
       |> List.tryFind (fun i -> n%i=0)
       |> Option.isNone
let spir2 = 
    List.unfold (fun state -> 
        let p = fst state
        let i = snd state
        let n = i%4
        let a = 2 * (i/4 + 1)
        let diag = (a*n) + a + (a-1)*(a-1)
        if p*10 < (i+1) && p <> 0 then 
            printfn "%d" (2*((i+1)/4) + 1)
            None
        elif is_prime diag then
            Some(diag, (inc p, inc i))
        else Some(diag, (p, inc i))) (0, 0)

编辑#2

在 FuleSnabel 的信息丰富的帖子中，他的 is_prime 函数使上述代码的运行时间不到十分之一秒，比 C++ 代码更快:

let inc = function
| n -> n + 1
let is_prime = function
  | 1                 -> false
  | 2                 -> true
  | v when v % 2 = 0  -> false
  | v ->
    let stop = v |> float |> sqrt |> int
    let rec loop vv =
      if vv <= stop then
        if (v % vv) <> 0 then
          loop (vv + 2)
        else
          false
      else
        true
    loop 3
let spir2 = 
    List.unfold (fun state -> 
        let p = fst state
        let i = snd state
        let n = i%4
        let a = 2 * (i/4 + 1)
        let diag = (a*n) + a + (a-1)*(a-1)
        if p*10 < (i+1) && p <> 0 then 
            printfn "%d" (2*((i+1)/4) + 1)
            None
        elif i <> 3 && is_prime diag then
            Some(diag, (inc p, inc i))
        else Some(diag, (p, inc i))) (0, 0)

Answer 1

核心 F# 库中没有 Seq.tail 函数(更新:有，请参阅评论)，所以我假设您使用的是 Seq.tail 函数来自 FSharpx.Collections .如果您使用的是 Seq.tail 的不同实现，它可能是相似的——几乎可以肯定它是您的问题的原因，因为它不像您认为的那样 O(1)。获取 List 的尾部是 O(1)，因为 List 是如何实现的(作为一系列 cons 单元格)。但是得到一个 Seq 的尾部最终会从原始枚举中创建一个全新的 Seq，从中丢弃一个项目，并返回它的其余项目。当您第二次通过 accum 循环时，您在“跳过 1 然后返回”seq 上调用 Seq.tail。所以现在你有一个 Seq，我将其称为 S2，它向 S1 请求一个 IEnumerable，跳过 S1 的第一项，并返回它的其余部分。 S1，当被问到它的第一个项目时，向 S0(原始 Seq)询问一个可枚举的，跳过它的第一个项目，然后返回它的其余部分。所以 S2 要跳过两个项目，它必须创建两个序列。现在，在您下一次运行时，当您请求 S2 的 Seq.tail 时，您创建了 S3，它向 S2 请求一个 IEnumerable，它向 S1 请求一个 IEnumerable，它向 S0 请求一个 IEnumerable...等等。这实际上是 O(N^2)，当您认为您正在编写 O(N) 操作时。

恐怕我现在没有时间为您找出解决方案；使用 List.tail 无济于事，因为您需要无限序列。但也许仅仅了解 Seq.tail 陷阱就足以让你开始，所以即使它不完整，我现在也会发布这个答案。

如果您需要更多帮助，请在此答案上发表评论，我会在有时间时回复它 - 但这可能不会持续几天，因此希望其他人也能回答您的问题。