[Haskell-cafe] Re: On the verge of ... giving up!

Felipe Lessa felipe.lessa at gmail.com
Sun Oct 14 16:30:39 EDT 2007


On 10/14/07, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:
> > main n = print . sum . map read . take n . reverse . lines =<< getContents
>
> Could someone describe succinctly how to compute the space complexity of
> this program, if there are m lines of input and m >> n? Many thanks. --PR

'reverse' needs to go to the end of the list to start outputting, so
it has to keep all elements in memory somewhere at least in one moment
of time. That means that the program has space complexity of O(m) --
the other functions are all O(1) in terms of line count.

You may try this version instead:

main n = print . sum . map read . head . dropWhile (not . null . drop
n) . tails . lines =<< getContents

where I changed (take n . reverse) to (head . dropWhile (not . null .
drop n) . tails). Yes, I cheated, I'm using Data.List =). With this
version you keep only n lines in memory at any moment, so it has space
complexity of O(n).

Please anybody correct me if I'm wrong.

Cheers,

-- 
Felipe.


More information about the Haskell-Cafe mailing list