.Re: Faster remove-duplicates with sorted list.

[Robert L.]

> > 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.
>
> (defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
> (loop for element in list
> for element-key = (funcall key element)
> for last-element-key = (load-time-value (gensym))
> then element-key
> unless (funcall test element-key last-element-key)
> collect element))

(use foof-loop)

(define (uniquify-sorted-list the-list #!key (key identity) (test eqv?))
(loop ((for element (in-list the-list))
(let new-key (key element))
(old-key (gensym) new-key)
(for result (listing element (if (not (test new-key old-key))))))
=> result))

(uniquify-sorted-list '(0 0 1 2 3 3 3 4 5))
===>
(0 1 2 3 4 5)

(uniquify-sorted-list '(0 2 4 3 5 7 6 8) key: odd?)
===>
(0 3 6)

In Forth?

--
When the Israeli bombers and torpedo-planes were sent to attack and destroy the
ship, the Jewish commander, seeing that it was an American vessel, had
misgivings and reported to the High Command, which simply repeated the orders
to attack and sink the Liberty. www.revilo-oliver.com/rpo/Bit_of_Good_News.html