From: Hu Chengjun
Subject: Re: Looking for LISP source codes for sets manipulations
Date:
Message-ID: <34DE602C.1E5A27B0@iist.unu.edu>
David J Cooper Jr wrote:
>>
>
> Is there something wrong with your CL's implementation of union,
> intersection, set-difference, member, etc?
>
> --
> David J. Cooper Jr. Genworks International
> ········@genworks.com http://www.genworks.com
>
> "...Embracing an Open Systems approach to Knowledge-based Engineering..."
>
>
There's nothing wrong with my CL's implementation of union,
intersection,
etc. I knew that in CL we could use lists as sets. The problem is, since
I am to use
sets frequently, I hope there are some more efficient implementations
for sets,
say using balanced binary trees instead of lists.
From: Pierpaolo Bernardi
Subject: Re: Looking for LISP source codes for sets manipulations
Date:
Message-ID: <6bnfdt$2sq$1@croci.unipi.it>
Hu Chengjun (···@iist.unu.edu) wrote:
: David J Cooper Jr wrote:
: >>
: >
: > Is there something wrong with your CL's implementation of union,
: > intersection, set-difference, member, etc?
: >
: > --
: > David J. Cooper Jr. Genworks International
: > ········@genworks.com http://www.genworks.com
: >
: > "...Embracing an Open Systems approach to Knowledge-based Engineering..."
: >
: >
: There's nothing wrong with my CL's implementation of union,
: intersection,
: etc. I knew that in CL we could use lists as sets. The problem is, since
: I am to use
: sets frequently, I hope there are some more efficient implementations
: for sets,
: say using balanced binary trees instead of lists.
I have ported to CL the implementation of wt-trees which come with
Slib (original author S.J.Adams, IIRC). This library has functions
for all the usual set operations, and I found it quite fast.
Mail me if you want a copy.
Pierpaolo.
········@cli.di.unipi.it (Pierpaolo Bernardi) writes:
> Hu Chengjun (···@iist.unu.edu) wrote:
> : David J Cooper Jr wrote:
>
...
> : I am to use
> : sets frequently, I hope there are some more efficient implementations
> : for sets,
> : say using balanced binary trees instead of lists.
>
>
> I have ported to CL the implementation of wt-trees which come with
> Slib (original author S.J.Adams, IIRC). This library has functions
> for all the usual set operations, and I found it quite fast.
>
> Mail me if you want a copy.
>
The CMU AI.Repository contains an implementation of Red/Black trees
(along with simple and priority queues) straight out of CLR.
You can blame me if they do not work :)
BTW. Pierpaolo, if you have an implementation of the wt-trees, maybe
we could unify the interfaces and come up with a nicer package.
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - (0)6 - 68 80 79 23, fax. +39 - (0)6 - 68 80 79 26
http://www.parades.rm.cnr.it
From: Pierpaolo Bernardi
Subject: Re: Looking for LISP source codes for sets manipulations
Date:
Message-ID: <6bq1ii$7op$1@croci.unipi.it>
Marco Antoniotti (·······@galvani.parades.rm.cnr.it) wrote:
: ········@cli.di.unipi.it (Pierpaolo Bernardi) writes:
: > Hu Chengjun (···@iist.unu.edu) wrote:
: > : David J Cooper Jr wrote:
: > I have ported to CL the implementation of wt-trees which come with
: > Slib (original author S.J.Adams, IIRC). This library has functions
: > for all the usual set operations, and I found it quite fast.
: >
: > Mail me if you want a copy.
: The CMU AI.Repository contains an implementation of Red/Black trees
: (along with simple and priority queues) straight out of CLR.
Noted them. One difference with wt-trees, is that the wt-trees
provide both destructive and non-destructive operations.
For destructive operations, RB were faster, IIRC (sorry, no numbers, I
tested this some time ago).
: BTW. Pierpaolo, if you have an implementation of the wt-trees, maybe
: we could unify the interfaces and come up with a nicer package.
This seems a worthwhile project. I'll send the code to you too, let's
see what we can do.
(To the people which have mailed me to request a copy of the code:
please bear with me. For reasons too messy to describe, I cannot mail
the code today. Maybe tomorrow. (Actually, the reason involves the
lack of a floppy disk driver in the machine I can use today to post
8-( )).
Pierpaolo
From: David J Cooper Jr
Subject: Re: Looking for LISP source codes for sets manipulations
Date:
Message-ID: <34DF4510.ACB8F85C@genworks.com>
--------------6AABB8722A64F857CD6E6482
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Hu Chengjun wrote:
> , since
> I am to use
> sets frequently, I hope there are some more efficient implementations
> for sets,
> say using balanced binary trees instead of lists.
Right. that's what I figured.
I also frequently have a need for ordered set operations (though I know this
violates the textbook definition of sets).
For example, I have a
(set-difference-o (set1 set2 &key (test #'eql) (key #'identity)))
which returns the difference in the same order as they were in set1.
Same thing with intersection-o
Not very efficient though -- if you or somebody comes up with more efficient set
operations, perhaps they could kill two birds with one stone by being efficient
as well as maintaining the ordering, as with my set-difference-o and
intersection-o?
--
David J. Cooper Jr. Genworks International
········@genworks.com http://www.genworks.com
"...Embracing an Open Systems approach to Knowledge-based Engineering..."
--------------6AABB8722A64F857CD6E6482
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<HTML>
Hu Chengjun wrote:
<BLOCKQUOTE TYPE=CITE>, since
<BR>I am to use
<BR>sets frequently, I hope there are some more efficient implementations
<BR>for sets,
<BR>say using balanced binary trees instead of lists.</BLOCKQUOTE>
<BR>Right. that's what I figured.
<P>I also frequently have a need for ordered set operations (though I know
this violates the textbook definition of sets).
<P>For example, I have a
<P>(set-difference-o (set1 set2 &key (test #'eql) (key #'identity)))
<P>which returns the difference in the same order as they were in set1.
<P>Same thing with intersection-o
<P>Not very efficient though -- if you or somebody comes up with more efficient
set operations, perhaps they could kill two birds with one stone by being
efficient as well as maintaining the ordering, as with my set-difference-o
and intersection-o?
<BR>
<PRE>--
David J. Cooper Jr. Genworks International
········@genworks.com <A HREF="http://www.genworks.com">http://www.genworks.com</A>
"...Embracing an Open Systems approach to Knowledge-based Engineering..."</PRE>
</HTML>
--------------6AABB8722A64F857CD6E6482--
In article <·················@genworks.com>, David J Cooper Jr
<········@genworks.com> wrote:
> --------------6AABB8722A64F857CD6E6482
> Content-Type: text/plain; charset=us-ascii
> Content-Transfer-Encoding: 7bit
>
> Hu Chengjun wrote:
>
> > , since
> > I am to use
> > sets frequently, I hope there are some more efficient implementations
> > for sets,
> > say using balanced binary trees instead of lists.
>
>
> Right. that's what I figured.
>
> I also frequently have a need for ordered set operations (though I know this
> violates the textbook definition of sets).
>
> For example, I have a
>
> (set-difference-o (set1 set2 &key (test #'eql) (key #'identity)))
>
> which returns the difference in the same order as they were in set1.
>
> Same thing with intersection-o
>
> Not very efficient though -- if you or somebody comes up with more
efficient set
> operations, perhaps they could kill two birds with one stone by being
efficient
> as well as maintaining the ordering, as with my set-difference-o and
> intersection-o?
The usual inefficient ones:
(defun set-thing-o (set1 set2 test-key &key (test #'eql) (key #'identity))
(unless (and (eq key #'identity) (listp set2))
(setq set2 (map 'list key set2)))
(remove set2 set1 test-key #'(lambda (y x) (member x y :test test))))
(defun set-difference-o (set1 set2 &rest keys)
(apply #'set-thing-o set1 set2 :test keys))
(set-difference '(1 2 3 4 5 6) '(1 3 5 7)) => (6 4 2)
(set-difference-o '(1 2 3 4 5 6) '(1 3 5 7)) => (2 4 6)
(defun intersection-o (set1 set2 &rest keys)
(apply #'set-thing-o set1 set2 :test-not keys))
(intersection '(1 2 3 4 5 6) '(1 3 5 7)) => (5 3 1)
(intersection-o '(1 2 3 4 5 6) '(1 3 5 7)) => (1 3 5)
d
In article <····················@p137.bit-net.com>, ···@flavors.com (David
D. Smith) wrote:
> In article <·················@genworks.com>, David J Cooper Jr
> <········@genworks.com> wrote:
...
> > For example, I have a
> >
> > (set-difference-o (set1 set2 &key (test #'eql) (key #'identity)))
> >
> > which returns the difference in the same order as they were in set1.
> >
> > Same thing with intersection-o
> >
> > Not very efficient though -- if you or somebody comes up with more
> efficient set
...
> The usual inefficient ones:
...
I forgot to apply the KEY to SET1; should be:
(defun set-thing-o (set1 set2 test-key &key (test #'eql) (key #'identity))
(unless (and (eq key #'identity) (listp set2))
(setq set2 (map 'list key set2)))
(remove set2 set1 test-key #'(lambda (y x)
(member (funcall key x) y :test test))))
d