Geek Answers Handbook

Performance Improvement in Lists

I have a simple problem: given a list of integers, read the first line as N. Then read the next N lines and return their sum. Repeat to N= 0.

My first approach used this:

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 _ = []

But it is relatively slow. I profiled it with

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

Where input.inis the test input, where the first line is 100k, followed by 100k random numbers, followed by 0. We can see in the figure below that it uses O (N) memory:

enter image description here

EDITED . My initial question was comparing two similar slow approaches. I updated it to compare with the optimized approach below

Now, if I do the sum iteratively, instead of calling sum, I get a constant amount of memory

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

, . , ?

+4
2

, . :

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

, - ByteString, String; , , .

+3

, - , .

, ""

1
garbage_here
2
3
5
0

[error "... some parse error", 8], , . , .

, , , GHC - , foldl/foldl' splitAt. GHC , foldl/foldl'.

+1

More articles:


All Articles