Stats

  • Locked Locked
  • Replies 9
  • Subscribers 145
  • Views 20795
  • Members are here 0
This discussion has been locked.
You can no longer post new replies to this discussion. If you have a question you can start a new discussion

Remove duplicates from a list

tweeks

Just wanted to share my solution to this common problem. 

(defun nub (l "l")
  (let ((table (makeTable "" nil)))
    (foreach e l table[e] = t)
    table->?))

Output: 

(nub (parseString "Banana Rama" "")) => ("a" "m" "n" "R" "B" " ")

This assumes order doesn't matter. If order does matter (and efficiency doesn't...), you could use this O(n^2) version, which is a literal translation of the one in the Haskell Data.List library:

(defun nub (l "l")
  (defun _nub (xs ls "ll")
    (unless (null xs)
      (destructuringBind (x @rest xs) xs
        (if (member x ls)
            (_nub xs ls)
          (cons x (_nub xs (cons x ls)))))))
  (_nub l nil))

Output: 

(nub (parseString "Banana Rama" "")) => ("B" "a" "n" " " "R" "m")

If you want to preserve order and get O(n) performance, you could modify the last version to use a table instead of a list: 

(defun nub (l "l")
  (defun _nub (xs ls "lo")
    (unless (null xs)
      (destructuringBind (x @rest xs) xs
        (if (ls[x])
            (_nub xs ls)
          (cons x (_nub xs (ls[x] = t && ls)))))))
  (_nub l (makeTable "" nil)))

Output: 

(nub (parseString "Banana Rama" "")) => ("B" "a" "n" " " "R" "m")

  • Nice writeup.

    I was once shown a varient of this method to remove duplicates

    (defun nub (l_list)
      (let ( (l_unique (list nil)) g_first)    
        (while l_list            
          g_first = (car l_list)
          (tconc l_unique g_first)
          l_list=(remove g_first l_list)
        ) ; while
        (car l_unique)
      ); let
    ); defun    

    (nub (parseString "Banana Rama" ""))
    => ("B" "a" "n" " " "R"  "m")

    The nice thing about this method is that it works for large lists and preserves order (whereas your table version gave me a stack overflow with a large list).  That said, the first method you outlined has about 4X the performance of my method.  So if order is not important, your first method is the best way I've seen. Nice work!

    Mark

  • i made a procedure to remove duplicates from an actual list.

    procedure(filterRepeatedLayers(aList)  

    println(aList)
    if(car(aList) != cadr(aList) && aList != nil then
    ncons(car(aList))
    filterRepeatedLayers(copy(cdr(aList)))

    else if(car(aList) == cadr(aList) && aList != nil then
    ncons(cadr(aList))
    filterRepeatedLayers(copy(cddr(aList)))
       )
      )
     )

    however, when i invoke

    a = filterRepeatedLayers('("M1" "M2" "M2"))

    i get a = nil instead of a = '("M1" "M2")

  • In the Allegro world we have a newish command called "unique". Is this available to you?

  • i checked the manuals, and it doesn't have this function

  •  Hi Dave,

     I am not finding this command 'unique' in skill language reference manual.

    Is this removed?

    I need this in Allegro.

    Thanks,

    Nagaraj.

  • I can't answer about what's in Allegro, but it's easy to implement your own as shown in the original thread. Another implementation 

    (defun MyUnique (lst)
      (let ((seen (makeTable 'seen nil)))
        (setof elem lst
          (unless (arrayref seen elem)
            (setarray seen elem t)
          )
        )
      )
    )

    This preserves the order, isn't recursive so it's probably a little faster than final nub implementation (I didn't profile it, so take that with a pinch of salt). For the hard-of-LISP, it could be written:

    procedure(MyUnique(lst)
      let(((seen makeTable('seen nil)))
        setof(elem lst
          unless(seen[elem]
            seen[elem]=t
          )
        )
      )
    )

    So it's easy enough to write yourself!

    Andrew.

  • It's undocumented. Give it a try.
  • in reply to eDave

    its working fine . Thanks 


    ciUniqueMembers( list(list("MN3" `inst ) list("MN4" `inst ) list("MN3" `inst ) list("VEl" `name )) 

    list must have name and type if we use ciUniqureMembers

Community Guidelines

The Cadence Design Communities support Cadence users and technologists interacting to exchange ideas, news, technical information, and best practices to solve problems and get the most from Cadence technology. The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information. By accessing, contributing, using or downloading any materials from the site, you agree to be bound by the full Community Guidelines.