Topic: Remove duplicate Strings in List

[Kerry]

Remove duplicate Strings in List

Anyone have any alternatives to these ??

(setq full_list  (list "c" "a" "b"  "a" "d" "b" "c" "e"))

( RemoveDuplicateStrings full_list) ;;->> ("c" "a" "b" "d" "e")
( SortAndRemoveDuplicateStrings full_list) ;;->> ("a" "b" "c" "d" "e")
;;option
(vl-sort ( RemoveDuplicateStrings full_list) '<)  ;;->> ("a" "b" "c" "d" "e")

Code: [Select]


(defun SortAndRemoveDuplicateStrings (stringlist / newlist lastin)
  ;;kwb 20050221
  (foreach var (vl-sort stringlist '<)
    (if (/= var lastin)
      (setq newlist (cons (setq lastin var) newlist))
    )
  )
  (reverse newlist)
)


(defun RemoveDuplicateStrings (stringlist / newlist)
  ;;kwb 20050221
  (foreach var stringlist
    (if (not (vl-position var newlist))
      (setq newlist (cons var newlist))
    )
  )
  (reverse newlist)
)

I'm brain dead, and would appreciate any insight ..
.. probably time for MP's benchmarker too.

[CAB]

Here is an alternate 'Remove Duplicates'
Did not record the author

Code: [Select]

;---Remove Duplicate members from a list.
;   Given list = '(1 1 2 3 4 "a" "b" "a")
;   Returns '(1 2 3 4 "a" "b")
(defun Remove_Dup (LST / CL)
  (mapcar
    '(lambda (X)
      (cond
        ( (member X LST)
          (cond
            ( (not (member X CL))     ;if element not already in CL
              (setq CL (cons X CL))
            )
          ) ; end cond.
        )
      ) ; end cond.
    ) ;end lambda
    LST
  ) ; end mapcar
  (reverse CL)
) ;end defun


[CAB]

Perhaps it could be simplied to this:

Code: [Select]

(defun remove_dup (lst / cl)
  (mapcar
    '(lambda (x)
       (if (not (member x cl)) ;if element not already in CL
         (setq cl (cons x cl))
       )
     )
    lst
  )
  (reverse cl)
) ;end defun
Which is what you have

[Kerry]

Not quite what I have.

CAB, This will rock you a little perhaps   < or not >  ...
The REMOVE_DUP2  is the same as yours, with the MEMBER changed to VL-POSITION.
.. so the difference will be in the MAPCAR and LAMBDA where I used FOREACH

The test list was a list of duplicate DWG name strings [  2 instances of 25  for a total of 50 ]

Code: [Select]


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

    (REMOVE_DUP FULL_LIST).................5938 / 3.1203 <slowest>
    (REMOVE_DUP2 FULL_LIST)................4236 / 2.2260
    (REMOVEDUPLICATESTRINGS FULL_LIST).....1903 / 1.0000 <fastest>

[JohnK]

So what your saying is that Mapcar is slower.

[Kerry]

uhmmmmm ..

I'm just looking at the numbers Se7en.

[Kerry]

Oh, and Michael .. I flipped the report list around on my benchmark version so that the fastest was the lowest ratio .. and the slowest shows the larger number < elapsed time >.

[CAB]

No it doesn't rock me. I was just providing an alternative which I found somewhere else.
When I removed some of the code it looked similar to yours but using the mapcar / lambda
as you pointed out. I didn't think it would out preform yours because you obviously were
proud enough to put you name in the code. I just offered it up as food for thought as you
said "I'm brain dead, and would appreciate any insight .."
Sorry it wasn't what you were looking for.

[JohnK]

Well your right in this instance.

Mapcar is recursive by nature, foreach isnt. Therefore every time you are using a mapcar+lambda you are waiting for the intrip. to add a function definition to the stack.

[Kerry]

Hi CAB.

Wasn't dissing you  
 ... or the routine

and I was seriously looking for feedback, not a pat on the back.

The problem is sometimes I get my head burried in code and miss the 'obvious' alternatives, hence the post.

[JohnK]

Kerry, run this with the same paramaters as before and cross your fingers. I want to see if we can speed up this process a bit.

Code: [Select]

(defun remove_dup (lst / cl)
   (defun workhorse (x)
     (if (not (member x cl)) ;if element not already in CL
       (setq cl (cons x cl))))
  (mapcar 'workhorse lst)
  (reverse cl)
 )

[Kerry]

Wrapping it like that doesn't help, sorry.

Code: [Select]

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

    (REMOVE_DUP FULL_LIST).................5978 / 3.0609 <slowest>
    (REMOVE_DUP2 FULL_LIST)................4347 / 2.2258
    (REMOVE_DUP_Se7en FULL_LIST)...........3765 / 1.9278
    (REMOVEDUPLICATESTRINGS FULL_LIST).....1953 / 1.0000 <fastest>

[MP]

Compare the performance of this --

Code: [Select]

(defun RemoveDuplicates ( lst / temp )
    (vl-remove-if
       '(lambda (x)
            (cond
                ((vl-position x temp) t)
                ((setq temp (cons x temp)) nil)
            )
        )
        lst
    )
)
Against preceeding variants using this list --

Code: [Select]

(setq lst '(1 2 3 4 5 6 7 8))
(repeat 10
    (setq lst
        (append lst lst)
    )
)
Also (Kerry) please tell me about the speedometer in your vehicle.

[MP]

Even more amusing is the performance of this --

Code: [Select]

(defun RemoveDuplicates ( lst / foo temp )
    (defun foo (x)
        (cond
            ((vl-position x temp) t)
            ((setq temp (cons x temp)) nil)
        )
    )
    (vl-remove-if
       'foo
        lst
    )
)

[JohnK]

Code: [Select]

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

    (REMOVE_DUP FULL_LIST).................5938 / 3.1203 <slowest>
    (REMOVE_DUP2 FULL_LIST)................4236 / 2.2260
    (REMOVEDUPLICATESTRINGS FULL_LIST).....1903 / 1.0000 <fastest>

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

    (REMOVE_DUP FULL_LIST).................5978 / 3.0609 <slowest>
    (REMOVE_DUP2 FULL_LIST)................4347 / 2.2258
    (REMOVE_DUP_Se7en FULL_LIST)...........3765 / 1.9278
    (REMOVEDUPLICATESTRINGS FULL_LIST).....1953 / 1.0000 <fastest>

But it looks like it did. If I'm reading your benchmark correct. I imporved the preformance of the procedure by over 60% by just changing one thing. (using a NAMED procedure instead of an UNNAMED.) Am i right?