簡單字符串生成中的空間泄漏。爲什麼？

-- 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

簡單字符串生成中的空間泄漏。爲什麼？

回答

相關問題