[Haskell-cafe] Re: On the verge of ... giving up!
apfelmus at quantentunnel.de
Mon Oct 15 04:32:50 EDT 2007
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
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
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.
More information about the Haskell-Cafe