Prabhakar Ragde 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
Good point :) Felipe Lessa wrote:
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).
Yes, this has O(n) space complexity since dropWhile can discard the dropped elements. Unfortunately, we now have O(m*n) time complexity since drop n is executed for every list element. Of course, the solution is to first drop n elements and then take tails instead of dropping n elements every time. map (drop n) . tails = tails . drop n O(m*n) O(m) With this, we can write a function that returns the last n elements of a list in O(m) time and O(n) space as lasts :: Int -> [a] -> [a] lasts n xs = head $ [x | (x,[]) <- zip (tails xs) (tails $ drop n xs)] and use it as a drop-in replacement main n = print . sum . map read . lasts n . lines =<< getContents Regards, apfelmus PS: The implementation of lasts n in my original version would be lasts n = reverse . take n . reverse But thanks to map f . reverse = reverse . map f sum . reverse = sum we can leave out one reverse.