Topic: Remove Duplicates from list?

[mkweaver]

In March of 1998, Tony T posted the following code to remove duplicate items from a list.  Are there any improvements that can be made on this using functions added to vlisp since then?

The thread Tony started can be viewed here: http://groups.google.com/group/autodesk.autocad.customization/browse_thread/thread/19cbd1eb1d9a13e9/c433c86f15038465?hl=en&lnk=st&q=vlisp+remove+duplicate&rnum=1#c433c86f15038465

Mike Weaver

Code: [Select]

(defun remove-duplicates (inlist / dupes)
   (apply 'append
      (mapcar
        '(lambda (x)
            (if (not (member x dupes))
               (list (car (setq dupes (cons x dupes))))
            )
         )
         inlist
      )
   )
)

[daron]

Yes, vl-sort:

Code: [Select]

(defun alphalist (listas / conv sort)
     (setq conv   (mapcar 'ascii listas)
      sort   (vl-sort conv '<)
     )
     (mapcar 'chr sort)
)It sorts the list alphanumerically and removes duplicates.

[CAB]

Look here:
http://www.theswamp.org/index.php?topic=4144.0

[ASMI]

One more from me with VL-REMOVE:

Code: [Select]

(defun Remove_Dublicates(inLst)
  (reverse
    (foreach x inLst
       (setq inLst(cons x(vl-remove x inLst)))
    ); end foreach
   ); end reverse
 ); end of Remove_Dublicates
It seems I don't look it in CAB's thread.

[JohnK]

Some code...

Code: [Select]

(defun remove-duplicates-tony (inlist / dupes)
   (apply 'append
      (mapcar
        '(lambda (x)
            (if (not (member x dupes))
               (list (car (setq dupes (cons x dupes)))) ) )
         inlist ) ) )
(defun Remove_Dublicates-ASMI(inLst)
  (reverse
    (foreach x inLst
       (setq inLst(cons x(vl-remove x inLst))))) )
(defun RemoveDuplicates-mp1 ( lst / foo temp )
    (defun foo (x)
        (cond
            ((vl-position x temp) t)
            ((setq temp (cons x temp)) nil)
        )
    )
    (vl-remove-if
       'foo
        lst
    )
)
(defun RemoveDuplicates-mp2 ( lst / temp )
    (vl-remove-if
       '(lambda (x)
            (cond
                ((vl-position x temp) t)
                ((setq temp (cons x temp)) nil)
            )
        )
        lst
    )
)
(defun remove_dup-se7en (lst / cl)
  ;; Se7en
  ;; (remove_dup-se7en mylst)
   (defun workhorse (x)
     (if (not (member x cl)) ;if element not already in CL
       (setq cl (cons x cl))))
  (mapcar 'workhorse lst)
  (reverse cl)
 )
(defun remove-dup-se7en2 ( lst )
  ;; Se7en
  ;;   (apply 'append (remove-dup-se7en2 mylst))
  (if (null lst)
    nil
    (cons
      (if (member (car lst) (cdr lst))
        'nil
        (list (car lst)))
      (remove-duplicates (cdr lst))) ))
Some setup...

Code: [Select]

(setq mylst '(1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0  1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0))

(benchmark
 '(
   (remove-duplicates-tony mylst)
   (apply 'append (remove-dup-se7en2 mylst))
   (remove_Dublicates-ASMI mylst)
   (RemoveDuplicates-mp1 mylst)
   (RemoveDuplicates-mp2 mylst)
   (remove_dup-se7en mylst)
   ))

Results...

Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (REMOVEDUPLICATES-MP1 MYLST).................1032 / 3.88 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST).................1516 / 2.64
    (REMOVE_DUP-SE7EN MYLST).....................2250 / 1.78
    (REMOVE-DUPLICATES-TONY MYLST)...............2438 / 1.64
    (REMOVE_DUBLICATES-ASMI MYLST)...............2875 / 1.39
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...).....4000 / 1 <slowest>

Benchmarking ................Elapsed milliseconds / relative speed for 8192 iteration(s):

    (REMOVEDUPLICATES-MP1 MYLST).................1016 / 3.97 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST).................1516 / 2.66
    (REMOVE_DUP-SE7EN MYLST).....................2235 / 1.8
    (REMOVE-DUPLICATES-TONY MYLST)...............2437 / 1.65
    (REMOVE_DUBLICATES-ASMI MYLST)...............2922 / 1.38
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...).....4031 / 1 <slowest>

[MP]

I'd take those results with a grain of salt. Performance processing lists does not tend to be truly linear.

I'd consider testing against lists of widely varying lengths as well as composition (i.e. nesting level etc.) before I considered it 'conclusive'.

Interesting no less.

[JohnK]

I'd take those results with a grain of salt. Performance processing lists does not tend to be truly linear.

I'd consider testing against lists of widely varying lengths as well as composition (i.e. nesting level etc.) before I considered it 'conclusive'.

Interesting no less.

Im on it...

[JohnK]

Wow your right. I did not meet the differing list length criteria but still interesting results nonetheless. Oh and i added another procedure def to the mix; minor change but weird results for test two.

Code: [Select]

(defun remove-duplicates-tony (inlist / dupes)
   (apply 'append
      (mapcar
        '(lambda (x)
            (if (not (member x dupes))
               (list (car (setq dupes (cons x dupes)))) ) )
         inlist ) ) )
(defun Remove_Dublicates-ASMI(inLst)
  (reverse
    (foreach x inLst
       (setq inLst(cons x(vl-remove x inLst))))) )
(defun RemoveDuplicates-mp1 ( lst / foo temp )
    (defun foo (x)
        (cond
            ((vl-position x temp) t)
            ((setq temp (cons x temp)) nil)
        )
    )
    (vl-remove-if
       'foo
        lst
    )
)
(defun RemoveDuplicates-mp2 ( lst / temp )
    (vl-remove-if
       '(lambda (x)
            (cond
                ((vl-position x temp) t)
                ((setq temp (cons x temp)) nil)
            )
        )
        lst
    )
)
(defun remove_dup-se7en (lst / cl)
  ;; Se7en
  ;; (remove_dup-se7en mylst)
   (defun workhorse (x)
     (if (not (member x cl)) ;if element not already in CL
       (setq cl (cons x cl))))
  (mapcar 'workhorse lst)
  (reverse cl)
 )
(defun remove-dup-se7en2 ( lst )
  ;; Se7en
  ;;   (apply 'append (remove-dup-se7en2 mylst))
  (if (null lst)
    nil
    (cons
      (if (member (car lst) (cdr lst))
        'nil
        (list (car lst)))
      (remove-dup-se7en2 (cdr lst))) ))
(defun remove_dup-se7en3 (lst / cl)
 ;; Se7en
 ;; (remove_dup-se7en3 mylst)
 (set 'workhorse
   (lambda (x)
      (if
       (not (member x cl))
       ;if element not already in CL
       (setq cl (cons x cl)))))
  (mapcar 'workhorse lst)
  (reverse cl))

Code: [Select]

( (lambda ( )
    (setq mylst '(1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0  1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0))


    (benchmark
      '(
        (remove-duplicates-tony mylst)
        (apply 'append (remove-dup-se7en2 mylst))
        (remove_Dublicates-ASMI mylst)
        (RemoveDuplicates-mp1 mylst)
        (RemoveDuplicates-mp2 mylst)
        (remove_dup-se7en mylst)
        (remove_dup-se7en3 mylst)
        ))



    (setq mylst (mapcar '(lambda ( x ) (* 479.93 x)) mylst))

    (benchmark
      '(
        (remove-duplicates-tony mylst)
        (apply 'append (remove-dup-se7en2 mylst))
        (remove_Dublicates-ASMI mylst)
        (RemoveDuplicates-mp1 mylst)
        (RemoveDuplicates-mp2 mylst)
        (remove_dup-se7en mylst)
        (remove_dup-se7en3 mylst)
        ))

    (setq mylst (mapcar '(lambda ( x )
                           (setq nu (fix (/ x 72546544515.2556)))
                           (cond
                             ((< 2815 x)
                              (list x))
                             (T (~ (fix x)))))
                        mylst)
          )

    (benchmark
      '(
        (remove-duplicates-tony mylst)
        (apply 'append (remove-dup-se7en2 mylst))
        (remove_Dublicates-ASMI mylst)
        (RemoveDuplicates-mp1 mylst)
        (RemoveDuplicates-mp2 mylst)
        (remove_dup-se7en mylst)
        (remove_dup-se7en3 mylst)
        ))
    )
 )

Elapsed milliseconds / relative speed for 2048 iteration(s):

    (REMOVEDUPLICATES-MP1 MYLST).................1140 / 1.95 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST).................1250 / 1.78
    (REMOVE_DUP-SE7EN MYLST).....................1265 / 1.75
    (REMOVE_DUP-SE7EN3 MYLST)....................1328 / 1.67
    (REMOVE-DUPLICATES-TONY MYLST)...............1343 / 1.65
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...).....2219 / 1.00
    (REMOVE_DUBLICATES-ASMI MYLST)...............2219 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 4096 iteration(s):

    (REMOVEDUPLICATES-MP1 MYLST).................1219 / 3.28 <fastest>
    (REMOVE_DUP-SE7EN3 MYLST)....................2281 / 1.75
    (REMOVEDUPLICATES-MP2 MYLST).................2438 / 1.64
    (REMOVE_DUBLICATES-ASMI MYLST)...............2750 / 1.45
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...).....3531 / 1.13
    (REMOVE_DUP-SE7EN MYLST).....................3625 / 1.10
    (REMOVE-DUPLICATES-TONY MYLST)...............4000 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 2048 iteration(s):

    (REMOVE_DUP-SE7EN MYLST).....................1062 / 1.82 <fastest>
    (REMOVE_DUP-SE7EN3 MYLST)....................1078 / 1.80
    (REMOVE-DUPLICATES-TONY MYLST)...............1234 / 1.57
    (REMOVEDUPLICATES-MP1 MYLST).................1359 / 1.43
    (REMOVE_DUBLICATES-ASMI MYLST)...............1406 / 1.38
    (REMOVEDUPLICATES-MP2 MYLST).................1594 / 1.22
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...).....1937 / 1.00 <slowest>

[It's Alive!]

oh! oh! I want to play

try this one

Code: [Select]

(DEFUN REMOVEDUPLICATES-DM (L / ITEM I OUT)
 (SETQ OUT '()
       I -1
 )
 (WHILE (SETQ ITEM (NTH (SETQ I (1+ I)) L))
  (IF (NOT (MEMBER ITEM OUT))
   (SETQ OUT (CONS ITEM OUT))
  )
 )
 (REVERSE OUT)
)



[It's Alive!]

oh darn 

Code: [Select]

Elapsed milliseconds / relative speed for 8192 iteration(s):
    (REMOVEDUPLICATES-MP1 MYLST).................1342 / 7.21 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST).................2183 / 4.43
    (REMOVE_DUP-SE7EN MYLST).....................3836 / 2.52
    (REMOVE_DUP-SE7EN3 MYLST)....................3995 / 2.42
    (REMOVEDUPLICATES-DM MYLST)..................4417 / 2.19
    (REMOVE-DUPLICATES-TONY MYLST)...............4697 / 2.06
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...).....6910 / 1.40
    (REMOVE_DUBLICATES-ASMI MYLST)...............9674 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 8192 iteration(s):
    (REMOVEDUPLICATES-MP1 MYLST)..................1502 / 6.89 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2404 / 4.30
    (REMOVE_DUP-SE7EN MYLST)......................3975 / 2.60
    (REMOVE_DUP-SE7EN3 MYLST).....................4056 / 2.55
    (REMOVEDUPLICATES-DM MYLST)...................4377 / 2.36
    (REMOVE-DUPLICATES-TONY MYLST)................4827 / 2.14
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......7210 / 1.43
    (REMOVE_DUBLICATES-ASMI MYLST)...............10345 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 8192 iteration(s):
    (REMOVEDUPLICATES-MP1 MYLST)..................1442 / 6.99 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2294 / 4.39
    (REMOVE_DUP-SE7EN MYLST)......................3945 / 2.55
    (REMOVE_DUP-SE7EN3 MYLST).....................4156 / 2.42
    (REMOVEDUPLICATES-DM MYLST)...................4437 / 2.27
    (REMOVE-DUPLICATES-TONY MYLST)................4816 / 2.09
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......7141 / 1.41
    (REMOVE_DUBLICATES-ASMI MYLST)...............10074 / 1.00 <slowest>


[T.Willey]

oh darn 

Doesn't look to good for you code Daniel.  Try using 'vl-position' instead of 'member' as member returns the whole list from the point it is found, and vl-position only returns an integer of the position it is found.  May speed things up.

[ASMI]

Maybe one more fresh:

Code: [Select]

(defun Remove_Dublicates2-ASMI(inLst / outLst)
  (mapcar
      '(lambda(x)(setq outLst(cons x(vl-remove x outLst))))
    inLst
    ); end mapcar
  (reverse outLst)
 ); end of Remove_Dublicates2-ASMI
It seems MAPCAR faster than FOREACH.

[It's Alive!]

May speed things up.

sure did

Code: [Select]

Elapsed milliseconds / relative speed for 8192 iteration(s):
    (REMOVEDUPLICATES-MP1 MYLST)..................1172 / 10.66 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2022 / 6.18
    (REMOVEDUPLICATES-DM2 MYLST)..................2423 / 5.15
    (REMOVE_DUP-SE7EN MYLST)......................3395 / 3.68
    (REMOVE_DUP-SE7EN3 MYLST).....................3435 / 3.64
    (REMOVEDUPLICATES-DM1 MYLST)..................3736 / 3.34
    (REMOVE-DUPLICATES-TONY MYLST)................4426 / 2.82
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......6139 / 2.03
    (REMOVE_DUBLICATES-ASMI MYLST)...............12488 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 8192 iteration(s):
    (REMOVEDUPLICATES-MP1 MYLST)..................1332 / 9.65 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2143 / 6.00
    (REMOVEDUPLICATES-DM2 MYLST)..................2463 / 5.22
    (REMOVE_DUP-SE7EN MYLST)......................3515 / 3.66
    (REMOVE_DUP-SE7EN3 MYLST).....................3555 / 3.62
    (REMOVEDUPLICATES-DM1 MYLST)..................3685 / 3.49
    (REMOVE-DUPLICATES-TONY MYLST)................4626 / 2.78
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......6249 / 2.06
    (REMOVE_DUBLICATES-ASMI MYLST)...............12859 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 8192 iteration(s):
    (REMOVEDUPLICATES-MP1 MYLST)..................1242 / 10.18 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2093 / 6.04
    (REMOVEDUPLICATES-DM2 MYLST)..................2414 / 5.24
    (REMOVE_DUP-SE7EN MYLST)......................3525 / 3.59
    (REMOVE_DUP-SE7EN3 MYLST).....................3565 / 3.55
    (REMOVEDUPLICATES-DM1 MYLST)..................3715 / 3.40
    (REMOVE-DUPLICATES-TONY MYLST)................4596 / 2.75
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......6480 / 1.95
    (REMOVE_DUBLICATES-ASMI MYLST)...............12638 / 1.00 <slowest>
Command:


[gile]

Here's my 2 cents

Code: [Select]

(defun remove_doubles (lst)
  (if lst
    (cons (car lst) (remove_doubles (vl-remove (car lst) lst)))
  )
)
Obviously, this recursive form seems to run faster :

Code: [Select]

Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):

    (REMOVE_DOUBLES MYLST).......................1094 / 5.13 <fastest>
    (REMOVEDUPLICATES-MP1 MYLST).................1625 / 3.45
    (REMOVEDUPLICATES-MP2 MYLST).................2421 / 2.32
    (REMOVE_DUP-SE7EN3 MYLST)....................2859 / 1.96
    (REMOVE_DUBLICATES2-ASMI MYLST)..............2875 / 1.95
    (REMOVE_DUP-SE7EN MYLST).....................2891 / 1.94
    (REMOVE-DUPLICATES-TONY MYLST)...............3203 / 1.75
    (REMOVE_DUBLICATES-ASMI MYLST)...............3844 / 1.46
    (REMOVEDUPLICATES-DM MYLST)..................4813 / 1.17
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...).....5610 / 1.00 <slowest>

[JohnK]

Here's my 2 cents
...

Nice!