Print Page - Remove Duplicates from list?

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: mkweaver on September 28, 2007, 08:07:48 AM

Title: Remove Duplicates from list?
Post by: mkweaver on September 28, 2007, 08:07:48 AM

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

Title: Re: Remove Duplicates from list?
Post by: daron on September 28, 2007, 08:41:27 AM

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.

Title: Re: Remove Duplicates from list?
Post by: CAB on September 28, 2007, 08:52:56 AM

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

Title: Re: Remove Duplicates from list?
Post by: ASMI on September 28, 2007, 09:37:24 AM

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.

Title: Re: Remove Duplicates from list?
Post by: JohnK on September 28, 2007, 11:25:34 AM

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...

Quote

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>

Title: Re: Remove Duplicates from list?
Post by: MP on September 28, 2007, 12:22:50 PM

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.

:)

Title: Re: Remove Duplicates from list?
Post by: JohnK on September 28, 2007, 12:28:35 PM

Quote from: MP on September 28, 2007, 12:22:50 PM

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...

Title: Re: Remove Duplicates from list?
Post by: JohnK on September 28, 2007, 01:04:32 PM

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

Quote

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>

Title: Re: Remove Duplicates from list?
Post by: It's Alive! on September 28, 2007, 01:59:45 PM

oh! oh! I want to play :lol:

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

Title: Re: Remove Duplicates from list?
Post by: It's Alive! on September 28, 2007, 02:22:53 PM

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>

Title: Re: Remove Duplicates from list?
Post by: T.Willey on September 28, 2007, 02:29:33 PM

Quote from: Daniel on September 28, 2007, 02:22:53 PM

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.

Title: Re: Remove Duplicates from list?
Post by: ASMI on September 28, 2007, 02:37:04 PM

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.

Title: Re: Remove Duplicates from list?
Post by: It's Alive! on September 28, 2007, 02:57:32 PM

Quote from: T.Willey on September 28, 2007, 02:29:33 PM

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:

Title: Re: Remove Duplicates from list?
Post by: gile on September 28, 2007, 03:45:24 PM

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>

Title: Re: Remove Duplicates from list?
Post by: JohnK on September 28, 2007, 04:00:28 PM

Quote from: gile on September 28, 2007, 03:45:24 PM

Here's my 2 cents
...

Nice!

Title: Re: Remove Duplicates from list?
Post by: ASMI on September 28, 2007, 04:26:09 PM

Another test with 100000 iterations and list length = 30.

Code: [Select]

RemoveDuplicates-mp1       (min:sec.msek): 0:06.98 <fastest>
remove_doubles (gile)         (min:sec.msek): 0:08.28
remove_dup-se7en3           (min:sec.msek): 0:13.38
Remove_Dublicates2-ASMI   (min:sec.msek): 0:13.41
remove_dup-se7en             (min:sec.msek): 0:13.62
remove-duplicates-tony       (min:sec.msek) 0:17.42
RemoveDuplicates-mp2        (min:sec.msek) 0:18.06
remove-dup-se7en2            (min:sec.msek) 20:19.14
Remove_Dublicates-ASMI     (min:sec.msek)  0:21.44 <slowlest>

Title: Re: Remove Duplicates from list?
Post by: Binky on September 28, 2007, 05:19:44 PM

Lamba hurts my brain and anything that starts with VL is still ahead of me. So here is a non-gifted monkey behind a typewriter approach.. (may not be even close to fast, but it does work)

Code: [Select]

(defun remove_duplicate_list-Binky (xlist / ylist)

  (foreach x xlist
	   (foreach y ylist
		    (if (= x y)
		      (setq fg 1)))
	   (if (/= fg 1)
	     (setq ylist (cons x ylist)))
	   (setq fg 0))
  ylist)

Here are the results

Code: [Select]

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

    (REMOVEDUPLICATES-MP1 MYLST)..................1437 / 9.25 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2391 / 5.56
    (REMOVE_DUP-SE7EN MYLST)......................2812 / 4.73
    (REMOVE_DUP-SE7EN3 MYLST).....................2875 / 4.63
    (REMOVE-DUPLICATES-TONY MYLST)................3547 / 3.75
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......5703 / 2.33
    (REMOVE_DUBLICATES-ASMI MYLST)................6454 / 2.06
    (REMOVE_DUPLICATE_LIST-BINKY MYLST)..........13297 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 16384 iteration(s):

    (REMOVEDUPLICATES-MP1 MYLST)..................1594 / 8.71 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2640 / 5.26
    (REMOVE_DUP-SE7EN MYLST)......................2984 / 4.66
    (REMOVE_DUP-SE7EN3 MYLST).....................3047 / 4.56
    (REMOVE-DUPLICATES-TONY MYLST)................3594 / 3.87
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......5641 / 2.46
    (REMOVE_DUBLICATES-ASMI MYLST)................6765 / 2.05
    (REMOVE_DUPLICATE_LIST-BINKY MYLST)..........13891 / 1.00 <slowest>
Elapsed milliseconds / relative speed for 16384 iteration(s):

    (REMOVEDUPLICATES-MP1 MYLST)..................1578 / 21.11 <fastest>
    (REMOVEDUPLICATES-MP2 MYLST)..................2531 / 13.16
    (REMOVE_DUP-SE7EN MYLST)......................3063 / 10.88
    (REMOVE_DUP-SE7EN3 MYLST).....................3156 / 10.56
    (REMOVE-DUPLICATES-TONY MYLST)................3719 / 8.96
    (APPLY (QUOTE APPEND) (REMOVE-DUP-SE...)......5641 / 5.91
    (REMOVE_DUBLICATES-ASMI MYLST)................6750 / 4.94
    (REMOVE_DUPLICATE_LIST-BINKY MYLST)..........33312 / 1.00 <slowest>

so here I find some motivation to learn more.

Title: Re: Remove Duplicates from list?
Post by: MP on September 28, 2007, 05:30:20 PM

Quote from: Binky on September 28, 2007, 05:19:44 PM

... non-gifted monkey behind a typewriter ...

I'm sorry, that position is taken.

Title: Re: Remove Duplicates from list?
Post by: Binky on September 28, 2007, 06:13:36 PM

Can I be his apprentice then??????

Title: Re: Remove Duplicates from list?
Post by: FengK on September 28, 2007, 07:06:58 PM

Quote from: Se7en on September 28, 2007, 04:00:28 PM

Quote from: gile on September 28, 2007, 03:45:24 PM
Here's my 2 cents
...
Nice!

i second that!

Title: Re: Remove Duplicates from list?
Post by: MP on September 28, 2007, 07:36:02 PM

Quote from: gile on September 28, 2007, 03:45:24 PM

Code: [Select]
(defun remove_doubles (lst) (if lst (cons (car lst) (remove_doubles (vl-remove (car lst) lst))) ) )
...

I like the way you think.

:)

Title: Re: Remove Duplicates from list?
Post by: MP on September 28, 2007, 07:53:30 PM

What's interesting is that the original --

Code: [Select]

(defun remove_doubles (lst)
  (if lst
    (cons (car lst) (remove_doubles (vl-remove (car lst) lst)))
  )
)

Should be outperformed by this --

Code: [Select]

(defun remove_doubles2 (lst)
  (if lst
    (cons (car lst) (remove_doubles2 (vl-remove (car lst) (cdr lst))))
  )
)

But the difference in performance is negligible.

(Based on a very cursory test).

:)

Title: Re: Remove Duplicates from list?
Post by: gile on September 29, 2007, 04:59:11 AM

Quote from: MP on September 28, 2007, 07:53:30 PM

What's interesting is that the original --

Code: [Select]
(defun remove_doubles (lst) (if lst (cons (car lst) (remove_doubles (vl-remove (car lst) lst))) ) )
Should be outperformed by this --

Code: [Select]
(defun remove_doubles2 (lst) (if lst (cons (car lst) (remove_doubles2 (vl-remove (car lst) (cdr lst)))) ) )
But the difference in performance is negligible.

(Based on a very cursory test).

:)

May be a joke, but my poor English unable me to really understand it.

Anyway, I thank you (Se7en, Kelie, MP) for your comments, I receive them according to how I consider your great knowledge and experience in LISP writing (you and some other ones are my "Mentors").

PS: this routine is the example I use when I try to explain the recursive form.

Title: Re: Remove Duplicates from list?
Post by: mkweaver on September 29, 2007, 09:10:14 AM

Thanks for the response, folks. These are great!

Mike Weaver

Title: Re: Remove Duplicates from list?
Post by: JohnK on October 01, 2007, 08:58:45 AM

Quote from: gile on September 29, 2007, 04:59:11 AM

...
Anyway, I thank you (Se7en, Kelie, MP) for your comments, I receive them according to how I consider your great knowledge and experience in LISP writing (you and some other ones are my "Mentors").
...

That is funny because i study and learn from your code!?

Title: Re: Remove Duplicates from list?
Post by: FengK on October 01, 2007, 12:52:42 PM

That is funny because i study and learn from your code!?
[/quote]

Quote from: Se7en on October 01, 2007, 08:58:45 AM

Quote from: gile on September 29, 2007, 04:59:11 AM
...
Anyway, I thank you (Se7en, Kelie, MP) for your comments, I receive them according to how I consider your great knowledge and experience in LISP writing (you and some other ones are my "Mentors").
...

That is funny because i study and learn from your code!?

i suppose he really meant MP.

Title: Re: Remove Duplicates from list?
Post by: VovKa on July 06, 2008, 05:17:49 AM

found my way to here from a faraway thread
mine:

Code: [Select]

(defun vk_RemoveDupl
		     (InList / OutList First)
  (while InList
    (setq First	  (car InList)
	  InList  (cdr InList)
	  OutList (cons First OutList)
    )
    (if	(vl-position First InList)
      (setq InList (vl-remove First InList))
    )
  )
  (reverse OutList)
)

it's slower that gile's recursive one, but has no "19975" limitation.

Title: Re: Remove Duplicates from list?
Post by: CAB on July 06, 2008, 07:22:40 AM

Thanks for your contribution VovKa

Another look back. http://www.theswamp.org/index.php?topic=7891.0

Title: Re: Remove Duplicates from list?
Post by: VovKa on July 06, 2008, 08:02:21 AM

interesting look back :)
sometimes duplicates are not so frequent or there could be no duplicates at all in a given list, that's why i use vl-position
try this

Code: [Select]

(progn (setq mylst nil
	     i 0
       )
       (repeat 1000 (setq mylst (cons (setq i (1+ i)) mylst)))
       (benchmark '((unique mylst) (vk_RemoveDupl mylst)))
)

Title: Re: Remove Duplicates from list?
Post by: domenicomaria on March 12, 2022, 12:55:18 PM

(defun :LST-REMOVE-DUPLICATES (l / r)
(while (setq i (car l) ) (setq r (cons i r) l (vl-remove i l) ) )
(reverse r)
)

this one seems to be faster

Title: Re: Remove Duplicates from list?
Post by: Marc'Antonio Alessi on March 14, 2022, 09:16:17 AM

Quote from: domenicomaria on March 12, 2022, 12:55:18 PM

(defun :LST-REMOVE-DUPLICATES (l / r)
(while (setq i (car l) ) (setq r (cons i r) l (vl-remove i l) ) )
(reverse r)
)

this one seems to be faster

you need to declare "i" as local...

Code: [Select]

; Function: ALE_RemoveDupOnLst2
;
; Version 1.00 - 9 Apr 2003
;
; Description:
;   removes all the duplicated elements leaving originals,
;   faster on lists with high number of duplicates
;   For example:
;   (setq alist nil) (setq alist2 '(1 2 3 4 4 5 5 5 6 7 8 9 9 9 9))
;   (setq alist (repeat 500 (setq alist (append alist alist2))))
;
; Arguments:
;   In_Lst = A list
;
(defun ALE_RemoveDupOnLst2 (In_Lst / OutLst CarElm)
  (while In_Lst
    (setq 
      In_Lst (vl-remove (setq CarElm (car In_Lst)) (cdr In_Lst))
      OutLst (cons CarElm OutLst)
    )
  )
  (reverse OutLst)
)

Title: Re: Remove Duplicates from list?
Post by: Marc'Antonio Alessi on March 14, 2022, 09:22:13 AM

Code: [Select]

; Marc'Antonio Alessi
; Function: ALE_RemoveDupOnLst14
;
; Version 1.00 9 Apr 2003
;
; Description:
;   removes all the duplicated elements leaving originals,
;   for R14
;
; Arguments:
;   In_Lst = A list
;
(defun ALE_RemoveDupOnLst14 (In_Lst / OutLst)
  (reverse
    (foreach ForElm In_Lst
      (if (member ForElm OutLst)
        OutLst
        (setq OutLst (cons ForElm OutLst))
      )
    )
  )
)

Title: Re: Remove Duplicates from list?
Post by: domenicomaria on March 14, 2022, 09:55:46 AM

(setq l '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54) )
(setq l (append l l l l l l l) )

(ALE_REMOVEDUPONLST2 L)........390 / 1.0428 <slowest>
(:LST-REMOVE-DUPLICATES L).....374 / 1.0000 <FASTEST>

. . .
because there is no need of
(cdr In_Lst)
if you add CarElm to OutLst
BEFORE !

Title: Re: Remove Duplicates from list?
Post by: VovKa on March 14, 2022, 10:52:39 AM

(:LST-REMOVE-DUPLICATES '(1 nil 2 3))

Title: Re: Remove Duplicates from list?
Post by: Marc'Antonio Alessi on March 14, 2022, 11:50:38 AM

Quote from: domenicomaria on March 14, 2022, 09:55:46 AM

(setq l '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54) )
(setq l (append l l l l l l l) )
(ALE_REMOVEDUPONLST2 L)........390 / 1.0428 <slowest>
(:LST-REMOVE-DUPLICATES L).....374 / 1.0000 <FASTEST>
. . .
because there is no need of
(cdr In_Lst)
if you add CarElm to OutLst
BEFORE !

Code: [Select]

(defun ALE_RemoveDupOnLst2 (L / o e)
  (while L
    (setq
      L (vl-remove (setq e (car L)) (cdr L))
      o (cons e o)
    )
  )
  (reverse o)
)

Code: [Select]

(Benchmark '(
(ALE_RemoveDupOnLst2 l)
(:LST-REMOVE-DUPLICATES l)
(ALE_RemoveDupOnLst2 l)
(:LST-REMOVE-DUPLICATES l)
))
--- Benchmark utility: In memory of Michael Puckett ---
Elapsed milliseconds / relative speed for 2048 iteration(s):
    (ALE_REMOVEDUPONLST2 L)........1437 / 1.01 <fastest>
    (:LST-REMOVE-DUPLICATES L).....1438 / 1.01
    (ALE_REMOVEDUPONLST2 L)........1453 / 1
    (:LST-REMOVE-DUPLICATES L).....1453 / 1 <slowest>

Title: Re: Remove Duplicates from list?
Post by: Marc'Antonio Alessi on March 14, 2022, 11:53:40 AM

BricsCAD V22

Code: [Select]

--- Benchmark utility: In memory of Michael Puckett ---
Elapsed milliseconds / relative speed for 8192 iteration(s):
    (ALE_REMOVEDUPONLST2 L)........1062 / 1.03 <fastest>
    (ALE_REMOVEDUPONLST2 L)........1078 / 1.01
    (:LST-REMOVE-DUPLICATES L).....1094 / 1
    (:LST-REMOVE-DUPLICATES L).....1094 / 1 <slowest>

Title: Re: Remove Duplicates from list?
Post by: Marc'Antonio Alessi on March 14, 2022, 12:03:26 PM

Maybe a VERY little faster...

Code: [Select]

(defun ALE_RemoveDupOnLst4 (L / o e)
 (reverse
  (while L
    (setq
      L (vl-remove (setq e (car L)) (cdr L))
      o (cons e o)
    )
  )
 )
)

Title: Re: Remove Duplicates from list?
Post by: domenicomaria on March 14, 2022, 12:55:27 PM

Quote from: VovKa on March 14, 2022, 10:52:39 AM

(:LST-REMOVE-DUPLICATES '(1 nil 2 3))

(defun :LST-REMOVE-DUPLICATES (l / i r)
(while (or (setq i (car l) ) (setq l (cdr l) ) ) (setq r (cons i r) l (vl-remove i l) ) )
(reverse r)
)
This one, seems to work, but it is not faster.
...
... The truth is that you are always right ! :-)
...

Title: Re: Remove Duplicates from list?
Post by: domenicomaria on March 14, 2022, 02:01:52 PM

Quote from: VovKa on July 06, 2008, 05:17:49 AM

found my way to here from a faraway thread
mine:
Code: [Select]
(defun vk_RemoveDupl (InList / OutList First) (while InList (setq First (car InList) InList (cdr InList) OutList (cons First OutList) ) (if (vl-position First InList) (setq InList (vl-remove First InList)) ) ) (reverse OutList) )it's slower that gile's recursive one, but has no "19975" limitation.

I know that when you do something,
there is always a good reason.

So let me to understand :

why do you use vl-position?

I believe that
vl-remove contains within it a function like vl-position. . . .
. . .
because before removing an element
it must check if it is present in the list,
and what is/are the position/s . . .
(because vl-remove removes ALL the items to remove)
. . .
so what's the point of using vl-position before vl-remove?

Title: Re: Remove Duplicates from list?
Post by: domenicomaria on March 14, 2022, 02:30:00 PM

(defun :LST-REMOVE-DUPLICATES (l / i r)
(while (or (setq i (car l) ) (setq l (cdr l) ) ) (setq r (cons i r) l (vl-remove i l) ) )
(reverse r)
)
However this code is still wrong,
because if there is only one NIL and it is the last element,
it is removed anyway, even though it is not a duplicate . . .

Title: Re: Remove Duplicates from list?
Post by: VovKa on March 14, 2022, 03:02:21 PM

Quote from: domenicomaria on March 14, 2022, 02:01:52 PM

why do you use vl-position?

i explained it in this post https://www.theswamp.org/index.php?topic=19128.msg288827#msg288827

Title: Re: Remove Duplicates from list?
Post by: domenicomaria on March 15, 2022, 03:05:50 AM

Quote from: VovKa on March 14, 2022, 03:02:21 PM

i explained it in this post https://www.theswamp.org/index.php?topic=19128.msg288827#msg288827

You are right !
I made these the following 2 tests only with your function :
vk_RemoveDupl
and
vk_RemoveDupl_2 (where I have removed vl-position)
. . .

Code - Auto/Visual Lisp: [Select]

(defun vk_RemoveDupl
                                                        (InList / OutList First)
        (while InList
                (setq   First     (car InList)
                                InList  (cdr InList)
                                OutList (cons First OutList)
                )
                (if (vl-position First InList)
                        (setq InList (vl-remove First InList))
                )
        )
        (reverse OutList)
)
 
. . . . . 
 
(defun vk_RemoveDupl_2
                                                          (InList / OutList First)
        (while InList
                (setq   First     (car InList)
                                InList  (cdr InList)
                                OutList (cons First OutList)
                )
                (setq InList (vl-remove First InList))
        )
        (reverse OutList)
)
 

(setq mylst nil i 0)
(repeat 1000 (setq mylst (cons (setq i (1+ i)) mylst)))
---------------------------------------------------------------------
(benchmark '((vk_RemoveDupl mylst) (vk_RemoveDupl_2 mylst)))

Elapsed milliseconds for 80 iteration(s)/ relative Timing :

(VK_REMOVEDUPL_2 MYLST).....5039 / 20.1560 <slowest>
(VK_REMOVEDUPL MYLST)........250 / 1.0000 <fastest>

---------------------------------------------------------------------

(setq mylst (append mylst mylst mylst mylst mylst mylst ) )
(benchmark '((vk_RemoveDupl mylst) (vk_RemoveDupl_2 mylst)))

(now mylst contains duplicates . . .)

Elapsed milliseconds for 5 iteration(s)/ relative Timing :

(VK_REMOVEDUPL MYLST).......1794 / 1.0176 <slowest>
(VK_REMOVEDUPL_2 MYLST).....1763 / 1.0000 <fastest>

---------------------------------------------------------------------

So the result depends from the "type" of the list ...

... and because vl-position finds only the first position
while vl-remove, before removing something, has to find all the positions
. . .
VovKa, You are always right ! :-)

Title: Re: Remove Duplicates from list?
Post by: VovKa on March 15, 2022, 08:18:25 AM

Quote from: domenicomaria on March 15, 2022, 03:05:50 AM

So the result depends from the "type" of the list ...

this is absolutely correct
that is why it would be good to have both variants in one's library and use the appropriate

Title: Re: Remove Duplicates from list?
Post by: ribarm on March 27, 2022, 05:05:20 AM

Another one :
https://www.cadtutor.net/forum/topic/74677-lisp-for-total-line-length-for-lines-which-in-every-separately-box/?do=findComment&comment=591483

Something like :

Code - Auto/Visual Lisp: [Select]

(setq lst '("box1" "box1" "box1" "box2" "box2" "box3" "box3"))
(defun mr_RemoveDupl (InList fuzz)
  (vl-remove-if-not
    (function
      (lambda ( x )
        (if
          (vl-some
            (function
              (lambda ( y )
                (equal x y fuzz)
              )
            ) InList
          )
          (progn
            (setq InList
              (vl-remove-if
                (function
                  (lambda ( y )
                    (equal x y fuzz)
                  )
                ) InList
              )
            )
            x
          )
        )
      )
    ) InList
  )
)
(mr_RemoveDupl lst 0) => ("box1" "box2" "box3")
 

This one is for benchmark testing :

Code - Auto/Visual Lisp: [Select]

(setq lst '("box1" "box1" "box1" "box2" "box2" "box3" "box3"))
(defun mr_RemoveDupl (InList fuzz / x r )
  (while (setq x (car InList))
    (setq InList
      (vl-remove-if
        (function
          (lambda ( y )
            (equal x y fuzz)
          )
        ) InList
      )
    )
    (setq r (append r (list x)))
  )
)
(mr_RemoveDupl lst 0) => ("box1" "box2" "box3")
 

TheSwamp

Code Red => AutoLISP (Vanilla / Visual) => Topic started by: mkweaver on September 28, 2007, 08:07:48 AM