Hi,
I have very big (?) question.
I don't konw how to remove duplicated string
For example,
(remove-duplicates '("a" "a" "a" "b" "c"))
I expect to have this result. ----> ("a" "b" "c")
Please solve my touble and send me your solution.
Thanks,
Dae-won
My Blue Heaven!
From: Christopher N. Vogt
Subject: Re: [Q] HELP: Remove-Duplicates!
Date:
Message-ID: <344631E1.9F47CF0F@home.com>
Dae-Won Lim wrote:
>
> Hi,
> I have very big (?) question.
>
> I don't konw how to remove duplicated string
> For example,
>
> (remove-duplicates '("a" "a" "a" "b" "c"))
>
> I expect to have this result. ----> ("a" "b" "c")
>
> Please solve my touble and send me your solution.
remove-duplicates, like most of the sequence operations,
takes a keyword argument :test and the default test is #'eq.
In order for remove-duplicates to work as you would like,
you need to supply the :test keyword argument with #'equal (or
maybe #'string-equal or maybe #'string=) e.g.
(remove-duplicates '("a" "a" "a" "b" "c") :test #'string-equal)
In article <·················@daelimen.co.kr>,
Dae-Won Lim <·····@daelimen.co.kr> wrote:
>I don't konw how to remove duplicated string
>For example,
>
> (remove-duplicates '("a" "a" "a" "b" "c"))
>
>I expect to have this result. ----> ("a" "b" "c")
Hint: the default comparison function is EQL. What's the result of
(eql "a" "a")
? What comparison function will cause the result you want?
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.
I am actually working on the same problem but I don't have a lisp
interpereter at home to test out my solution. I figured you could do it
without any tests but instead as follows:
(defun remove-duplicates (lst)
(reverse (mapcar #'(lambda (elem) (cons elem (remove elem lst)) lst)))
I think this would work but then again I am new to LISP but perhaps this is
an awkward solution. If anybody knows where I could down load a free lisp
interpereter for a Windows machine I would appreciate it.
Thanks,
Dan Balis
·······@vaxsar.vassar.edu
"Dan" <·······@vaxsar.vassar.edu> writes:
>
> I am actually working on the same problem but I don't have a lisp
> interpereter at home to test out my solution. I figured you could do it
> without any tests but instead as follows:
~~~~~~~~~~~~~~~~~
Except that the REMOVE function uses tests internally. That is why, for
example, it accepts the :TEST keyword -- to allow you to specify a test
other than the default EQL test to use for comparing elements.
> (defun remove-duplicates (lst)
> (reverse (mapcar #'(lambda (elem) (cons elem (remove elem lst)) lst)))
>
> I think this would work but then again I am new to LISP but perhaps this is
> an awkward solution. If anybody knows where I could down load a free lisp
> interpereter for a Windows machine I would appreciate it.
I think that this program will have a few problems:
First off, mapcar applies the function to each element of a list and it
then collects the results of each such function application into a
list. So for the simple case of applying your function to
Let f = #'(lambda (elem) (cons elem (remove elem lst)))
'(a a b a b)
you would get the equivalent of
(list (f a) (f a) (f b) (f a) (f b))
=>
(list (a b b) (a b b) (b a a a) (a b b) (b a a a))
Which is probably not what you would want. A couple alternatives that
use things like your solution do come to mind. For example:
Recursive:
(defun recursive-remove-duplicates (lst)
(if (null lst)
nil
(cons (first lst)
(recursive-remove-duplicates (remove (first lst) lst)))))
This is an N^2 algorithm because it will call REMOVE (which is O(N)), N
times. It will also cons up a storm, since the calls to remove will
have to generate new list structure. I woudn't recommend it for
production code. A recursive solution that uses something like PUSHNEW
and a value accumulating argument would be an improvement on the
consing.
Mapping:
(defun mapping-remove-duplicates (lst)
(mapc #'(lambda (elem) (setf lst (cons elem (remove elem lst))))
lst)
lst)
Again this is an N^2 algorithm since it will call REMOVE N times. It
also has the (to my opinion) extremely distasteful feature of having
side-effects in the mapped function that affect the structure being
mapped over.
Our experience is that the built-in remove-duplicates code in most lisp
implementation uses an O(N^2) algorithm for duplicate removal. For large
lists this gets to be a real performance bottleneck, so we ended up
implementing our own fast-remove-duplicates using hashtables. Since we
weren't concerned about preserving the original order, this allowed a
fairly simple O(N) algorithm. Actually, one that preserved order
wouldn't actually be particularly difficult to write either...
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu