Complexity of two cumulative sum (cumsum) functions in Haskell
Consider the following two cumulative sum (cumsum) functions:
cumsum :: Num a => [a] -> [a]
cumsum [] = []
cumsum [x] = [x]
cumsum (x:y:ys) = x : (cumsum $ (x+y) : ys)
and
cumsum' :: Num a => [a] -> [a]
cumsum' x = [sum $ take k x | k <- [1..length x]]
Of course, I prefer the definition of cumsum to that of cumsum' and I understand that the former has linear complexity.
But just why does cumsum' also have linear complexity? take itself has linear complexity in the length of its argument and k runs from 1 to length x . Therefore I'd have expected quadratic complexity for cumsum' .
Moreover, the constant of cumsum' is lower than that of cumsum . Is that due to the recursive list appending of the latter?
NOTE : welcoming any smart definition of a cumulative sum.
EDIT : I'm measuring execution times using (after enabling :set +s in GHCi):
last $ cumsum [1..n]
This is a measurement error caused by laziness.
Every value in Haskell is lazy: it isn't evaluated until necessary. This includes sub-structure of values - so for example when we see a pattern ( x:xs ) this only forces evaluation of the list far enough to identify that the list is non-empty, but it doesn't force the head x or the tail xs .
The definition of last is something like:
last [x] = x
last (x:xs) = last xs
So when last is applied to the result of cumsum' , it inspects the list comprehension recursively, but only enough to track down the last entry. It doesn't force any of the entries, but it does return the last one.
When this last entry is printed in ghci or whatever, then it is forced which takes linear time as expected. But the other entries are never calculated so we don't see the "expected" quadratic behaviour.
Using maximum instead of last does demonstrate that cumnorm' is quadratic whereas cumnorm is linear.
[Note: this explanation is somewhat hand-wavy: really evaluation is entirely driven by what's needed for the final result, so even last is only evaluted at all because its result is needed. Search for things like "Haskell evaluation order" and "Weak Head Normal Form" to get a more precise explanation.]
上一篇: 后缀树和尝试。 有什么不同？