[Haskell-cafe] Re: Function to detect duplicates
daniel.is.fischer at web.de
Tue Feb 23 08:09:32 EST 2010
Am Dienstag 23 Februar 2010 13:59:49 schrieb Ertugrul Soeylemez:
> Jonas Almström Duregård <jonas.duregard at gmail.com> wrote:
> > Ertugrul: while your solution is minimalistic, Rafael deemed his
> > ~n*log n implementation too inefficient. Thus your ~n^3 implementation
> > is hardly an improvement...
Not quite as bad, nub is O(n^2).
> My variant has an advantage, though. It is completely lazy, so it will
> take a shortcut, as soon as a duplicate is found. Depending on his
> application, this may be useful or not.
> I think the nub-based solution is the best one in general, but it's the
> base library implementation of nub, which is unfortunate. In fact, with
> a better nub implementation, this becomes an O(n * log n) time
How can you nub in O(n*log n)? Remember, you only have Eq for nub.
> algorithm, too, but with the additional laziness advantage. The article
> you linked to contains such an implementation, I think.
More information about the Haskell-Cafe