Re: Faster remove-duplicates with sorted list.

B. Pym <No_spamming@nowhere_7073.org> wrote:

"Pierre R. Mai" wrote:
 

(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))

 
Testing under SBCL:
 
(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))
 
(uniquify-sorted-list '(a b b c d d e f f f g))
  ===>
(A)
 
(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7))
  ===>
(2)
 
(uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7) :test #'=)
  ===>
debugger invoked on a SIMPLE-TYPE-ERROR in thread
#<THREAD "main thread" RUNNING {23EAC0D1}>:
  Argument Y is not a NUMBER: #:G5

(defun uniquify-sorted-list (list &key (key #'identity) (test #'eql))
  (loop for element in list
        for last-element-key = nil then element-key
        for element-key = (funcall key element)
        for result = nil then (funcall test element-key last-element-key)
        unless result collect element))

Tested with GNU Clisp:

[3]> (uniquify-sorted-list '(a b b c d d e f f f g))
(A B C D E F G)
[4]> (uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7))
(2 3 4 5 6 7)
[5]> (uniquify-sorted-list '(2 2 3 4 4 4 5 5 6 7) :test #'=)
(2 3 4 5 6 7)