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