.NET 优化埃拉托色尼 F# 筛法

Question

我正在摆弄 F# 并使用 FSI REPL 我注意到我的初学者天真的埃拉托色尼筛法实现的两个略有不同的实现之间存在巨大的效率差异。第一个带有额外的 if:

let rec sieve max current pList =
    match current with
    | 2 -> sieve max (current + 1) (current::pList)
    | 3 -> sieve max (current + 2) (current::pList)
    | n when n < max ->
        if (n % 5 = 0) || (n % 3 = 0) then
            sieve max (current + 2) (current::pList)
        else if (pList |> (List.map (fun n -> current % n = 0)) |> List.contains true) then
            sieve max (current + 2) (pList)
        else
            sieve max (current + 2) (current::pList)
    | n when n >= max
        -> pList
    | _
        ->  printfn "Error: list length: %A, current: %A" (List.length pList) current
            [-1]

第二个没有:

let rec sieve max current pList =
    match current with
    | 2 -> sieve max (current + 1) (current::pList)
    | 3 -> sieve max (current + 2) (current::pList)
    | n when n < max ->
        if (pList |> (List.map (fun n -> current % n = 0)) |> List.contains true) then
            sieve max (current + 2) (pList)
        else
            sieve max (current + 2) (current::pList)
    | n when n >= max
        -> pList
    | _
        ->  printfn "Error: list length: %A, current: %A" (List.length pList) current
            [-1]

带有额外 if 分支的分支实际上较慢，尽管它看起来应该更快。 然后，我使用以下命令对 REPL 中的两个实现进行计时:

#time 筛 200000 2 [] #time

并且在我的机器上看到，带有额外的 if 语句的实现每次运行大约需要 2 分钟，而没有的则需要大约 1 分钟。 这怎么可能？通过添加处理 3 或 5 的倍数的 if 语句，它实际上比仅映射整个列表然后查找素数列表中是否有数字的约数要慢。 如何？ F# 是否针对处理列表进行了优化？

Answer 1

第一个筛子中的额外 if 可能是为了快捷方式，实际上稍微改变了行为。它没有删除除以 3 和 5 的所有内容，而是实际添加了它。比较一下输出就很容易看出:

1st sieve: [19; 17; 15; 13; 11; 9; 7; 5; 3; 2]
2st sieve: [19; 17; 13; 11; 7; 5; 3; 2]

我假设你想要的是这样的:

if (n % 5 = 0) || (n % 3 = 0) then
    sieve max (current + 2) (pList)

但是，在这种情况下，它不会包括 5(很明显)。所以正确的代码是

if (n <> 5 && n % 5 = 0) || (n <> 3 && n % 3 = 0) then
    sieve max (current + 2) (pList)

检查上面代码的性能 - 应该没问题。