提高分块列表的性能

我有一个简单的问题：给定一个整数列表，读第一行为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

提高分块列表的性能

回答

相关问题