Re: Faster remove-duplicates with sorted list.

[WJ]

Barry Margolin wrote:

> In article <3c6c1dab.139781...@nntp.interaccess.com>,
> Thaddeus L Olczyk <olc...@interaccess.com> wrote:
>
> >Is there a fast way to remove duplicate elements in a sorted list
> >where the function sorting is compatible with the "sorting" function?
> >( Meaning that if the sort function says x=>y and y=>x then x=y
> >and that if not (x=>y and y<=x) then not (x=y). )
>
> >I believe that remove-duplicates has to assume that the list is not
> >sorted. Therefore it has to compare each element, element by element
> >( ~N^2 ). Whereas a side by side goes like 2*N.
>
> >The only problem I have is excessive consing which significantly slows
> >down the algorithm.
>
> Untested:
>
> (defun remove-duplicates-sorted (list)
> (loop for element in list
> and last-element = '(nil) then element
> unless (eql element last-element)
> collect element))

Using Racket instead of COBOL:

(define (remove-duplicates-sorted xs [prev xs])
(define (test x) (begin0 (equal? x prev) (set! prev x)))
(filter-not test xs))

(remove-duplicates-sorted '(a a b c c c d d))
=> '(a b c d)


Always remember, and never forget:
WE DON'T NEED NO STINKIN' LOOPS!