Re: Deleting elments of a list which are in it more than once

From: Bart Demoen (bmd_at_cs.kuleuven.ac.be)
Date: 02/28/05 

Date: Mon, 28 Feb 2005 22:05:50 +0100

tmp123 wrote:

> About next algorithm:
> Doubt1: is it OK? (no time to test it in deep).
> Doubt2: is it O(N*log(N))?
>
> | nodups(I,O) :- nodups(I,_,O).
> | nodups([],_,[]).
> | nodups([H|Q],TREE,O) :-
> | tree(H,TREE,FOUND),
> | ( FOUND==true ->
> | nodups(Q,TREE,O)
> | ;
> | O=[H|QR],
> | nodups(Q,TREE,QR)
> | ).
> |
> | tree(H,[K,_,_],true) :- K==H, !.
> | tree(H,[K,_,_],fail) :- var(K), K=H, !.
> | tree(H,[K,S,_],R) :-
> | H @< K, !,
> | tree(H,S,R).
> | tree(H,[_,_,G],R) :-
> | tree(H,G,R).

It looks ok (I didn't test it thoroughly either) but it definitely isn't
O(N*log(N)) because the tree you build in the second arg of nodups/3 is
not balanced in a way that would make it of that complexity.
You can test that easily by added the following code:

makelist(N,Out) :-
         (N < 0 ->
             Out = []
         ;
             Out = [N|R],
             M is N - 1,
             makelist(M,R)
         ).

test(N) :-
         makelist(N,L),
         time(nodups(L,_)).

and checking the following queries (and their results) in SWI-Prolog:

?- t(100).
% 31,110 inferences, 0.01 CPU in 0.01 seconds (121% CPU, 3111000 Lips)

Yes
?- t(200).
% 122,210 inferences, 0.04 CPU in 0.04 seconds (108% CPU, 3055250 Lips)

Yes
?- t(400).
% 484,410 inferences, 0.13 CPU in 0.13 seconds (98% CPU, 3726231 Lips)

Yes
?- t(800).
% 1,928,810 inferences, 0.52 CPU in 0.52 seconds (101% CPU, 3709250 Lips)

Yes

You can see the number of inferences and the time going up
quadratically.

Cheers

Bart Demoen