I need to do something similar to collect-max (described in CLtL2 but
not in the hyperspec), except that collect-max requires a list of
numbers. Mine is a list of structs, so I need to be able to provide a
custom comparison function. The following works, but my definition for
"biggest" is very inefficient. It sorts the entire list, then takes the
first element, which probably takes a lot longer than just finding the
biggest element. Any better ideas? Using a dolist and keeping track of
the biggest apple encountered so far should work, but it's rather
inelegant. I'm guessing there's a built in function that takes care of
this, but I couldn't find it.
(defstruct apple
color
radius)
(defvar *applelist*
(list
(make-apple :color "red" :radius 2)
(make-apple :color "green" :radius 1)
(make-apple :color "orange" :radius 4)
(make-apple :color "purple" :radius 3)))
(defun bigger (apple1 apple2)
(> (apple-radius apple1)
(apple-radius apple2)))
(defun biggest (lst)
(car
(sort lst #'bigger)))
>The following works, but my definition for
>"biggest" is very inefficient.
>
>(defstruct apple
> color
> radius)
>(defun bigger (apple1 apple2)
> (> (apple-radius apple1)
> (apple-radius apple2)))
>(defun biggest (lst)
> (car
> (sort lst #'bigger)))
I found something similar to what I want. The problem now is that it
returns the biggest radius (4) instead of the apple with the biggest
radius (:color "orange" :radius 4). Plus it's starting to look more
complicated instead of less.
(loop for i in *applelist*
maximizing (apple-radius i) into max
finally (return max))
This is such a simple and common idea. Surely CL has a simple way to do
this.
"Eric Lavigne" <············@gmail.com> writes:
> (loop for i in *applelist*
> maximizing (apple-radius i) into max
> finally (return max))
This can be written simpler:
(loop for i in *applelist* maximizing (apple-radius i))
or
(reduce #'max *applelist* :key #'apple-radius)
Unfortunately I don't think there's really any elegant way to solve
your problem. It boils down to something like
(loop with biggest-apple = (first *applelist*)
for i in (rest *applelist*)
do (when (> (apple-radius i) (apple-radius biggest-apple))
(setf biggest-apple i))
finally (return biggest-apple))
--
Frode Vatvedt Fjeld
>"Eric Lavigne" <············@gmail.com> writes:
>> (loop for i in *applelist*
>> maximizing (apple-radius i) into max
>> finally (return max))
>This can be written simpler:
> (loop for i in *applelist* maximizing (apple-radius i))
>or
> (reduce #'max *applelist* :key #'apple-radius)
>Unfortunately I don't think there's really any elegant way to solve
>your problem. It boils down to something like
> (loop with biggest-apple = (first *applelist*)
> for i in (rest *applelist*)
> do (when (> (apple-radius i) (apple-radius biggest-apple))
> (setf biggest-apple i))
> finally (return biggest-apple))
>--
>Frode Vatvedt Fjeld
I hadn't seen reduce before. The following function solves my problem
rather nicely. Thanks for the idea, Frode.
(defun biggest (lst)
(reduce
(lambda (x y)
(if (bigger x y) x y))
lst))
What you want is EXREMUM <http://cliki.net/EXTREMUM>, which does
exactly what you asked for. I see you've found the (reduce (comparator
#'bigger) list) method, but that has some shortcomings.
What happens when you try to find the biggest apple in ()? Should you
return nil, or signal an error? What restarts should be provided?
What happens if there are multiple apples of equal size? Which one gets
returned?
There are some other minor problems, but my summary is: get
cl-utilities <http://common-lisp.net/project/cl-utilities/>, hopefully
via asdf-install, and use EXTREMUM. It addresses some of the issues I
mentioned, and it's maintained with a lot more attention to detail than
you're probably willing to expend.
If you just want the juicy part, here's the file you want:
http://common-lisp.net/cgi-bin/viewcvs.cgi/cl-utilities/extremum.lisp?rev=1.1.1.1&cvsroot=cl-utilities&content-type=text/vnd.viewcvs-markup
(Full disclosure: I maintain the cl-utilities project, so this is a
plug.)
-Peter
>There are some other minor problems, but my summary is: get
>cl-utilities <http://common-lisp.net/project/cl-utilities/>, hopefully
>via asdf-install, and use EXTREMUM. It addresses some of the issues I
>mentioned, and it's maintained with a lot more attention to detail
than
>you're probably willing to expend.
Ask a simple question... stumble into a gold mine. That seems to happen
pretty often on CLL ^^
Thanks.
"Eric Lavigne" <············@gmail.com> writes:
> I need to do something similar to collect-max (described in CLtL2 but
> not in the hyperspec), except that collect-max requires a list of
> numbers. Mine is a list of structs, so I need to be able to provide a
> custom comparison function.
Follow the conventions for the standard functions, and have your
function take :TEST and :KEY arguments:
(defun maximize (list &key (test #'>) (key #'identity))
(prog (max)
is-there-any-work?
(when (null list) (return (values nil nil)))
initialize-max
(setf max (first list))
are-we-finished?
(when (null list)
(return (values max t)))
process-current-element
(if (funcall test (funcall key (first list)))
(setf max (pop list))
(pop list))
(go are-we-finished?)))
Now you can use it on your structs no problem:
(maximize foo :key #'apple-radius)
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
Your MAXIMIZE function is defective, returning the last element of the
list whether or not it's biggest. Here's an improved version, which
works (and is about four times slower):
(defun maximize (list &key (test #'>) (key #'identity))
(prog (max)
is-there-any-work?
(when (null list) (return (values nil nil)))
initialize-max
(setf max (first list))
are-we-finished?
(when (null list)
(return (values max t)))
process-current-element
(if (funcall test
(funcall key (first list))
(funcall key max))
(setf max (pop list))
(pop list))
(go are-we-finished?)))
I apologize for the lack of indentation; Google Groups really needs to
stop chomping whitespace.
[brace yourself for blatant plugging that would put Kenny Tilton to
shame...]
A more clever implementation would accept :start and :end keyword
arguments, work on all proper sequences, and call KEY less. Most of
this is available in cl-utilities
<http://common-lisp.net/project/cl-utilities/>, and all of it is
available in CVS.
-Peter
"Peter Scott" <·········@gmail.com> writes:
> Your MAXIMIZE function is defective, returning the last element of the
> list whether or not it's biggest. Here's an improved version, which
> works (and is about four times slower):
Yeah, that was pointed out to me after I posted. I was concentrating
too much on needlessly (and badly) using PROG to make it read like a
Knuth algorithm, and forgot to check to see if it was correct. Oops.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
>I was concentrating too much on needlessly (and badly) using
>PROG to make it read like a Knuth algorithm, and forgot to
>check to see if it was correct. Oops.
Knuth wrote a 4 volume series on algorithms, with all code written in a
hypothetical version of assembler. You try to immitate the same style
in Lisp? I'm confused.
"Eric Lavigne" <············@gmail.com> writes:
> >I was concentrating too much on needlessly (and badly) using
> >PROG to make it read like a Knuth algorithm, and forgot to
> >check to see if it was correct. Oops.
>
> Knuth wrote a 4 volume series on algorithms, with all code written in a
> hypothetical version of assembler. You try to immitate the same style
> in Lisp? I'm confused.
(a) I was writing that way for shits and giggles on usenet, that's not
normally how I code
(b) His books include precise descriptions of algorithms that read
like "Q1 Initialize J. ... Q2. Check for blah. ... Q7. Increment f_12
and go to Q2."
(c) Knuth has written more than just The AOCP
(d) He's still working on AOCP, and is not yet finished with vol 4,
and I believe he still plans on writing a vol 5. Either way, I was
just reading Fascile 2 from Volume 4, which is what sparked my corny
sense of humor; it's a great read.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
"Eric Lavigne" <············@gmail.com> writes:
> I need to do something similar to collect-max (described in CLtL2
> but not in the hyperspec), except that collect-max requires a list
> of numbers. Mine is a list of structs, so I need to be able to
> provide a custom comparison function.
For what it's worth, ITERATE (a Lispier replacement for LOOP) has a
nice syntax for this:
(iter (for apple :in *applelist*)
(finding apple :maximizing (apple-radius apple)))
(See http://www.common-lisp.net/project/iterate/)
James (iterate addict)
Eric,
Have you thought about an insertion sort?
I'm about to embark on a voyage into Lisp, which is new territory for
me, so this may not be a 'Lispy' approach. Nonetheless . . .
For the whole list, find the largest, then if it is not the first
element, swap it with the first element. (Now use the first element.)
To continue the insertion sort, recurse on the cdr, in your case using
each element as it becomes available.
This allows you to use the first result (and each additional result)
immediately, instead of waiting for the sort to finish. It is also the
case that each iteration operates on a smaller list than its
predecessor, so each result is found in succeedingly shorter times.
If this is a list that varies over time, you can insert new elements
into the list in sorted order, or keep track of the last-sorted item,
and place new elements after the last-sorted item, only running the
insertion sort on the tail of the list when necessary.
There are other sorting methods that may run faster (I'd have to know
more about 'how sorted' the list is expected to be), but this one should
start returning results quickly.
Hope this helps,
--
Barry
Eric Lavigne wrote:
>I need to do something similar to collect-max (described in CLtL2 but
>not in the hyperspec), except that collect-max requires a list of
>numbers. Mine is a list of structs, so I need to be able to provide a
>custom comparison function. The following works, but my definition for
>"biggest" is very inefficient. It sorts the entire list, then takes the
>first element, which probably takes a lot longer than just finding the
>biggest element. Any better ideas? Using a dolist and keeping track of
>the biggest apple encountered so far should work, but it's rather
>inelegant. I'm guessing there's a built in function that takes care of
>this, but I couldn't find it.
>
>(defstruct apple
> color
> radius)
>
>(defvar *applelist*
> (list
> (make-apple :color "red" :radius 2)
> (make-apple :color "green" :radius 1)
> (make-apple :color "orange" :radius 4)
> (make-apple :color "purple" :radius 3)))
>
>(defun bigger (apple1 apple2)
> (> (apple-radius apple1)
> (apple-radius apple2)))
>
>(defun biggest (lst)
> (car
> (sort lst #'bigger)))
>
>
>
>Have you thought about an insertion sort?
>I'm about to embark on a voyage into Lisp, which is new territory for
>me, so this may not be a 'Lispy' approach. Nonetheless . . .
>There are other sorting methods that may run faster (I'd have to know
>more about 'how sorted' the list is expected to be), but this one
should
>start returning results quickly.
I trust the built in sort function to be faster than anything I would
write myself. If your insertion sort does a better/faster job of
sorting lists than the built in sort, this would be a good thing to
discuss with compiler writers ^^
The reason I consider the function below to be inefficient is that a
full sort is not really needed. After sorting the entire list, it
throws out all but the first item. If all I want to know is the biggest
item, why sort the rest of the items? I wasn't looking for a faster
sort, just an elegant way to get the biggest item without wasting time
on sorting. Peter's EXREMUM <http://cliki.net/EXTREMUM> does that job
nicely.
(defun biggest (lst)
(car
(sort lst #'bigger)))
Eric Lavigne wrote:
> I trust the built in sort function to be faster than anything I would
> write myself. If your insertion sort does a better/faster job of
> sorting lists than the built in sort, this would be a good thing to
> discuss with compiler writers ^^
A partial insertion sort would be a good description for the algorithm
you would use to write an n-biggest-elements function (either
destructively or with way too much consing). An insertion sort only
requires you to go until you have the n biggest elements, and then you
can stop. SORT can't possibly know that you only intend to use a few of
the return values, so it'll use a general-purpose sorting algorithm.
If you just want to get the biggest element, I suppose you *could*
think of that as a mergesort, but I don't see much point.
> The reason I consider the function below to be inefficient is that a
> full sort is not really needed. After sorting the entire list, it
> throws out all but the first item. If all I want to know is the
biggest
> item, why sort the rest of the items? I wasn't looking for a faster
> sort, just an elegant way to get the biggest item without wasting
time
> on sorting.
That's (sort of) why insertion sort was proposed; it lets you do
partial sorting.
> Peter's EXREMUM <http://cliki.net/EXTREMUM> does that job
> nicely.
Yay! I have a user!
-Peter
"Peter Scott" <·········@gmail.com> writes:
> Eric Lavigne wrote:
> > I trust the built in sort function to be faster than anything I would
> > write myself. If your insertion sort does a better/faster job of
> > sorting lists than the built in sort, this would be a good thing to
> > discuss with compiler writers ^^
This is often not true. In particular, the built-in sort is in
general performing a function call for every comparison. if you write
your own sort (or in my case, a sort template), you can easily avoid
this.
rif
Eric Lavigne wrote:
> (defstruct apple
> color
> radius)
>
> (defvar *applelist*
> (list
> (make-apple :color "red" :radius 2)
> (make-apple :color "green" :radius 1)
> (make-apple :color "orange" :radius 4)
> (make-apple :color "purple" :radius 3)))
What about
(defun biggest (ls)
(loop for apple in ls
maximizing (apple-radius apple)
return apple))
CL-USER 11 > (biggest *applelist*)
#S(APPLE COLOR "orange" RADIUS 4)
Quite similar to your earlier loop post, but you forgot to "return
apple".
--
Don't let school interfere with your education. -- Mark Twain
Ulrich Hobelmann <···········@web.de> wrote:
> What about
> (defun biggest (ls)
> (loop for apple in ls
> maximizing (apple-radius apple)
> return apple))
> CL-USER 11 > (biggest *applelist*)
> #S(APPLE COLOR "orange" RADIUS 4)
On which system did you create this transcript, eh?
College Moocher's United (CMU) Fake Lisp?
> Don't let school interfere with your education. -- Mark Twain
Yeah... and don't let your conscience interfere with mooching an
education off people you hate on usenet.
A. Nawroth wrote:
> Ulrich Hobelmann <···········@web.de> wrote:
>
>
>>What about
>>(defun biggest (ls)
>> (loop for apple in ls
>> maximizing (apple-radius apple)
>> return apple))
>
>
>>CL-USER 11 > (biggest *applelist*)
>>#S(APPLE COLOR "orange" RADIUS 4)
>
>
> On which system did you create this transcript, eh?
> College Moocher's United (CMU) Fake Lisp?
It's called LispWorks 4.3.7 Personal Edition.
Whow, just pasted the code again to see what you are complaining
about, and now it says radius 2... Weird...
Hm, seems like I misunderstood something, but due to other inputs
I made it seemed to work. Really weird, I didn't modify the list,
or anything. Just tried to reconstruct what I tried to write, but
it doesn't work. Well, my apologies for that crap.
Is there any way to use "maximizing" to somehow trigger a "return"
in the loop?
>>Don't let school interfere with your education. -- Mark Twain
>
>
> Yeah... and don't let your conscience interfere with mooching an
> education off people you hate on usenet.
What's mooching, and who do I hate??
--
Don't let school interfere with your education. -- Mark Twain