haskell - 不断出现堆栈溢出

Question

我的解决方案 Project Euler #7 反复出现堆栈溢出问题我不知道为什么。 这是我的代码:

import System.Environment

checkPrime :: Int -> Bool
checkPrime n = not $ testList n [2..n `div` 2]

--testList :: Int -> [Int] -> Bool
testList _ [] = False
testList n xs 
    | (n `rem` (head xs) == 0) = True
    | otherwise  = testList n (tail xs)

primesTill n = sum [1 | x <- [2..n], checkPrime x]
nthPrime n = nthPrime' n 2
nthPrime' n x
    | (primesTill x == n) = x
    | otherwise = nthPrime' n x+1

main = print (nthPrime 10001)

Answer 1

解决堆栈溢出问题

正如 @bheklilr 在他的评论中提到的，堆栈溢出是由 nthPrime' 函数的 other 分支中错误的求值顺序引起的:

nthPrime' n x+1

将被解释为

(nthPrime' n x)+1

由于此表达式是递归调用的，因此您对 nthPrime' n 2 的调用将扩展为

(nthPrime' n 2)+1+1+1+1+1+1+1+1 ...

但是第二个参数永远不会增加，并且您的程序会收集大量未评估的重击。仅当第一个参数减少为 Int 时才会进行评估，但您的函数处于无限递归中，因此这种情况永远不会发生。所有加号都存储在堆栈中，如果没有剩余空间，您将收到堆栈溢出错误。

要解决这个问题，您需要在 x+1 周围添加括号，这样您的递归调用将如下所示

 nthPrime' n (x+1)

现在参数在传递给递归调用之前会递增。

这应该可以解决您的 stackoverflow 问题，您可以尝试使用较小的数字，例如101，您将得到所需的结果。

运行时优化

如果您使用原始值 10001 测试您的程序，您可能会发现它仍然无法在合理的时间内完成。

我不会详细介绍解决这个问题的奇特算法，如果你对它们感兴趣，你可以很容易地在网上找到它们。 相反，我将向您展示代码中的问题所在，并向您展示一个简单的解决方案。

瓶颈是您的 nthPrime 函数:

 primesTill n = sum [1 | x <- [2..n], checkPrime x]
 nthPrime n = nthPrime' n 2
 nthPrime' n x
     | (primesTill x == n) = x
     | otherwise = nthPrime' n (x+1)

此函数检查 2 和 x 之间的素数数量是否等于 n。这个想法是正确的，但它会导致运行时间呈指数级增长。问题是您每次迭代都要重新计算 primesTill x 。要计算小于 x 的素数，您需要计算所有素数，然后将它们相加。在 x+1 的下一步中，您会忘记关于 2 和 x 之间的数字的所有知识，并再次测试它们是否符合质数仅作为测试 x+1 是否为质数的最后一步。然后您重复此操作 - 忘记所有事情并再次测试所有数字 - 直到完成。

如果计算机能够记住它已经找到的素数，那不是很好吗？

有很多可能性可以做到这一点，我将使用一个简单的无限列表，如果您对其他方法感兴趣，您可以搜索术语内存或动态编程 .

我们从您在 primesTill 中使用的列表理解开始:

 [1 | x <- [2..n], checkPrime x]

这会计算 2 和 n 之间的所有素数，但会立即忘记素数并将其替换为 1，因此第一步将保留实际数字。

 [x | x <- [2..n], checkPrime x]

这为我们提供了 2 和 n 之间所有素数的列表。如果我们有足够大的素数列表，我们可以使用索引函数 !! 来获取第 10001 个素数。所以我们需要将n设置为一个非常非常大的数字，以确保过滤后的列表足够长？

惰性求值来拯救!

haskell 中的惰性求值允许我们构建一个无限列表，仅根据需要求值。如果我们不为列表生成器提供上限，它将为我们构建这样一个无限列表。

 [x | x <- [2..], checkPrime x]

现在我们有一个包含所有素数的无限列表。 我们可以将它绑定(bind)到名称，例如primes 并用它来定义 nthPrime

primes = [x | x <- [2..], checkPrime x]
nthPrime n = primes !! n

现在您可以使用ghc -O2编译它，运行它，结果将立即交付给您。