为什么我理论上更高效的 prime 测试仪速度更慢？
Why is my theoretically more efficient prime tester slower?
我正在 Haskell 中试验不同的素数测试仪。该算法通过尝试将整数 n 除以从 2 到 sqrt(n) 的每个整数 i 来检查它是否为素数:
isPrime2a n =
helper 2
where
helper i
| (i * i) > n = True
| mod n i == 0 = False
| otherwise = helper (i+1)
我相信这个实现只测试素数：
primes3a = 2 : 3 : filter isPrime3a [4..]
isPrime3a n =
not (divisibleByAny (tail primes3a))
where
divisibleByAny (i : rest)
| (i * i) > n = False
| mod n i == 0 = True
| otherwise = divisibleByAny rest
此记录表明（与我的预期相反）第一个函数更快：
ghci> isPrime2a 10000000019
True
(0.14 secs, 50,455,088 bytes)
ghci> isPrime3a 10000000019
True
(1.27 secs, 475,058,704 bytes)
怎么会？我对算法的分析是否不正确，或者构建列表的开销是否超过了减少的 mod 操作数量？
不仅仅是记忆。
逐步了解这对于相当小的数字（如 29）的工作原理。
isPrime2a 必须将 29 除以 2，然后除以 3，然后除以 4，再除以 5，然后它停在 6（因为 6*6 = 36，即 > 29）并报告 True.
isPrime3a 必须将 29 除以 2，然后除以 3，然后 primes3a 的下一个元素。要算出那是什么 filter isPrime3a [4..] 必须用 4 除以 2 以确认下一个元素不是 4。然后 filter isPrime3a 必须用 5 除以 2，然后停在 3 以确认 5 是primes3a的下一个元素。
那么isPrime3a可以将29除以5，然后我们回到需要primes3a的下一个元素，这意味着运行宁filter isPrime3a一些更多的。我们达到了 6，所以我们用 6 除以 2 来找出它 不是 primes3a 的下一个元素。然后 filter isPrime3a 考虑 7，这意味着将它除以 2，然后除以 3，然后停在 5（4 不在 primes3a 中，记住）以确认 7 是 在 primes3a.
终于isPrime3a可以停了，因为7*7 = 49，也就是>29。
那是 步！请注意，isPrime3a 只需将 29 除以 2、3 和 5，而 isPrime2a 只需将 29 除以 2、3、4、5 和 6； isPrime3a 必须跳过 4 和 6，节省 2 个分区。但要做到这一点，它必须将 4 除以 2、5 除以 2 和 3、6 除以 2，以及 7 除以 2 和 3；为了拯救这 2 个师，我们又做了 6 个师！还有一些管理开销，如 not 和 filter，在 primes2a 中根本不存在，当你所做的只是算术运算时，这样的东西可能很重要（至少在我们达到巨大数量之前是这样）。
但是，当我们 运行 每个人不止一次时，我们会看到不同的行为：
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.06 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
请注意，重复执行需要相同的时间（和内存）。
λ isPrime3a 10000000019
True
it :: Bool
(0.68 secs, 475,082,944 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.01 secs, 4,198,032 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.01 secs, 4,198,032 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.02 secs, 4,198,032 bytes)
isPrime3a 在 第一次 执行时比 isPrime2a 花费更多的时间和内存。随后的速度更快，分配更少； primes3a 列表已经构建，因此尽管它占用了大量内存，但不必为任何后续 isPrime3a 查询构建它（不需要更多素数）。
此外，您的实现中存在错误。
λ take 20 primes3a
[2,3,4,5,6,7,8,10,11,13,14,17,19,22,23,26,29,31,34,37]
it :: [Integer]
因为您检查 not (divisibleByAny (tail primes3a))，所以您永远不会检查 primes3a 的头部是否可整除，即 2。因此所有偶数都被报告为质数。修复：
λ isPrime3a' 10000000019
True
it :: Bool
(0.33 secs, 230,822,560 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
确实没有改变结论。它在第一次执行时仍然比 isPrimes2 慢得多，在随后的 运行 中快得多。
长话短说：这两种 行为都很有用。如果您需要在真实程序中测试素数并且必须在这两种实现之间进行选择，那么如果您只需要测试一个（或少数）数字，您可能会选择 primes2a。 primes3a 如果你要测试很多数字，看起来不错，而且你可以一直在内存中保留一个大列表（或者你测试的数字足够小，列表并不大）。在这些数字上，两者都不完全优于另一个。
当然，正如 Louis Wasserman 在评论中指出的那样，不应在 GHCi 中进行认真的性能测量（即有助于您预测程序的性能，因为它们 运行 出于实际目的） .如何正确地做到这一点是另一个话题，但你最想念的是代码没有优化，GHC 的优化器可以对速度和执行产生 巨大 差异的代码，但它也非常 non-uniform 加快了速度。很可能您可以拥有一个算法的两个版本，当您比较未优化的构建时，一个比另一个快 10 倍以上，而当您比较优化的构建时，情况正好相反。如果您关心性能，那么您几乎总是会 运行 对其进行优化，因此这通常是您要衡量的状态。
我正在 Haskell 中试验不同的素数测试仪。该算法通过尝试将整数 n 除以从 2 到 sqrt(n) 的每个整数 i 来检查它是否为素数:
isPrime2a n =
helper 2
where
helper i
| (i * i) > n = True
| mod n i == 0 = False
| otherwise = helper (i+1)
我相信这个实现只测试素数：
primes3a = 2 : 3 : filter isPrime3a [4..]
isPrime3a n =
not (divisibleByAny (tail primes3a))
where
divisibleByAny (i : rest)
| (i * i) > n = False
| mod n i == 0 = True
| otherwise = divisibleByAny rest
此记录表明（与我的预期相反）第一个函数更快：
ghci> isPrime2a 10000000019
True
(0.14 secs, 50,455,088 bytes)
ghci> isPrime3a 10000000019
True
(1.27 secs, 475,058,704 bytes)
怎么会？我对算法的分析是否不正确，或者构建列表的开销是否超过了减少的 mod 操作数量？
不仅仅是记忆。
逐步了解这对于相当小的数字（如 29）的工作原理。
isPrime2a 必须将 29 除以 2，然后除以 3，然后除以 4，再除以 5，然后它停在 6（因为 6*6 = 36，即 > 29）并报告 True.
isPrime3a 必须将 29 除以 2，然后除以 3，然后 primes3a 的下一个元素。要算出那是什么 filter isPrime3a [4..] 必须用 4 除以 2 以确认下一个元素不是 4。然后 filter isPrime3a 必须用 5 除以 2，然后停在 3 以确认 5 是primes3a的下一个元素。
那么isPrime3a可以将29除以5，然后我们回到需要primes3a的下一个元素，这意味着运行宁filter isPrime3a一些更多的。我们达到了 6，所以我们用 6 除以 2 来找出它 不是 primes3a 的下一个元素。然后 filter isPrime3a 考虑 7，这意味着将它除以 2，然后除以 3，然后停在 5（4 不在 primes3a 中，记住）以确认 7 是 在 primes3a.
终于isPrime3a可以停了，因为7*7 = 49，也就是>29。
那是 步！请注意，isPrime3a 只需将 29 除以 2、3 和 5，而 isPrime2a 只需将 29 除以 2、3、4、5 和 6； isPrime3a 必须跳过 4 和 6，节省 2 个分区。但要做到这一点，它必须将 4 除以 2、5 除以 2 和 3、6 除以 2，以及 7 除以 2 和 3；为了拯救这 2 个师，我们又做了 6 个师！还有一些管理开销，如 not 和 filter，在 primes2a 中根本不存在，当你所做的只是算术运算时，这样的东西可能很重要（至少在我们达到巨大数量之前是这样）。
但是，当我们 运行 每个人不止一次时，我们会看到不同的行为：
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.06 secs, 50,474,736 bytes)
*Main
λ isPrime2a 10000000019
True
it :: Bool
(0.07 secs, 50,474,736 bytes)
请注意，重复执行需要相同的时间（和内存）。
λ isPrime3a 10000000019
True
it :: Bool
(0.68 secs, 475,082,944 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.01 secs, 4,198,032 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.01 secs, 4,198,032 bytes)
*Main
λ isPrime3a 10000000019
True
it :: Bool
(0.02 secs, 4,198,032 bytes)
isPrime3a 在 第一次 执行时比 isPrime2a 花费更多的时间和内存。随后的速度更快，分配更少； primes3a 列表已经构建，因此尽管它占用了大量内存，但不必为任何后续 isPrime3a 查询构建它（不需要更多素数）。
此外，您的实现中存在错误。
λ take 20 primes3a
[2,3,4,5,6,7,8,10,11,13,14,17,19,22,23,26,29,31,34,37]
it :: [Integer]
因为您检查 not (divisibleByAny (tail primes3a))，所以您永远不会检查 primes3a 的头部是否可整除，即 2。因此所有偶数都被报告为质数。修复：
λ isPrime3a' 10000000019
True
it :: Bool
(0.33 secs, 230,822,560 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
*Main
λ isPrime3a' 10000000019
True
it :: Bool
(0.01 secs, 2,760,760 bytes)
确实没有改变结论。它在第一次执行时仍然比 isPrimes2 慢得多，在随后的 运行 中快得多。
长话短说：这两种 行为都很有用。如果您需要在真实程序中测试素数并且必须在这两种实现之间进行选择，那么如果您只需要测试一个（或少数）数字，您可能会选择 primes2a。 primes3a 如果你要测试很多数字，看起来不错，而且你可以一直在内存中保留一个大列表（或者你测试的数字足够小，列表并不大）。在这些数字上，两者都不完全优于另一个。
当然，正如 Louis Wasserman 在评论中指出的那样，不应在 GHCi 中进行认真的性能测量（即有助于您预测程序的性能，因为它们 运行 出于实际目的） .如何正确地做到这一点是另一个话题，但你最想念的是代码没有优化，GHC 的优化器可以对速度和执行产生 巨大 差异的代码，但它也非常 non-uniform 加快了速度。很可能您可以拥有一个算法的两个版本，当您比较未优化的构建时，一个比另一个快 10 倍以上，而当您比较优化的构建时，情况正好相反。如果您关心性能，那么您几乎总是会 运行 对其进行优化，因此这通常是您要衡量的状态。