> Niklas Hambüchen <mail <at> nh2.me> writes:
>
> > On 13/10/13 21:42, AntC wrote:
> > ...
> > If you use the Set library, that fact may be very visible!
> > Because Set re-sequences the whole list, as per its Ord instance.
> >
> > But List.nub preserves the list sequence
> > (except for omitting duplicates).
>
> I mean *exactly* what you say here.
>
> ordNub behaves has the same behaviour as nub, while (Set.toList .
> Set.fromList) doesn't.
>
That's great, thank you.
> > [BTW I am still less than convinced that overall a Set-based ordNub is
> > significantly more efficient. I suspect it depends on how big is your
> > list.]
>
> What do you mean?
>
> ordNub is clearly in a different complexity class, ...
Yes, I'm not disputing that.
> ... and the benchmarks that I provided show not only this,
> but also that ordNub is *always* faster than nub,
> even for singleton lists.
Thanks Niklas, I hadn't spotted those benchmarks back in July.
I'm surprised at that result for singletons
(and for very small numbers of elements which are in fact each different).
Especially because List's `nub` uses `filter` ==> fold, which should be
tail-recursive.
It seems to me that for small numbers, the Set-based approach still
requires comparing each element to each other. Plus there's the overhead
for building the Set and inserting each element into it -- where `insert`
again walks the Set to find the insertion point.
Then here's a further possible optimisation, instead of making separate
calls to `member` and `insert`:
* Make a single call to
insert' :: (Ord a) => a -> Set a -> (Bool, Set a)
* The Bool returns True if already a member.
* Else returns an updated Set in the snd, with the element inserted.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
