我正在 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操作数量？
这不仅仅是记忆。
\n逐步了解对于相当小的数字（例如 29），这是如何工作的。
\nisPrime2a必须将 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 处停止（primes3a记住 4 不在 中）以确认 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，当您所做的只是算术运算时，类似的事情可能很重要（至少在我们得到巨大的数字之前）。
然而，当我们多次运行它们时，我们会看到不同的行为：
\n\xce\xbb isPrime2a 10000000019\nTrue\nit :: Bool\n(0.07 secs, 50,474,736 bytes)\n*Main\n\xce\xbb isPrime2a 10000000019\nTrue\nit :: Bool\n(0.07 secs, 50,474,736 bytes)\n*Main\n\xce\xbb isPrime2a 10000000019\nTrue\nit :: Bool\n(0.06 secs, 50,474,736 bytes)\n*Main\n\xce\xbb isPrime2a 10000000019\nTrue\nit :: Bool\n(0.07 secs, 50,474,736 bytes)\n请注意，重复执行需要相同的时间（和内存）。
\n\xce\xbb isPrime3a 10000000019\nTrue\nit :: Bool\n(0.68 secs, 475,082,944 bytes)\n*Main\n\xce\xbb isPrime3a 10000000019\nTrue\nit :: Bool\n(0.01 secs, 4,198,032 bytes)\n*Main\n\xce\xbb isPrime3a 10000000019\nTrue\nit :: Bool\n(0.01 secs, 4,198,032 bytes)\n*Main\n\xce\xbb isPrime3a 10000000019\nTrue\nit :: Bool\n(0.02 secs, 4,198,032 bytes)\nisPrime3aisPrime2a比第一次执行需要更多的时间和内存。后续的速度更快并且分配更少；该primes3a列表已经构建完毕，因此尽管它占用了大量内存，但不必为任何后续isPrime3a查询构建它（不需要更多素数）。
另外，您的实现中存在错误。
\n\xce\xbb take 20 primes3a\n[2,3,4,5,6,7,8,10,11,13,14,17,19,22,23,26,29,31,34,37]\nit :: [Integer]\n因为您检查not (divisibleByAny (tail primes3a))，所以您永远不会检查是否能被 的头primes3a（即 2）整除。因此，所有偶数都被报告为素数。解决这个问题：
\xce\xbb isPrime3a' 10000000019\nTrue\nit :: Bool\n(0.33 secs, 230,822,560 bytes)\n*Main\n\xce\xbb isPrime3a' 10000000019\nTrue\nit :: Bool\n(0.01 secs, 2,760,760 bytes)\n*Main\n\xce\xbb isPrime3a' 10000000019\nTrue\nit :: Bool\n(0.01 secs, 2,760,760 bytes)\n*Main\n\xce\xbb isPrime3a' 10000000019\nTrue\nit :: Bool\n(0.01 secs, 2,760,760 bytes)\n其实并没有改变结论。还是比慢很多isPrimes2第一次执行慢得多，而后续运行则快得多。
长话短说：这两种行为都很有用。如果您需要在实际程序中测试素数并且必须在这两种实现之间进行选择，那么primes2a如果您只需要测试一个（或少数）数字，您可能会选择。primes3a如果您要测试大量数字，并且您可以一直在内存中保留一个大列表（或者您正在测试足够小的数字，因此列表并不大），那么看起来不错。从这些数字来看，两者并不完全优于另一方。
当然，正如 Louis Wasserman 在评论中指出的那样，不应在 GHCi 中进行严格的性能测量（即，有助于预测程序的性能，因为它们将用于实际目的）。如何正确地做到这一点是一个完全不同的话题，但你错过的最大的事情是代码没有优化，GHC 的优化器可以对代码的速度和执行产生巨大的影响，但它也非常非 -其加速速度是一致的。您很可能拥有一个算法的两个版本，当您比较未优化的构建时，一个版本比另一个版本快 10 倍以上，而当您比较优化的构建时，情况正好相反。如果您关心性能，那么您几乎总是会通过优化来运行它，因此这通常是您想要测量的状态。
\n