Topic: Remove Duplicates from list?

[Marc'Antonio Alessi]

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

[Marc'Antonio Alessi]

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

[domenicomaria]

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

[VovKa]

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

[Marc'Antonio Alessi]

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

[Marc'Antonio Alessi]

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>

[Marc'Antonio Alessi]

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

[domenicomaria]

(: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 ! 
...

[domenicomaria]

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?

[domenicomaria]

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

[VovKa]

why do you use vl-position?

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

[domenicomaria]

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]

1. (defun vk_RemoveDupl
2.                                                         (InList / OutList First)
3.         (while InList
4.                 (setq   First     (car InList)
5.                                 InList  (cdr InList)
6.                                 OutList (cons First OutList)
7.                 )
8.                 (if (vl-position First InList)
9.                         (setq InList (vl-remove First InList))
10.                 )
11.         )
12.         (reverse OutList)
13. )
14.  
15. . . . . .
16.  
17. (defun vk_RemoveDupl_2
18.                                                           (InList / OutList First)
19.         (while InList
20.                 (setq   First     (car InList)
21.                                 InList  (cdr InList)
22.                                 OutList (cons First OutList)
23.                 )
24.                 (setq InList (vl-remove First InList))
25.         )
26.         (reverse OutList)
27. )
28.  

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

[VovKa]

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

[ribarm]

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]

1. (setq lst '("box1" "box1" "box1" "box2" "box2" "box3" "box3"))
2. (defun mr_RemoveDupl (InList fuzz)
3.   (vl-remove-if-not
4.     (function
5.       (lambda ( x )
6.         (if
7.           (vl-some
8.             (function
9.               (lambda ( y )
10.                 (equal x y fuzz)
11.               )
12.             ) InList
13.           )
14.           (progn
15.             (setq InList
16.               (vl-remove-if
17.                 (function
18.                   (lambda ( y )
19.                     (equal x y fuzz)
20.                   )
21.                 ) InList
22.               )
23.             )
24.             x
25.           )
26.         )
27.       )
28.     ) InList
29.   )
30. )
31. (mr_RemoveDupl lst 0) => ("box1" "box2" "box3")
32.  

This one is for benchmark testing :

Code - Auto/Visual Lisp: [Select]

1. (setq lst '("box1" "box1" "box1" "box2" "box2" "box3" "box3"))
2. (defun mr_RemoveDupl (InList fuzz / x r )
3.   (while (setq x (car InList))
4.     (setq InList
5.       (vl-remove-if
6.         (function
7.           (lambda ( y )
8.             (equal x y fuzz)
9.           )
10.         ) InList
11.       )
12.     )
13.     (setq r (append r (list x)))
14.   )
15. )
16. (mr_RemoveDupl lst 0) => ("box1" "box2" "box3")
17.