Given 2 lists Olist and Clist. I want to remove items that appears in
both list. How best to do this?
Say,
(setq Olist (list "a" "b" "c" "d" "e"))
(setq Clist (list "ee" "a" "d" "c" "bb"))
i want the result to be like
(setq Olist (list "b" "e"))
(setq Clist (list "ee" "bb"))
order doesn't matter.
i think i can go thru each element and build OlistNew, and removing
Clist to build a ClistNew. But the checking existance and building
item by item would be difficult or very inefficient i think but am not
sure about lisp here.
should i turn them both into hash table first for easy checking
existance?
Thanks.
Xah
∑ http://xahlee.org/
☄
Posted to too many groups by mistake. Sorry. Fixed follow up to just
lisp and emacs.
On Jul 20, 7:14 am, ·······@gmail.com" <······@gmail.com> wrote:
> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))
>
> order doesn't matter.
>
> i think i can go thru each element and build OlistNew, and removing
> Clist to build a ClistNew. But the checking existance and building
> item by item would be difficult or very inefficient i think but am not
> sure about lisp here.
>
> should i turn them both into hash table first for easy checking
> existance?
>
> Thanks.
>
> Xah
> ∑http://xahlee.org/
>
> ☄
On 20 Jul., 16:14, ·······@gmail.com" <······@gmail.com> wrote:
> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))
>
> order doesn't matter.
>
> i think i can go thru each element and build OlistNew, and removing
> Clist to build a ClistNew. But the checking existance and building
> item by item would be difficult or very inefficient i think but am not
> sure about lisp here.
>
> should i turn them both into hash table first for easy checking
> existance?
>
> Thanks.
>
> Xah
> ∑http://xahlee.org/
>
> ☄
In Common Lisp:
CL-USER 4 > (let* ((Olist (list "a" "b" "c" "d" "e"))
(Clist (list "ee" "a" "d" "c" "bb"))
(i (intersection Olist Clist :test #'equal)))
(setf Olist (set-difference Olist i :test #'equal)
Clist (set-difference Clist i :test #'equal))
(values Olist Clist i))
("e" "b")
("bb" "ee")
("d" "c" "a")
From: Kent M Pitman
Subject: Re: remove items appearing in both lists
Date:
Message-ID: <uk5fgbl26.fsf@nhplace.com>
[ comp.lang.lisp only; http://www.nhplace.com/kent/PFAQ/cross-posting.html
Besides, the answer would be different in different dialects of Lisp,
so someone on comp.emacs can answer separately for that dialect. ]
·······@gmail.com" <······@gmail.com> writes:
> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))
>
> order doesn't matter.
(psetq Olist (set-difference Olist Clist :test #'string=)
Clist (set-difference Clist Olist :test #'string=))
Order of the results is indeed not guaranteed. e.g.,
Olist => ("e" "b")
Clist => ("bb" "ee")
in the implementation I used.
> i think i can go thru each element and build OlistNew, and removing
> Clist to build a ClistNew. But the checking existance and building
> item by item would be difficult or very inefficient i think but am not
> sure about lisp here.
Although I made the technical suggestion one day at a committee
meeting during the design of ANSI CL that we should think about
specifying the algorithmic complexity of some of the operations,
that idea was not taken seriously and so the operations in general
do not say how fast they should be.
Implementations are certainly capable of recognizing particular
predicates and optimizing the search by using hash tables so they
don't have to use linear lookup, though in general, without a lot
of serious thought that I haven't done, I don't see how you can do
better with a pre-packaged SET-DIFFERENCE predicate that takes an
arbitrary test than doing O(n^2) comparisons because in general
making a hash table on an arbitrary opaque predicate is hard.
Presumably implementations optimize at least EQ and EQL tests, but
I don't know how many other tests they do. It probably varies.
The basic loop in CL that does what you want, though, is:
(let ((table (make-hash-table :test your-predicate-here)))
(dolist (element elements)
(setf (gethash element table) t))
(loop for element in set
unless (gethash element table) collect element))
That's not super-painful, I think. It will return the elements in possibly
different order, of course.
> should i turn them both into hash table first for easy checking
> existance?
I might suggest just calling set-difference with EQUAL as the predicate
instead of with STRING=.
But it depends on how portable you want to be, how reliably
algorithmically fast you want to be, how big your data is and whether
it can grow or is fixed size (i.e., whether algorithmic complexity
even matters, given that for many applications, the constant factors
will overwhelm matters)
> Thanks.
>
> Xah
Happy to help.
From: Jon Harrop
Subject: Re: remove items appearing in both lists
Date:
Message-ID: <g64gan$n8d$2@aioe.org>
······@gmail.com wrote:
> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))
>
> order doesn't matter.
In F#, convert the lists to sets and use set theoretic operations:
let Olist, Clist = set Olist, set Clist
let union = Olist + Clist
let Olist, Clist = Olist - union, Clist - union
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com/products/?u
> In F#, convert the lists to sets and use set theoretic operations:
>
> let Olist, Clist = set Olist, set Clist
> let union = Olist + Clist
> let Olist, Clist = Olist - union, Clist - union
I guess one would have to write code to marshall the Lisp objects to F#,
call this nice code that Dr.Jon Harrop posted (off course first you have
to buy Windows), and then it'll marshall the objects back so the Common
Lisp code can use them.
Sounds like a great plan!
And a win for the Democracy!
On Jul 22, 9:55 pm, "Dimiter \"malkia\" Stanev" <······@gmail.com>
wrote:
> > In F#, convert the lists to sets and use set theoretic operations:
>
> > let Olist, Clist = set Olist, set Clist
> > let union = Olist + Clist
> > let Olist, Clist = Olist - union, Clist - union
>
> I guess one would have to write code to marshall the Lisp objects to F#,
> call this nice code that Dr.Jon Harrop posted (off course first you have
> to buy Windows), and then it'll marshall the objects back so the Common
> Lisp code can use them.
>
> Sounds like a great plan!
>
> And a win for the Democracy!
You don't really have to buy Windows because F# will probably run on
top of Mono. You just have to buy Harrop's books and his priceless
advices about how static typing and pattern matching will set you
free :)
(No disrespect intended Dr. Harrop, but I see a "pattern" here)
Rainer Joswig and Kent Pitman suggested the Common Lisp solution:
(psetq Olist (set-difference Olist Clist :test #'string=)
Clist (set-difference Clist Olist :test #'string=))
Thanks to Rainer Joswig and Kent Pitman.
Jon Harrop wrote:
> In F#, convert the lists to sets and use set theoretic operations:
>
> let Olist, Clist = set Olist, set Clist
> let union = Olist + Clist
> let Olist, Clist = Olist - union, Clist - union
O, great. In Mathematica.
olist = {"a", "b", "c", "d", "e"};
clist = {"ee", "a", "d", "c", "bb"};
olist = Complement[olist, clist]
clist = Complement[clist, olist]
btw, if i'm curious and want to have a peek of docs of Caml or F# now
and then, is there a easy to use website?
--------------------------------------
David Kastrup offered a pure elisp solution:
David wrote:
«
(setq Olist (sort Olist 'string<) Clist (sort Clist 'string<))
(let (outolist outclist)
(while (and Olist Clist)
(cond ((string= (car Olist) (car Clist))
(pop Olist) (pop Clist))
((string< (car Olist) (car Clist))
(push (pop Olist) outolist))
(t (push (pop Clist) (outclist)))))
(setq Olist (nconc (nreverse outolist) Olist)
Clist (nconc (nreverse outclist) Clist)))
Untested, of course. But something like that should work.
»
Will there be a day when emacs lisp incorporate many of CL's highlevel
list manipulation functions? I think there's controversy... especially
adding CL's more complex features, but i think just adding highlevel
functions is very beneficial.
Xah
∑ http://xahlee.org/
☄
On Jul 22, 4:29 am, Jon Harrop <····@ffconsultancy.com> wrote:
> ······@gmail.com wrote:
> > Given 2 lists Olist and Clist. I want to remove items that appears in
> > both list. How best to do this?
>
> > Say,
>
> > (setq Olist (list "a" "b" "c" "d" "e"))
> > (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> > i want the result to be like
>
> > (setq Olist (list "b" "e"))
> > (setq Clist (list "ee" "bb"))
>
> > order doesn't matter.
>
> In F#, convert the lists to sets and use set theoretic operations:
>
> let Olist, Clist = set Olist, set Clist
> let union = Olist + Clist
> let Olist, Clist = Olist - union, Clist - union
>
> --
> Dr Jon D Harrop, Flying Frog Consultancyhttp://www.ffconsultancy.com/products/?u
On Jul 22, 11:33 pm, ·······@gmail.com" <······@gmail.com> wrote:
> Rainer Joswig and Kent Pitman suggested the Common Lisp solution:
>
> (psetq Olist (set-difference Olist Clist :test #'string=)
> Clist (set-difference Clist Olist :test #'string=))
>
> Thanks to Rainer Joswig and Kent Pitman.
:-)
> Will there be a day when emacs lisp incorporate many of CL's highlevel
> list manipulation functions? I think there's controversy... especially
> adding CL's more complex features, but i think just adding highlevel
> functions is very beneficial.
That day was already long ago. Emacs comes with a Common Lisp
extension:
This is the Emacs Lisp REPL: M-x ielm
*** Welcome to IELM *** Type (describe-mode) for help.
ELISP> (require 'cl)
cl
ELISP> (intersection '(a b c d) '( t u b d))
(d b)
ELISP> (intersection '("A" "a" "b") '("a") :test #'equal)
("a")
ELISP> (set-difference '(a b c d) '(a b f g))
(d c)
On Jul 22, 10:33 pm, ·······@gmail.com" <······@gmail.com> wrote:
> O, great. In Mathematica.
>
> olist = {"a", "b", "c", "d", "e"};
> clist = {"ee", "a", "d", "c", "bb"};
>
> olist = Complement[olist, clist]
> clist = Complement[clist, olist]
Sorry, my F# code was wrong. It should have been:
let olist = set ["a"; "b"; "c"; "d"; "e"]
let clist = set ["ee"; "a"; "d"; "c"; "bb"]
let olist, clist = olist - clist, clist - olist
> btw, if i'm curious and want to have a peek of docs of Caml or F# now
> and then, is there a easy to use website?
There is a site running OCamlJava somewhere but it is not the real
OCaml implementation (e.g. no tail calls).
Easiest to "apt-get install ocaml" under Linux or install Visual
Studio Shell and the F# distribution under Windows.
Cheers,
Jon Harrop.
·······@gmail.com" <······@gmail.com> writes:
> Rainer Joswig and Kent Pitman suggested the Common Lisp solution:
>
> (psetq Olist (set-difference Olist Clist :test #'string=)
> Clist (set-difference Clist Olist :test #'string=))
>
> Thanks to Rainer Joswig and Kent Pitman.
>
> Jon Harrop wrote:
>
>> In F#, convert the lists to sets and use set theoretic operations:
>>
>> let Olist, Clist = set Olist, set Clist
>> let union = Olist + Clist
>> let Olist, Clist = Olist - union, Clist - union
>
> O, great. In Mathematica.
>
> olist = {"a", "b", "c", "d", "e"};
> clist = {"ee", "a", "d", "c", "bb"};
>
> olist = Complement[olist, clist]
> clist = Complement[clist, olist]
>
> btw, if i'm curious and want to have a peek of docs of Caml or F# now
> and then, is there a easy to use website?
>
> --------------------------------------
> David Kastrup offered a pure elisp solution:
>
> David wrote:
>
> �
> (setq Olist (sort Olist 'string<) Clist (sort Clist 'string<))
> (let (outolist outclist)
> (while (and Olist Clist)
> (cond ((string= (car Olist) (car Clist))
> (pop Olist) (pop Clist))
> ((string< (car Olist) (car Clist))
> (push (pop Olist) outolist))
> (t (push (pop Clist) (outclist)))))
> (setq Olist (nconc (nreverse outolist) Olist)
> Clist (nconc (nreverse outclist) Clist)))
>
> Untested, of course. But something like that should work.
> �
Uh, it might be worth to add that only the last, explicit solution is
guaranteed to be O(n lg n), efficient.
The Common Lisp solution that you are clamoring for most certainly
_isn't_ O(n lg n) but rather O(n^2). The same likely holds for the
other "elegant" solutions based on a set abstraction. You can at best
have O(n^2) behavior without making use of an order relation, because
then you are reduced to comparing everything with everything.
If we are not talking about similarly sized sets, the "elegant"
solutions are O(m n), and the one using sorting is O(n lg n + m lg m).
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
On Jul 23, 7:49 am, David Kastrup <····@gnu.org> wrote:
> Uh, it might be worth to add that only the last, explicit solution is
> guaranteed to be O(n lg n), efficient.
>
> The Common Lisp solution that you are clamoring for most certainly
> _isn't_ O(n lg n) but rather O(n^2). The same likely holds for the
> other "elegant" solutions based on a set abstraction...
Both the OCaml and the F# are already asymptotically efficient (at
least as good as O(n log n)) because very efficient set
implementations are provided in their standard libraries. In
Mathematica 6, sets are also efficient.
Cheers,
Jon.
P� Wed, 23 Jul 2008 08:49:03 +0200, skrev David Kastrup <···@gnu.org>:
>
> The Common Lisp solution that you are clamoring for most certainly
> _isn't_ O(n lg n) but rather O(n^2). The same likely holds for the
> other "elegant" solutions based on a set abstraction. You can at best
> have O(n^2) behavior without making use of an order relation, because
> then you are reduced to comparing everything with everything.
>
> If we are not talking about similarly sized sets, the "elegant"
> solutions are O(m n), and the one using sorting is O(n lg n + m lg m).
>
Not entirely true.
You could store one set in a hash table without making assumptions about
order.
Then you have k * n complexity. I believe SBCL does this for large lists.
K here is a high number so for small lists the approach above is still
better.
As for order. Well if they are in order it is a merge or order n.
There is no reason you couldn't keep the set in order. (And sort it at
compile time if the elements are known in advance.)
Thus you can do better than that.
--------------
John Thingstad
"John Thingstad" <·······@online.no> writes:
> P� Wed, 23 Jul 2008 08:49:03 +0200, skrev David Kastrup <···@gnu.org>:
>
>>
>> The Common Lisp solution that you are clamoring for most certainly
>> _isn't_ O(n lg n) but rather O(n^2). The same likely holds for the
>> other "elegant" solutions based on a set abstraction. You can at best
>> have O(n^2) behavior without making use of an order relation, because
>> then you are reduced to comparing everything with everything.
>>
>> If we are not talking about similarly sized sets, the "elegant"
>> solutions are O(m n), and the one using sorting is O(n lg n + m lg m).
>>
>
> Not entirely true.
> You could store one set in a hash table without making assumptions
> about order.
Hash codes _provide_ an order relation.
> As for order. Well if they are in order it is a merge or order n.
> There is no reason you couldn't keep the set in order.
_Keeping_ in order is usually more expensive than bothering about order
only when it is needed.
> (And sort it at compile time if the elements are known in advance.)
> Thus you can do better than that.
You _are_ aware that the code I posted starts by a sort on both lists,
and returns an ordered list?
So if your data is in order, the code is trivial to change in order to
make use of that. Just throw out the initial calls to sort.
--
David Kastrup
On 2008-07-20, ······@gmail.com <······@gmail.com> wrote:
> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))
Since you're assigning to variables, wouldn't this be off-topic in
comp.lang.functional? :)
> order doesn't matter.
;; items common to both sets
(intersection '("a" "b" "c") '("b" "c" "d") :test #'equal)
-> ("b" "c")
;; items in the left set which are not in the right set
(set-difference '("a" "b" "c") '("b" "c" "d") :test #'equal)
-> ("a")
You want to remove (via set-difference) from each original list the
intersection of those two lists:
On Sun, 20 Jul 2008 07:14:51 -0700 (PDT), ·······@gmail.com" <······@gmail.com> said:
| Given 2 lists Olist and Clist. I want to remove items that appears in
| both list.
And in case one wants the remaining items in one place [*], one
may call SET-EXCLUSIVE-OR.
[*] what I thought at first when I read the opening paragraph
See also Scott Burson's FSet Functional Collections Libraries
<http://common-lisp.net/project/fset/>,
<http://common-lisp.net/project/fset/Site/index.html>.
| ...
| (setq Olist (list "a" "b" "c" "d" "e"))
| (setq Clist (list "ee" "a" "d" "c" "bb"))
By the way, arguably symbols, rather than strings, should make up
the "native" lisp _example_ (for serious applications Kent Pitman's
notes apply).
---Vassil.
--
Peius melius est. ---Ricardus Gabriel.