简单字符串生成中的空间泄漏。为什么？

-- generates names in the following order 
-- a, b, c ... z, aa, ba, ca, ... za, ab, bb, cb ... 
nextName :: String -> String 
nextName [] = "a" 
nextName (x:xs) = if x == 'z' then 'a' : nextName xs else succ x : xs 

-- verify if the number of names generated is as expected. 
countNames :: String -> String -> Int 
countNames start end = loop 1 start 
    where 
     loop acc next = 
      if next == end then 
       acc 
      else 
       loop (acc + 1) (nextName next)

运行countNames "a" "zzzzzz"在ghci中简单字符串生成中的空间泄漏。为什么？

在我的COM运行它占据了整个内存和需要大量的时间来完成的地狱。

如果有人指出发生空间泄漏的位置和原因，请注意它吗？

来源

2013-10-14 santosh

制作'loop'严格其参数。 – Satvik

你是如何编译的？ – jberryman

问题是一个大的计数器thunk，因为在计数器acc上循环不严格。通常的解决方案是使用seq或BangPatterns使其更为严格。这里是使用BangPatterns的解决方案。

{-# LANGUAGE BangPatterns #-} 
-- generates names in the following order 
-- a, b, c ... z, aa, ba, ca, ... za, ab, bb, cb ... 
nextName :: String -> String 
nextName [] = "a" 
nextName (x:xs) = if x == 'z' then 'a' : nextName xs else succ x : xs 

-- verify if the number of names generated is as expected. 

countNames :: String -> String -> Int 
countNames start end = loop 1 start 
    where 
     loop !acc next = 
      if next == end then 
       acc 
      else 
       loop (acc + 1) (nextName next)

来源

2013-10-14 07:50:06 Satvik

为什么GHC严格性分析器没有（不能？）捕获这种简单的累加器？这种事情几乎捕捉到Haskeller的每一个开始，并有充分的理由。当我刚开始听说严格性分析器时，我认为至少它会严格评估一个简单的整数和。直到我花了一个下午追逐堆栈溢出，我才意识到自己的错误。 – bgamari

你可以看看这个页面：http：//www.haskell.org/haskellwiki/Performance/Strictness#Strictness_analysis tl; dr：严格性分析不是默认执行的，你应该使用“-O”标志。 – Nicolas

虽然采用严格的评估解决您的问题，我建议你能够重复使用标准函数来计算区间长度：

countNames :: String -> String -> Int 
countNames start end = (+) 1 . length . takeWhile (/= end) $ iterate nextName start

说明：

iterate产生无限列表nextName：[start, nextname start, nextname (nextName start), ...];
takeWhile (/= end)保留列表元素，直到达到预期值（不包括上限）;
然后你把length再加1

来源

2013-10-14 08:30:30 Nicolas

不知道迭代。这真的很有用。学到了什么。谢谢。 – santosh

简单字符串生成中的空间泄漏。为什么？

回答

相关问题