[Haskell-cafe] Arrays performance
paolo.veronelli at gmail.com
Wed Jan 3 13:38:20 EST 2007
Quoting Udo Stenzel <u.stenzel at web.de>:
> paolo.veronelli at gmail.com wrote:
> It isn't, but not for the reasons you might suspect. You're using
> 'nub', which is quadratic, and your 'coupage' is also quadratic because
> it uses 'lookup' on a list, which is linear, a linear number of times.
> You can get this down to O(n * log n) if you replace these lists by
> Data.Map and Data.Set, to get down to O(n) you need arrays there, too,
> but that would be pointless, because you're also using 'sort', which is
> already in O(n * log n). The core of the algorithm is clearly linear in
> the length of its input.
> (Btw, putting 'devil' into a state monad doesn't make much sense. I
> think, ordinary recursion would be more clear. In fact, it's a
Ok, I've simplified some code and moved to foldl, to collect the result.
I paste new version in case you care give me some moe suggestion.
More information about the Haskell-Cafe