From: Robert Uhl
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <m3ek5z2bb3.fsf@4dv.net>
drewc <·····@rift.com> writes:
>
> This is a _very_ FAQ, so let me summarise the most likely responses:
>
> * Those other languages need so many libraries because they are
> missing functionality that is already included in CL (the cl standard is
> huge, most of it could be considered 'library').
What does CL provide that Python, Java or Perl require libraries for?
It's a serious question, really. CL certain provides a fair amount
those languages _can't_ do (e.g. conditions & restarts, decent macros
&c.). But I'm trying to see what CL provides which they can use
libraries for. Don't know much about Java, but Perl & Python have hash
tables. They have lists/arrays. They have classes (not nearly as nice
as full CLOS, but they can't _do_ full CLOS, even in a library). They
have streams.
No library can provide symbols, or real Lisp-like macros, or a condition
system. At least, my small brain can't think of how to do it.
Now, they could each use a better portable pathname library--that's one
thing I can think of.
A lot of folks think that CL is huge, but I've never really been
convinced. Compared to a language like Perl or Python, it's not much
bigger. Sure, it's larger than C circa 1983, but that's no longer the
state of the art.
Not really picking on you, but I read this a lot (that CL provides as
part of the language what others need libraries for), but I don't think
that this really holds true anymore. Sure, C requires libraries for
lists, sequences, hash tables and objects, but most modern languages
give you those with the base language.
--
Robert Uhl <http://public.xdi.org/=ruhl>
More Slightly Less Common Latin Phrases:
Anulos qui animum ostendunt omnes gestemus!
Let's all wear mood rings!
Just off the top of my head:
* bignums/complex numbers. Python finally has these integrated, but
they're still libraries in Java/Perl
* bit vectors
* rational numbers
* set operations on sequences
You are right, though - the other languages are catching up in terms of
coverage of the features that have reasonable equivalents. Leaving us
to fall back on the unreasonable, unequalled features you mentioned
(symbols, macros, readtables, CLOS, (COMPILE ...)).
Having been forced out into the C++/Java universe recently, I agree
with Kenny's statement about most libraries being crap. Hell is Other
People's Libraries, as far as I'm concerned...
From: Robert Uhl
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <m3d5li1uza.fsf@4dv.net>
"bob_bane" <····@zzapp.org> writes:
> Just off the top of my head:
>
> * bignums/complex numbers. Python finally has these integrated, but
> they're still libraries in Java/Perl
>
> * bit vectors
>
> * rational numbers
>
> * set operations on sequences
Ah, thanks--I'd forgotten those.
> You are right, though - the other languages are catching up in terms
> of coverage of the features that have reasonable equivalents. Leaving
> us to fall back on the unreasonable, unequalled features you mentioned
> (symbols, macros, readtables, CLOS, (COMPILE ...)).
And for a good bit of those, any language which has them is really Lisp
with another syntax, so if a language _does_ get them then it has become
Lisp!
--
Robert Uhl <http://public.xdi.org/=ruhl>
If you stand on your head, you will get footprints in your hair.
Robert Uhl wrote:
> "bob_bane" <····@zzapp.org> writes:
>
> > Just off the top of my head:
> >
> > * bignums/complex numbers. Python finally has these integrated, but
> > they're still libraries in Java/Perl
> >
> > * bit vectors
> >
> > * rational numbers
> >
> > * set operations on sequences
>
> Ah, thanks--I'd forgotten those.
>
> > You are right, though - the other languages are catching up in terms
> > of coverage of the features that have reasonable equivalents. Leaving
> > us to fall back on the unreasonable, unequalled features you mentioned
> > (symbols, macros, readtables, CLOS, (COMPILE ...)).
>
> And for a good bit of those, any language which has them is really Lisp
> with another syntax, so if a language _does_ get them then it has become
> Lisp!
I've been mentioning to people about the Conditions System, so
hopefully people will start agitating for it in their languages. I'm
rather surprised the more well-known pundits don't mention it, in favor
of things like "closures."
Also, I think people are a little impressed by things which
simultaneously update, like the FOR...AND connectives in loop.
Updating a function's definition is surprisingly mystifying to people,
such as in the MEMOIZE function.
Tayssir
From: Rob Warnock
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <7v6dnTerfJOSEvTeRVn-vA@speakeasy.net>
bob_bane <····@zzapp.org> wrote:
+---------------
| * set operations on sequences
+---------------
Uh... Which "set operations on sequences" did you have in mind?
Set operations on *lists*, yes, CL has lots of those. But I don't
see any "set" operations per se in CLHS "17.3 The Sequences Dictionary".
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> bob_bane <····@zzapp.org> wrote:
> +---------------
> | * set operations on sequences
> +---------------
>
> Uh... Which "set operations on sequences" did you have in mind?
> Set operations on *lists*, yes, CL has lots of those. But I don't
> see any "set" operations per se in CLHS "17.3 The Sequences Dictionary".
>
>
You're right, of course. *thwack to side of head*
And I had my ancient and revered copy of CLtL2 open as I wrote that...
- Bob
From: Marco Antoniotti
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <RNKaf.58$pa3.22430@typhoon.nyu.edu>
Rob Warnock wrote:
> bob_bane <····@zzapp.org> wrote:
> +---------------
> | * set operations on sequences
> +---------------
>
> Uh... Which "set operations on sequences" did you have in mind?
> Set operations on *lists*, yes, CL has lots of those. But I don't
> see any "set" operations per se in CLHS "17.3 The Sequences Dictionary".
Not only that. There no guarantee that the operations are efficiently
implemented. I got recently bitten by discovering that INTERSECTION (on
an implementation I won't name) was implemented using the naive
quadratic algorithm.
Cheers
--
Marco
From: Fred Gilham
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <u7r79sm6cg.fsf@snapdragon.csl.sri.com>
Marco Antoniotti <·······@cs.nyu.edu> writes:
> Not only that. There no guarantee that the operations are
> efficiently implemented. I got recently bitten by discovering that
> INTERSECTION (on an implementation I won't name) was implemented
> using the naive quadratic algorithm.
Name it! Name it! Don't protect the guilty!
--
Fred Gilham ······@csl.sri.com
The people who think that the power of big business is enormous are
mistaken...since big business depends entirely on the patronage of
those who buy its products: the biggest enterprise loses its power and
its influence when it loses its customers. -- Ludwig Von Mises
On Mon, 07 Nov 2005 14:38:23 -0800, Fred Gilham wrote:
>
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
>> Not only that. There no guarantee that the operations are
>> efficiently implemented. I got recently bitten by discovering that
>> INTERSECTION (on an implementation I won't name) was implemented
>> using the naive quadratic algorithm.
>
> Name it! Name it! Don't protect the guilty!
Incidentally I wrote my own set intersection a while back, mostly because
I wanted to give it an arbitrary number of sets, but I also believe it's
reasonably fast (assuming hashing isn't too bad).
(defun set-intersection-using-test (test &rest lists)
(let ((n (length lists))
(counts (make-hash-table :test test))
(result nil))
(dolist (list lists result)
(dolist (i list)
(when (= (incf (gethash i counts 0)) n)
(push i result))))))
This looks like O(N) to me (where N is the sum of the sizes of all the
sets). Is this fairly good, or am I missing something better?
Cheers,
Bill.
William Bland wrote:
> Incidentally I wrote my own set intersection a while back, mostly because
> I wanted to give it an arbitrary number of sets, but I also believe it's
> reasonably fast (assuming hashing isn't too bad).
>
> (defun set-intersection-using-test (test &rest lists)
> (let ((n (length lists))
> (counts (make-hash-table :test test))
> (result nil))
> (dolist (list lists result)
> (dolist (i list)
> (when (= (incf (gethash i counts 0)) n)
> (push i result))))))
>
> This looks like O(N) to me (where N is the sum of the sizes of all the
> sets). Is this fairly good, or am I missing something better?
What happens in the situation, where all the elements have the
same hash value?
--
Jens Axel S�gaard
Jens Axel S�gaard wrote:
> What happens in the situation, where all the elements have the
> same hash value?
No two different things ever hash to the same value (when the hash is
being used as an equality test). This is an orthodoxy of practical
computer science (PCS), and SHALL not be questioned. How many millions
of websites would be broken right now if this weren't true?
The beautiful mystery of it all is how these same hashes can be used, in
different algorithms, to map a large number of objects into a small
number of buckets. The computer just seems to KNOW. My bet's on
Intelligent Design.
:-) Seeing statistically broken hash code is a pet peeve of mine, but I
didn't notice this one.
On Wed, 09 Nov 2005 12:51:33 -0500, Cameron MacKinnon wrote:
> Jens Axel S�gaard wrote:
>> What happens in the situation, where all the elements have the
>> same hash value?
The function gets slower as hash collisions increase (approaching
quadratic time, when all elements hash to the same value, if CL
hash-tables are usually implemented the way I think they are).
> No two different things ever hash to the same value (when the hash is
> being used as an equality test). This is an orthodoxy of practical
> computer science (PCS), and SHALL not be questioned. How many millions
> of websites would be broken right now if this weren't true?
>
> The beautiful mystery of it all is how these same hashes can be used, in
> different algorithms, to map a large number of objects into a small
> number of buckets. The computer just seems to KNOW. My bet's on
> Intelligent Design.
>
> :-) Seeing statistically broken hash code is a pet peeve of mine, but I
> didn't notice this one.
Hehe. Yes, I'm aware that one cannot map all the information in the
universe into a single bit ;-)
I'd say it's stretching things rather to say that the code is
"statistically broken" though - it gets slower, but doesn't really "break"
(unless you have a really strict definition of the word "break").
Best wishes,
Bill.
From: Cameron MacKinnon
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <xtmdnQEEVZjI1e_eRVn-vQ@rogers.com>
William Bland wrote:
> On Wed, 09 Nov 2005 12:51:33 -0500, Cameron MacKinnon wrote:
>
>
>>Jens Axel S�gaard wrote:
>>
>>>What happens in the situation, where all the elements have the
>>>same hash value?
>
>
> The function gets slower as hash collisions increase (approaching
> quadratic time, when all elements hash to the same value, if CL
> hash-tables are usually implemented the way I think they are).
>
>>:-) Seeing statistically broken hash code is a pet peeve of mine, but I
>>didn't notice this one.
>
> I'd say it's stretching things rather to say that the code is
> "statistically broken" though - it gets slower, but doesn't really "break"
> (unless you have a really strict definition of the word "break").
My bad. I was confused. Must've been the hash.
Pascal Bourguignon wrote:
> William Bland <···············@gmail.com> writes:
>>On Wed, 09 Nov 2005 12:51:33 -0500, Cameron MacKinnon wrote:
>>>Jens Axel S�gaard wrote:
>>>
>>>>What happens in the situation, where all the elements have the
>>>>same hash value?
>>
>>The function gets slower as hash collisions increase (approaching
>>quadratic time, when all elements hash to the same value, if CL
>>hash-tables are usually implemented the way I think they are).
>
> Not necessarily: the bucket can be held in a balanced binary tree.
> Then you get O(N*log(n)), unless you get the misfortune of having a
> degenerate sequence in each bucket.
A worst case of O(n log(n)) for intersection sounds reasonable.
How expensive is it to create the initial hashtable? For small sets
it might be faster to do the na�ve thing - i.e. sort the lists and
then determine the common elements.
--
Jens Axel S�gaard
From: John Thingstad
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <op.szv9lblapqzri1@mjolner.upc.no>
On Mon, 07 Nov 2005 23:38:23 +0100, Fred Gilham
<······@snapdragon.csl.sri.com> wrote:
>
>
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
>> Not only that. There no guarantee that the operations are
>> efficiently implemented. I got recently bitten by discovering that
>> INTERSECTION (on an implementation I won't name) was implemented
>> using the naive quadratic algorithm.
>
> Name it! Name it! Don't protect the guilty!
>
I had a suspicion.. So I checked out Corman Lisp.
In sys/lists.lisp I found..
(defun intersection (list-1 list-2
&key (key nil)
(test #'eql)
(test-not nil))
(if test-not
(setq test #'(lambda (x y) (not (funcall test-not x y)))))
(let ((newlist nil)
(kx nil))
(dolist (x list-1)
(setq kx (if key (funcall key x) x))
(if (member kx list-2 :test test :key key)
(push x newlist)))
(nreverse newlist)))
dolist + member -- hmm.. looks quadric to me..
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Marco Antoniotti
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <0d3cf.62$pa3.24201@typhoon.nyu.edu>
Fred Gilham wrote:
>
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
>
>>Not only that. There no guarantee that the operations are
>>efficiently implemented. I got recently bitten by discovering that
>>INTERSECTION (on an implementation I won't name) was implemented
>>using the naive quadratic algorithm.
>
>
> Name it! Name it! Don't protect the guilty!
>
Well, I guess there is more than one :) My culprit is LW.
The truth is that, because of the lack of arbitrary :TEST hash tables
you cannot have the spec of work in O(N) expected time. So you have to
revert to a simplified version that supports only the EQ, EQL, EQUAL,
and EQUALP tests.
Cheers
--
Marco
From: John Thingstad
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <op.szxmn0sopqzri1@mjolner.upc.no>
On Tue, 08 Nov 2005 16:09:48 +0100, Marco Antoniotti <·······@cs.nyu.edu>
wrote:
>
>
> Fred Gilham wrote:
>> Marco Antoniotti <·······@cs.nyu.edu> writes:
>>
>>> Not only that. There no guarantee that the operations are
>>> efficiently implemented. I got recently bitten by discovering that
>>> INTERSECTION (on an implementation I won't name) was implemented
>>> using the naive quadratic algorithm.
>> Name it! Name it! Don't protect the guilty!
>>
>
> Well, I guess there is more than one :) My culprit is LW.
>
> The truth is that, because of the lack of arbitrary :TEST hash tables
> you cannot have the spec of work in O(N) expected time. So you have to
> revert to a simplified version that supports only the EQ, EQL, EQUAL,
> and EQUALP tests.
>
> Cheers
> --
> Marco
errm. Actually LW has a extension to make-hash-table that allows
general tests. (Lisp Works Reference Manulal p. 78)
So Bland's algorithm works in general here.
Perhaps a post is in order.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Marco Antoniotti
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <2Q5cf.64$pa3.24274@typhoon.nyu.edu>
John Thingstad wrote:
> On Tue, 08 Nov 2005 16:09:48 +0100, Marco Antoniotti
> <·······@cs.nyu.edu> wrote:
>
>>
>>
>> Fred Gilham wrote:
>>
>>> Marco Antoniotti <·······@cs.nyu.edu> writes:
>>>
>>>> Not only that. There no guarantee that the operations are
>>>> efficiently implemented. I got recently bitten by discovering that
>>>> INTERSECTION (on an implementation I won't name) was implemented
>>>> using the naive quadratic algorithm.
>>>
>>> Name it! Name it! Don't protect the guilty!
>>>
>>
>> Well, I guess there is more than one :) My culprit is LW.
>>
>> The truth is that, because of the lack of arbitrary :TEST hash tables
>> you cannot have the spec of work in O(N) expected time. So you have
>> to revert to a simplified version that supports only the EQ, EQL,
>> EQUAL, and EQUALP tests.
>>
>> Cheers
>> --
>> Marco
>
>
> errm. Actually LW has a extension to make-hash-table that allows
> general tests. (Lisp Works Reference Manulal p. 78)
> So Bland's algorithm works in general here.
> Perhaps a post is in order.
>
Yes. But extended hash table tests are not in the CLHS.
Cheers
--
Marco
From: John Thingstad
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <op.szxphhf3pqzri1@mjolner.upc.no>
On Tue, 08 Nov 2005 19:07:59 +0100, Marco Antoniotti <·······@cs.nyu.edu>
wrote:
>
> Yes. But extended hash table tests are not in the CLHS.
>
> Cheers
> --
> Marco
>
Indeed. I thought it was clear that this optimation is only
general for (intersection <> <> :test <>) in LW.
But since it is LW's library function intersection you
want more efficient...
I think most vendors have extensions and hidden functions that allow
a more efficient implementation while still conforming to CLHS.
Though the creators of this one may have been more interested in
supporting weak pointers (to implement cash'es perhaps) it can
clearly be used in intersection.
It is not entirly obvious (to me) that this optimation pays off in the
average case, however.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Marco Antoniotti
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <oX6cf.66$pa3.24287@typhoon.nyu.edu>
John Thingstad wrote:
> On Tue, 08 Nov 2005 19:07:59 +0100, Marco Antoniotti
> <·······@cs.nyu.edu> wrote:
>
>>
>> Yes. But extended hash table tests are not in the CLHS.
>>
>> Cheers
>> --
>> Marco
>>
>
> Indeed. I thought it was clear that this optimation is only
> general for (intersection <> <> :test <>) in LW.
> But since it is LW's library function intersection you
> want more efficient...
Nope. I want a portable and provably efficient implementation. Hence I
have no choice but roll up my own which takes into account the test.
Incidentally, LW (at least up to 4.3) used the naive quadratic time
algorithm even for lists of symbols with :TEST set to EQ.
> I think most vendors have extensions and hidden functions that allow
> a more efficient implementation while still conforming to CLHS.
You are back to square one. If you want to write a portable interface
you have to check all the implementations.
> Though the creators of this one may have been more interested in
> supporting weak pointers (to implement cash'es perhaps) it can
> clearly be used in intersection.
> It is not entirly obvious (to me) that this optimation pays off in the
> average case, however.
Using a O(N) algorithm to do the intersection is the only optimization
you need. You loose in flexibility, but that is the price to pay for
lack of general hash-table and an EQUALITY generic function hook.
Cheers
--
Marco
Marco Antoniotti wrote:
>
> Nope. I want a portable and provably efficient implementation. Hence I
> have no choice but roll up my own which takes into account the test.
This is a strange approach to take. If I understand correctly, you don't
want any functionality over and above what's specified in the CL spec,
but some implementations are inefficient? Surely the solution is to
complain to the maintainers.
Otherwise, your applications' libraries will soon contain a collection
of ad-hoc, formally specified, bug-ridden implementations of half of
Common Lisp. Not that I'm criticizing your code in particular, but
there's a reason these functions are in the standard. Implementations
should be accretions of bug fixes, rather than bugs (or inefficiencies)
which need to be worked around.
On the specific topic of INTERSECTION, I'd be curious as to how long the
sets need to be to outweigh the rather large (I presume) constant
factors involved in setting up and accessing hashes. Might it not be
quicker when comparing items for which there are also inequality
relations (i.e. <, >) to copy each set to a heap, then extract their
elements in order and cons up the matches? To put it another way, I
think the most efficient algorithm might depend heavily on the set
length and the cost of the comparison and hashing operators. This is
pure speculation on my part. Regardless, naive quadratic probably isn't
in the running very often.
From: Marco Antoniotti
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <Z68cf.67$pa3.24326@typhoon.nyu.edu>
Cameron MacKinnon wrote:
> Marco Antoniotti wrote:
>
>>
>> Nope. I want a portable and provably efficient implementation. Hence
>> I have no choice but roll up my own which takes into account the test.
>
>
> This is a strange approach to take. If I understand correctly, you don't
> want any functionality over and above what's specified in the CL spec,
> but some implementations are inefficient? Surely the solution is to
> complain to the maintainers.
>
> Otherwise, your applications' libraries will soon contain a collection
> of ad-hoc, formally specified, bug-ridden implementations of half of
> Common Lisp. Not that I'm criticizing your code in particular, but
> there's a reason these functions are in the standard. Implementations
> should be accretions of bug fixes, rather than bugs (or inefficiencies)
> which need to be worked around.
Of course. Of course. In my case it was a matter of time. The
turn-around time from the implementors is not necessarily short, plus,
in principle, you may need to complain to all the implementors.
This of course is still short to cast in the stone of a dreamed up
amendment to the ANSI spec that INTERSECTION should provide linear time
complexity at least for the hash table permitted tests.
>
> On the specific topic of INTERSECTION, I'd be curious as to how long the
> sets need to be to outweigh the rather large (I presume) constant
> factors involved in setting up and accessing hashes. Might it not be
> quicker when comparing items for which there are also inequality
> relations (i.e. <, >) to copy each set to a heap, then extract their
> elements in order and cons up the matches? To put it another way, I
> think the most efficient algorithm might depend heavily on the set
> length and the cost of the comparison and hashing operators. This is
> pure speculation on my part. Regardless, naive quadratic probably isn't
> in the running very often.
In my specific case the sets are in the 10^2 size magnitude (and
possibly 10^3), and INTERSECTION is called within a loop. This is
plenty to justify the rewriting. Believe me, I did my homework after
staring in front of the screen waiting for a result.
Cheers
--
Marco
From: John Thingstad
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <op.szxubcuupqzri1@mjolner.upc.no>
On Tue, 08 Nov 2005 20:24:04 +0100, Marco Antoniotti <·······@cs.nyu.edu>
wrote:
> Using a O(N) algorithm to do the intersection is the only optimization
> you need. You loose in flexibility, but that is the price to pay for
> lack of general hash-table and an EQUALITY generic function hook.
>
> Cheers
> --
> Marco
I have to agree with Weitz. On closer thought you would need to get a hash
function to mach the test. A general intersection of O(N) may be
inpractical.
It works fine for the special cases for make-hash-table in CLHS.
What I would do would be to go with the standard function and
then implement your own when better efficiency is needed like
Bland did. The generality of :test is really the culprit here.
(Is this what you are trying to say?)
The only way to do this intersection O(N) that I know either
explicity use a ordering of the list (a set implementation typically
creates this)
or uses hash to make the lookup O(1) this at the price of
a considrable overhead setting it up.
If I am missing something please let me know..
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Marco Antoniotti
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <tl8cf.69$pa3.24091@typhoon.nyu.edu>
John Thingstad wrote:
> On Tue, 08 Nov 2005 20:24:04 +0100, Marco Antoniotti
> <·······@cs.nyu.edu> wrote:
>
>> Using a O(N) algorithm to do the intersection is the only
>> optimization you need. You loose in flexibility, but that is the
>> price to pay for lack of general hash-table and an EQUALITY generic
>> function hook.
>>
>> Cheers
>> --
>> Marco
>
>
> I have to agree with Weitz. On closer thought you would need to get a hash
> function to mach the test. A general intersection of O(N) may be
> inpractical.
> It works fine for the special cases for make-hash-table in CLHS.
> What I would do would be to go with the standard function and
> then implement your own when better efficiency is needed like
> Bland did. The generality of :test is really the culprit here.
> (Is this what you are trying to say?)
Yep.
> The only way to do this intersection O(N) that I know either
> explicity use a ordering of the list (a set implementation typically
> creates this)
> or uses hash to make the lookup O(1) this at the price of
> a considrable overhead setting it up.
In the case of the hash table tests, EQ, EQL, EQUAL, and EQUALP, the
setup time is really not that much (at least for the application I have)
when your sets (lists) are in the possibly hundreds of elements. I
tried this in LW and in an older CMUCL and the results were comparable:
meaning that the ad-hoc rewriting was warranted.
Cheers
--
Marco
From: Edi Weitz
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <uirv37zyr.fsf@agharta.de>
On Tue, 08 Nov 2005 19:25:55 +0100, "John Thingstad" <··············@chello.no> wrote:
> Indeed. I thought it was clear that this optimation is only
> general for (intersection <> <> :test <>) in LW.
> But since it is LW's library function intersection you
> want more efficient...
> I think most vendors have extensions and hidden functions that allow
> a more efficient implementation while still conforming to CLHS.
> Though the creators of this one may have been more interested in
> supporting weak pointers (to implement cash'es perhaps) it can
> clearly be used in intersection.
I don't think so. Usage of this hash table extension for INTERSECTION
doesn't make sense in the general case because for it to be efficient
you'll have to provide a hash function which depends on the test
function.
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Fred Gilham wrote:
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
> > Not only that. There no guarantee that the operations are
> > efficiently implemented. I got recently bitten by discovering that
> > INTERSECTION (on an implementation I won't name) was implemented
> > using the naive quadratic algorithm.
>
> Name it! Name it! Don't protect the guilty!
MCL has this problem, but in general there isn't a lot that can be
done. That
(reduce 'intersection ...)
and
(reduce 'union ...)
are going to be slow is practically built into the language.
^L
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <87zmoekh76.fsf@qrnik.zagroda>
Marco Antoniotti <·······@cs.nyu.edu> writes:
> Not only that. There no guarantee that the operations are efficiently
> implemented. I got recently bitten by discovering that INTERSECTION
> (on an implementation I won't name) was implemented using the naive
> quadratic algorithm.
I think whoever represents sets by lists, either doesn't care about
efficiency, or knows that the lists are so short that naive algorithms
are applicable.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: Marco Antoniotti
Subject: Re: Why do Python, Java and Perl have so many libraries and CL does not?
Date:
Message-ID: <ok8cf.68$pa3.24091@typhoon.nyu.edu>
Marcin 'Qrczak' Kowalczyk wrote:
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
>
>>Not only that. There no guarantee that the operations are efficiently
>>implemented. I got recently bitten by discovering that INTERSECTION
>>(on an implementation I won't name) was implemented using the naive
>>quadratic algorithm.
>
>
> I think whoever represents sets by lists, either doesn't care about
> efficiency, or knows that the lists are so short that naive algorithms
> are applicable.
>
Sometimes lists are all you need. On top of that, if you represent sets
with something else (e.g. some balanced tree representation) you have to
take into account the consing that "listing" creates, plus, you need to
rely on some library. I have my own (cfr. the ancient "trees" library
in the AI.Repository), but I do not have INTERSECTION built for all of
them. After some thinking, for my specific application, ensuring a O(N)
algorithm for intersecting two lists turned out to be the best and
simplest way to have have my cake and eat it too.
Cheers
--
Marco