On 31/07/10 13:49, Stephen Tetley wrote:
Although I haven't calculated the Big-O scores suspect that original
post will actually be the best, the solutions that metamorph into a
list and out again look like they're doing needless extra work.
They're both O(size m) time, and yes the original is best (not least for
its simplicity and elegance); I now think that (on my part) it was a
case of following optimisation strategies without thinking hard enough
whether they apply: ie, traversing only once can be beneficial for space
reasons under certain circumstances [1]
But as Data.Map is spine-strict, there is no space saving here by
traversing only once, as the spine is already there taking up O(size m)
space before we even start traversing (whereas with lazy lists the spine
might not be taking up any space yet).
[1] to give a classic example:
mean :: Fractional a => [a] -> a
mean xs = sum xs / genericLength xs
which often consumes O(length xs) space, reducible to O(1) if only one
traversal is performed.
Claude
--
http://claudiusmaximus.goto10.org
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
