On 10/14/07, Prabhakar Ragde <[EMAIL PROTECTED]> 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
