提高分塊列表的性能

我有一個簡單的問題：給定一個整數列表，讀第一行爲N。然後，讀取下N行並返回它們的總和。重複，直到N = 0提高分塊列表的性能

我的第一種方法是用這樣的：

main = interact $ unlines . f . (map read) . lines 

f::[Int] -> [String] 
f (n:ls) 
    | n == 0 = [] 
    | otherwise = [show rr] ++ (f rest) 
    where (xs, rest) = splitAt n ls 
      rr = sum xs 
f _ = []

但它相對較慢。我已經用它

ghc -O2 --make test.hs -prof -auto-all -caf-all -fforce-recomp -rtsopts 
time ./test +RTS -hc -p -i0.001 < input.in

凡input.in是一個測試輸入，其中第一行是10萬，其次是100K的隨機數，其次是0。我們可以在下面，它的使用澳圖看異型（N）內存：

enter image description here

EDITED：我原來的問題是比較2點相同慢的方法。我已經更新了它與下面

最佳進場現在比較，如果我做的和反覆，而不是調用sum，我得到的內存

{-# LANGUAGE BangPatterns #-} 

main = interact $ unlines . g . (map read) . lines 

g::[Int] -> [String] 
g (n:ls) 
    | n == 0 = [] 
    | otherwise = g' n ls 0 
g _ = [] 

g' n (l:ls) !cnt 
    | n == 0 = [show cnt] ++ (g (l:ls)) 
    | otherwise = g' (n-1) ls (cnt + l)

enter image description here

我恆量試圖理解第一個例子中導致性能損失的原因。我會猜想所有可能會被懶惰評估的東西？

來源

2014-09-21 kunigami

未經測試的猜測：或許您在第一個示例中對'read'的兩次調用不使用相同的類型，例如有一些「整數」與「整數」問題。（編輯：這個評論是關於問題的以前的版本） – 2014-09-21 21:15:01

我不知道究竟是什麼導致了差異。但我可以告訴你這一點：

Data.Map> sum [1 .. 1e8] 
Out of memory. 

Data.Map> foldl' (+) 0 [1 .. 1e8] 
5.00000005e15

出於某種原因，sum = foldl (+) 0，而不是foldl'（帶撇號）。不同之處在於後者功能更爲嚴格，因此幾乎不使用內存。懶惰版本，相比之下，做這個的：

sum [1..100] 
1 + sum [2..100] 
1 + 2 + sum [3..100] 
1 + 2 + 3 + sum [4.100] 
...

換句話說，它會創建一個巨大的表情，說1 + 2 + 3 + ...然後，就在年底，它試圖對其進行評估所有。很顯然，這將會吃掉很多內存。通過使用foldl'而不是foldl，可以使其立即執行，而不是毫無意義地將它們存儲在RAM中。

您可能還想使用ByteString而不是String來執行I/O;但懶惰的差異可能會給你一個很大的提速。

來源

2014-09-21 20:20:44 MathematicalOrchid

謝謝！我認爲我嘗試的方法確實是效率低下，試圖將全部數據加載到內存中。我已經更新了一個優化的方法來比較差異。我仍然不確定爲什麼第一種方法無法像第二種方法那樣進行精簡處理。感謝您的ByteString建議。我會試一試。 – kunigami 2014-09-21 21:14:48

順便說一下，ByteString實際上是我需要的。我試過的想法只改善了內存佔用，而不是速度。 – kunigami 2014-10-08 02:39:09

我認爲懶惰是阻止你的第一個和第二個版本是等價的。

考慮從輸入「數字」產生的結果

1 
garbage_here 
2 
3 
5 
0

第一個版本將給出一個結果列表[錯誤「......一些語法錯誤」，8]，可以放心地看第二個元素，而第二個版本的錯誤立即臨近。以流媒體的方式實現第一個目標似乎很難。

儘管沒有懶惰，但從第一個版本到第二個版本可能比GHC可以處理的要多 - 它需要融合重寫規則，將元組的第一個元素的foldl/foldl'與splitAt結合起來。 GHC有only recently到了它可以熔合foldl/foldl'的地步。

來源

2014-09-22 01:27:49

是的，我認爲沒有改寫它以更聰明的方式，編譯器不能真正弄清楚了:( – kunigami 2014-10-08 02:37:50

提高分塊列表的性能

回答

相關問題