哈斯克尔空间溢出 [英] Haskell Space Overflow

问题描述

  import Data.List 
导入数据.Ord 
导入限定的Data.MemoCombinators作为备注
 
 collat​​zLength :: Int  - > Int 
 collat​​zLength = Memo.arrayRange（1，1000000）collat​​zLength'
 where 
 collat​​zLength'1 = 1 
 collat​​zLength'n |奇数n = 1 + collat​​zLength（3 * n + 1）
 |即使n = 1 + collat​​zLength（n``` 2）
 
 main = print $ maximumBy（比较fst）$ [（collat​​zLength n，n）| n < -  [1..1000000]] 
  

我从GHC获得以下内容

 堆栈空间溢出：当前大小8388608字节。 
使用'+ RTS -Ksize -RTS'来增加它。 
  

我认为这是我听说过的空间溢出之一。 （我对Haskell很新颖。）我该如何解决它？我是否必须重写collat​​zLength为尾递归？

解决方案

作为代码的作者，我现在有点尴尬因为它没有一个，而是两个可能的堆栈溢出错误。

1. 它使用诠释。在32位系统上，这会溢出，因为Collat​​z序列可能比起始号码高出很多。这个溢出会导致无限递归，因为函数会在负值和正值之间来回跳动。

   
   
   

   如果数字在一百万之间，最差的起点是704511，在返回到1之前高达56,991,483,520。这超出了32位范围。

使用 maximumBy 。这个函数并不严格，所以在长列表上使用时会导致堆栈溢出。一百万个元素足以满足默认堆栈大小的情况。不过，由于GHC进行严格性分析，它仍然可以在启用优化的情况下工作。




解决方案是使用严格版本。由于在标准库中没有可用的，所以我们可以自己使用严格的left fold。

这是一个更新的版本这应该（希望）是堆栈无溢出，即使没有优化。

  import Data.List 
导入数据。 Ord 
导入限定的Data.MemoCombinators作为备注
 
 collat​​zLength :: Integer  - > Integer 
 collat​​zLength = Memo.arrayRange（1,1000000）collat​​zLength'
 where 
 collat​​zLength'1 = 1 
 collat​​zLength'n |奇数n = 1 + collat​​zLength（3 * n + 1）
 |即使n = 1 + collat​​zLength（n```2）
 
 main = print $ foldl1'max $ [（collat​​zLength n，n）| n < -  [1..1000000]] 
  

I've compiled this program and am trying to run it.

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Int -> Int
collatzLength = Memo.arrayRange (1, 1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ maximumBy (comparing fst) $ [(collatzLength n, n) | n <- [1..1000000]]

I'm getting the following from GHC

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

I assume this is one of the "space overflow" things I've been hearing about. (I'm pretty new to Haskell.) How do I fix it? Do I have to rewrite collatzLength to be tail recursive?

解决方案

As the author of the code in question, I am now slightly embarrassed because it has not one but two possible stack overflow bugs.

1. It uses Int. On a 32-bit system this will overflow, as the Collatz sequence can go quite a bit higher than the starting number. This overflow can cause infinite recursion as the function jumps back and forth between negative and positive values.

   In the case of numbers between one and a million, the worst starting point is 704511, which goes as high as 56,991,483,520 before coming back down towards 1. This is well outside the 32-bit range.

2. It uses maximumBy. This function is not strict, so it will cause a stack overflow when used on long lists. One million elements is more than enough for this to happen with the default stack size. It still works with optimizations enabled, though, due to the strictness analysis performed by GHC.

   The solution is to use a strict version. Since none is available in the standard libraries, we can use the strict left fold ourselves.

Here is an updated version which should (hopefully) be stack overflow-free, even without optimizations.

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]

这篇关于哈斯克尔空间溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！