我有一个键值对列表,我想计算每个键出现的次数以及它出现的值,但是当我尝试时,我得到了堆栈溢出。这是我正在运行的代码的简化版本:
import Array
add (n, vals) val = n `seq` vals `seq` (n+1,val:vals)
histo = accumArray add (0,[]) (0,9) [(0, n) | n <- [0..5000000]]
main = print histo
当我用 'ghc -O' 编译并运行它时,我得到“堆栈空间溢出:当前大小 8388608 字节”。
我想我知道发生了什么:accumArray 具有与 foldl 相同的属性,因此我需要一个严格版本的 accumArray。不幸的是,我发现的唯一一个在 Data.Array.Unboxed 中,它不适用于列表数组。
文档说,当累加函数是严格的,那么 accumArray 也应该是,但我不能让它工作,讨论 here声称文档错误(至少对于 GHC)。
除了 Data.Array.Unboxed 中的 accumArray 之外,还有严格版本的 accumArray 吗?还是有更好的方法来做我想做的事?
最佳答案
好吧,严格并不一定意味着不创建 thunk,它只是意味着如果一个参数是底部,结果也是底部。但是accumArray
不是那么严格,如果它们发生,它只会将底部写入数组。它实际上不能做任何其他事情,因为它必须允许可以从中间底部生成定义值的非严格函数。并且严格度分析器无法重写它,因此如果它是严格的,则每次写入时都会将累积函数评估为 WHNF,因为这会以相当剧烈的方式改变程序的语义(包含一些底部与底部的数组) .
也就是说,我同意不幸的是,在几个领域缺乏严格和急切的功能。
对于您的问题,您可以使用更大的堆栈( +RTS -K128M
在这里不够,但 256M 可以),或者您可以使用
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import GHC.Arr
strictAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i,a)] -> Array i e
strictAccumArray fun ini (l,u) ies = case iar of
Array _ _ m barr -> Array l u m barr
where
iar = runSTArray $ do
let n = safeRangeSize (l,u)
stuff = [(safeIndex (l,u) n i, e) | (i, e) <- ies]
arr <- newArray (0,n-1) ini
let go ((i,v):ivs) = do
old <- unsafeRead arr i
unsafeWrite arr i $! fun old v
go ivs
go [] = return arr
go stuff
通过严格的写入,thunk 保持较小,因此没有堆栈溢出。但请注意,列表占用大量空间,因此如果您的列表太长,您可能会遇到堆耗尽。
另一种选择是使用
Data.Map
(或 Data.IntMap
,如果 containers 的版本是 0.4.1.0 或更高版本)而不是数组,因为它带有 insertWith'
,这会强制使用组合函数的结果。例如,代码可以是import qualified Data.Map as M -- or Data.IntMap
import Data.List (foldl')
histo :: M.Map Int (Int,[Int]) -- M.IntMap (Int,[Int])
histo = foldl' upd M.empty [(0,n) | n <- [0 .. 15000000]]
where
upd mp (i,n) = M.insertWith' add i (1,[n]) mp
add (j,val:_) (k,vals) = k `seq` vals `seq` (k+j,val:vals)
add _ pr = pr -- to avoid non-exhaustive pattern warning
使用
Map
的缺点是a -> a -> a
,所以在你的情况下它需要更复杂一些。 Map
s 和 IntMap
s 有一些记账开销,因此这将使用比数组更多的空间。但是,如果更新列表与索引数量相比很大,则差异将可以忽略不计(开销是每个键的 k
个字,与值的大小无关)在这种情况下,值的大小会增长每次更新。 关于haskell - 如何获得严格的 accumArray?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9491624/