I have been working on this problem for a while, It is in one of the
books I bought to teach myself but I can not solve it. For some
reason I am getting tons of errors, in the book it says it is a
begginer program but I can not get it, It is killing me I, would love
to see if someone could do it so I will have some closure.
Thanks in advance
Steve
Steve Heller <·······@optonline.net> wrote in message
······················@enews.newsguy.com...
| I have been working on this problem for a while, It is in one of the
| books I bought to teach myself but I can not solve it. For some
| reason I am getting tons of errors, in the book it says it is a
| begginer program but I can not get it, It is killing me I, would love
| to see if someone could do it so I will have some closure.
| Thanks in advance
| Steve
|
Here are a couple of versions. There should be some useful things to digest in them:
(defun average(args)
(/ (apply #'+ args) (length args)))
(defun avg(args)
(let ((sum 0) (count 0))
(loop for x in args do
(setf sum (+ sum x))
(incf count))
(/ sum count)))
Coby
From: Tim Bradshaw
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <ey3k8hm6ql7.fsf@cley.com>
* Coby Beck wrote:
> (defun avg(args)
> (let ((sum 0) (count 0))
> (loop for x in args do
> (setf sum (+ sum x))
> (incf count))
> (/ sum count)))
I think if you're going to use loop then you should go the whole
horrid way:
(defun avg (args)
(loop for x in args
for l upfrom 1
summing x into tot
finally (return (/ tot l))))
--tim
From: Russell Senior
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <86n1mhyit7.fsf@coulee.tdb.com>
>>>>> "Tim" == Tim Bradshaw <···@cley.com> writes:
Tim> I think if you're going to use loop then you should go the whole
Tim> horrid way:
Tim> (defun avg (args) (loop for x in args for l upfrom 1 summing
Tim> x into tot finally (return (/ tot l))))
Note that the current CLISP implementation[1] gives the wrong answer with
that code. This subject was discussed a month or two ago regarding
the lifetime of loop variables[2].
Another loopy way is:
(defun avg (args)
(loop for x in args
count x into l
sum x into tot
finally (return (/ tot l))))
or, with protection against empty ARGS, maybe:
(defun avg (args)
(loop for x in args
count x into l
sum x into tot
finally (return (if (zerop l)
0
(/ tot l)))))
[1] > (lisp-implementation-version)
"2000-03-06 (March 2000)"
[2] <http://www.deja.com/[ST_rn=ps]/getdoc.xp?AN=588956813>
--
Russell Senior ``The two chiefs turned to each other.
·······@aracnet.com Bellison uncorked a flood of horrible
profanity, which, translated meant, `This is
extremely unusual.' ''
From: David Hanley
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <39060FEF.2CA2EA75@ncgr.org>
Lots of ways to do it. The shortest is:
(defun average( numbers ) (/ (reduce #'+ numbers) (length numbers)))
dave
(defun average (num)
(let ((len (length num)))
(/ (eval (cons '+ num)) len))
is the simplest I can think of. I'm pretty new myself so there might be
something more straightforward than eval to use.
Ziad Ganim wrote:
>
> (defun average (num)
> (let ((len (length num)))
> (/ (eval (cons '+ num)) len))
>
> is the simplest I can think of. I'm pretty new myself so there might be
> something more straightforward than eval to use.
There is, but being a fellow Berkeleyan, I can at least understand where
you're coming from... =)
From: Joe Marshall
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <u4s8npqhl.fsf@alum.mit.edu>
Ziad Ganim <·····@uclink4.berkeley.edu> writes:
> (defun average (num)
> (let ((len (length num)))
> (/ (eval (cons '+ num)) len))
>
> is the simplest I can think of. I'm pretty new myself so there might be
> something more straightforward than eval to use.
Don't use eval in this case, use apply. What would happen if you did this?
(average (list 1 2 A 3 4))
From: Paul Rudin
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <wkitx3d2hu.fsf@scientia.com>
>>>>> "Joe" == Joe Marshall <·········@alum.mit.edu> writes:
Joe> Ziad Ganim <·····@uclink4.berkeley.edu> writes:
>> (defun average (num) (let ((len (length num))) (/ (eval (cons '+ num))
>> len))
>>
>> is the simplest I can think of. I'm pretty new myself so there might be
>> something more straightforward than eval to use.
Joe> Don't use eval in this case, use apply. What would happen if you did
Joe> this?
Although apply will fail if the length of the list exceeds
CL:CALL-ARGUMENTS-LIMIT. The reduce solution already suggested will work
with longer lists.
From: Barry Margolin
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <YhZN4.11$xb5.596@burlma1-snr2>
In article <·············@alum.mit.edu>,
Joe Marshall <·········@alum.mit.edu> wrote:
>Ziad Ganim <·····@uclink4.berkeley.edu> writes:
>
>> (defun average (num)
>> (let ((len (length num)))
>> (/ (eval (cons '+ num)) len))
>>
>> is the simplest I can think of. I'm pretty new myself so there might be
>> something more straightforward than eval to use.
>
>Don't use eval in this case, use apply. What would happen if you did this?
>
>(average (list 1 2 A 3 4))
Assuming A's value is a number (as required by the function), I think this
would work fine and give the same result as a solution using apply. Why do
you think otherwise? Perhaps you were thinking of:
(average '(1 2 A 3 4))
That won't work properly in any implementation of AVERAGE, although the
version with EVAL might not generate an error like other versions would (in
the case where A has a global value).
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Joe Marshall
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <uzoqfo5ev.fsf@alum.mit.edu>
Barry Margolin <······@genuity.net> writes:
> >(average (list 1 2 A 3 4))
>
> Assuming A's value is a number (as required by the function), I think this
> would work fine and give the same result as a solution using apply. Why do
> you think otherwise? Perhaps you were thinking of:
>
> (average '(1 2 A 3 4))
D'oh!
>
> That won't work properly in any implementation of AVERAGE, although the
> version with EVAL might not generate an error like other versions would (in
> the case where A has a global value).
Yes, this is what I was getting at.
From: Thomas A. Russ
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <ymiitx3tr2q.fsf@sevak.isi.edu>
Ziad Ganim <·····@uclink4.berkeley.edu> writes:
> (defun average (num)
> (let ((len (length num)))
> (/ (eval (cons '+ num)) len))
>
> is the simplest I can think of. I'm pretty new myself so there might be
> something more straightforward than eval to use.
It is generally best to avoid using EVAL in Lisp. (There are times when
it is necessary, but this isn't one of them). Rather than using the
EVAL, one could use APPLY, since + can take any number of arguments.
(defun average (num)
(/ (apply #'+ num) (length num)))
This works well in theory, but in practice could run afoul of the
maximum number of function arguments allowed in a particular
implementation (see the constant CALL-ARGUMENTS-LIMIT). Using REDUCE
avoids that problem:
(defun average (num)
(/ (reduce #'+ num) (length num)))
Now, neither of these solutions will work for a call of (AVERAGE '())
so one should test for an empty list and return something appropriate
(probably NIL or 0).
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
From: Barry Margolin
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <vx%N4.22$xb5.1122@burlma1-snr2>
In article <···············@sevak.isi.edu>,
Thomas A. Russ <···@sevak.isi.edu> wrote:
> (defun average (num)
> (/ (apply #'+ num) (length num)))
>
>This works well in theory, but in practice could run afoul of the
>maximum number of function arguments allowed in a particular
>implementation (see the constant CALL-ARGUMENTS-LIMIT). Using REDUCE
>avoids that problem:
This comes up so often, I thinks what Lisp needs is something in between
REDUCE and APPLY. APPLY calls the function once, but can fail if you have
too many arguments; but REDUCE can be inefficient because it calls the
function n-1 times -- I expect this can be quite noticeable for functions
like +, where the function call overhead is much larger than the work the
function actually does. What we need is something like Unix's "xargs"
command, which will bundle up the arguments into CALL-ARGUMENTS-LIMITS
bunches, and invoke the function for each group, and then recursively do
this with all the results (or we could simplify it and have it merge the
results pairwise into the final result -- unless the original list is
really huge it's probably not necessary to get it down to log n calls).
Perhaps it should actually be an option to REDUCE itself, :MAX-ARGS. The
default would be 2, but you could use :MAX-ARGS CALL-ARGUMENTS-LIMIT to get
the maximum bundling.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Michael Kappert
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <39089D4F.6372E63@iitb.fhg.de>
Barry Margolin wrote:
> In article <···············@sevak.isi.edu>,
> Thomas A. Russ <···@sevak.isi.edu> wrote:
> > (defun average (num)
> > (/ (apply #'+ num) (length num)))
> >
> >This works well in theory, but in practice could run afoul of the
> >maximum number of function arguments allowed in a particular
> >implementation (see the constant CALL-ARGUMENTS-LIMIT). Using REDUCE
> >avoids that problem:
> This comes up so often, I thinks what Lisp needs is something in between
> REDUCE and APPLY. APPLY calls the function once, but can fail if you have
> too many arguments; but REDUCE can be inefficient because it calls the
> function n-1 times -- I expect this can be quite noticeable for functions
> like +, where the function call overhead is much larger than the work the
> function actually does. What we need is something like Unix's "xargs"
> command, which will bundle up the arguments into CALL-ARGUMENTS-LIMITS
> bunches, and invoke the function for each group [...]
> Perhaps it should actually be an option to REDUCE itself, :MAX-ARGS. The
> default would be 2, but you could use :MAX-ARGS CALL-ARGUMENTS-LIMIT to get
> the maximum bundling.
This is no solution to
(reduce #'- <lots-of-numbers>)
because using non-default values for :max-args will change its semantics.
I think optimizing this should be left to the compiler.
For example, if the compiler sees (reduce #'+ ...), it knows a two-argument
version
of #'+ will be needed. disassemble output seems to suggests the ACL demo
for linux doesn't do this.
Maybe optimizations similar to tail-call optimization can be made.
Michael
--
From: Barry Margolin
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <Tf1O4.42$xb5.1405@burlma1-snr2>
In article <················@iitb.fhg.de>,
Michael Kappert <···@iitb.fhg.de> wrote:
>Barry Margolin wrote:
>
>> In article <···············@sevak.isi.edu>,
>> Thomas A. Russ <···@sevak.isi.edu> wrote:
>> > (defun average (num)
>> > (/ (apply #'+ num) (length num)))
>> >
>> >This works well in theory, but in practice could run afoul of the
>> >maximum number of function arguments allowed in a particular
>> >implementation (see the constant CALL-ARGUMENTS-LIMIT). Using REDUCE
>> >avoids that problem:
>
>> This comes up so often, I thinks what Lisp needs is something in between
>> REDUCE and APPLY. APPLY calls the function once, but can fail if you have
>> too many arguments; but REDUCE can be inefficient because it calls the
>> function n-1 times -- I expect this can be quite noticeable for functions
>> like +, where the function call overhead is much larger than the work the
>> function actually does. What we need is something like Unix's "xargs"
>> command, which will bundle up the arguments into CALL-ARGUMENTS-LIMITS
>> bunches, and invoke the function for each group [...]
>
>> Perhaps it should actually be an option to REDUCE itself, :MAX-ARGS. The
>> default would be 2, but you could use :MAX-ARGS CALL-ARGUMENTS-LIMIT to get
>> the maximum bundling.
>
>This is no solution to
> (reduce #'- <lots-of-numbers>)
>because using non-default values for :max-args will change its semantics.
Of course. It only applies in the cases where you might be tempted to use
APPLY, but can't because of CALL-ARGUMENTS-LIMIT. Since (apply #'- list)
and (reduce #'- list) are different, my propsal is clearly not applicable.
In other words, it only works for operations that are associative.
>I think optimizing this should be left to the compiler.
>For example, if the compiler sees (reduce #'+ ...), it knows a two-argument
>version
>of #'+ will be needed. disassemble output seems to suggests the ACL demo
>for linux doesn't do this.
True, the compiler could optimize the built-ins. But my REDUCE extension
would also work for user-defined functions, which are generally not
amenable to such optimizations (unless they're proclaimed INLINE, and even
then I would be surprised to find a compiler doing inline substitution in
this situation).
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: David Bakhash
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <m38zxxgja6.fsf@alum.mit.edu>
after reading barry's post, I realize that this optimization would
have affected code I've written in the past.
I decided to say screw it at the time, because I was using ACL, and
call-arguments-limit was really high (2^14 or something), and so I
decided to use #'apply. But considering that an implementation can
get really pathetic on this value, it's really not a bad idea.
I don't think that it needs to be a compiler-level thing, though. I
think that it could easily be written in Lisp.
One interesting aspect of it, if done in Lisp, is that you may end up
with two versions, such as a reduce* and an nreduce*.
If anyone cares to implement this/these, and does benchmarks, please
post them, as I'm sure many (including myself) would be interested.
dave
From: Barry Margolin
Subject: Re: Finding Average without using Recusrion only using Prog
Date:
Message-ID: <OFHO4.14$_B6.61@burlma1-snr2>
In article <··············@alum.mit.edu>,
David Bakhash <·····@alum.mit.edu> wrote:
>after reading barry's post, I realize that this optimization would
>have affected code I've written in the past.
>
>I decided to say screw it at the time, because I was using ACL, and
>call-arguments-limit was really high (2^14 or something), and so I
>decided to use #'apply. But considering that an implementation can
>get really pathetic on this value, it's really not a bad idea.
>
>I don't think that it needs to be a compiler-level thing, though. I
>think that it could easily be written in Lisp.
Certainly. But it seemed like such a common need that I thought it *ought*
to be standard.
--
Barry Margolin, ······@genuity.net
Genuity, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Michael Kappert
Subject: Efficient general apply, was: Re: Finding Average...
Date:
Message-ID: <390CB04E.23C2BCAD@iitb.fhg.de>
David Bakhash wrote:
> I don't think that it needs to be a compiler-level thing, though. I
> think that it could easily be written in Lisp.
>
> One interesting aspect of it, if done in Lisp, is that you may end up
> with two versions, such as a reduce* and an nreduce*.
>
> If anyone cares to implement this/these, and does benchmarks, please
> post them, as I'm sure many (including myself) would be interested.
I tried, but didn't really succeed.
The following destructive version is only marginally faster than reduce.
Nondestructive versions i tried are even slower than reduce, or don't
reduce the number of calls to the reducing function.
(defun napply* (f arguments)
(let ((result (apply f ()))
(k (floor (length arguments) call-arguments-limit))
split
rest)
(dotimes (j k (apply f result arguments))
(setf split (nthcdr (1- call-arguments-limit) arguments))
(setf rest (cdr split))
(setf (cdr split) ())
(setf result (apply f result arguments))
(setf arguments rest))))
I would be interested in seeing how to make this really fast.
Interestingly, apply accepts arguments a multiple of
call-arguments-limit,
but isn't faster than reduce (on ACL/Linux).
Michael
--
From: David Bakhash
Subject: Re: Efficient general apply, was: Re: Finding Average...
Date:
Message-ID: <m33do39cel.fsf@alum.mit.edu>
there are a couple of things to consider, though.
First off, you named the function napply*, which implied that you've
looked at the problem more carefully than I had. I should have called
mine (n)apply* rather than (n)reduce*, given what the whole point of
the exersise was. Secondly, implementing a reduce-like function is
much more of a pain, especially considering its various arguments.
Your approach was more sane, and thanks for posting it.
dave
In article <·················@iitb.fhg.de>,
Michael Kappert <···@iitb.fhg.de> wrote:
> I tried, but didn't really succeed....
here's my take on it:
1) in CMUCL (for example) call-arguments-limit is 536 million. I
couldn't even begin to cons up a list that big on my machine and not
have it swap all to hell and back again.... so apply is
practically ALWAYS going to work for me...
2) here's a version of napply...
(defun napply* (f arguments)
(labels
((getnthcdr (n l) ;; this ensures that we never call (cdr nil) a
;; bunch of times like (nthcdr 1000 nil) will in
;; CMUCL
(if (< n 0)
(error "getnthcdr called for n < 0")
(do ((count 0 (1+ count))
(thecdr l (cdr thecdr)))
((or (not thecdr ) (= count n))
thecdr)))))
(let ((accumulate '()))
(do* ((top arguments bottom)
(endtop (getnthcdr (1- call-arguments-limit) top)
(getnthcdr (1- call-arguments-limit) top))
(bottom (cdr endtop) (cdr endtop)))
((not top) (if (cdr accumulate)
(napply* f (nreverse accumulate)) (car
accumulate)))
; whoo hope it optimizes away
; tail recursion, but if not,
; then we could stick in an
; explicit loop here. at the
; very least, this should go
; to log n depth right?
(if (consp endtop)
(setf (cdr endtop) nil))
(push (apply f top) accumulate)))))
when I test this, compiled with standard compiler options (ie. no
special speed or compile-speed declarations) against reduce and apply
(call this function 30 times for a 10000 element list each time) in
CMUCL doing an apply of #'+
I get:
Seconds | Consed | Calls | Sec/Call | Name:
------------------------------------------------------
0.680 | 4,804,720 | 30 | 0.02266 | REDUCE
0.640 | 2,405,440 | 30 | 0.02133 | NAPPLY*
0.340 | 2,402,600 | 30 | 0.01133 | APPLY
------------------------------------------------------
1.660 | 9,612,760 | 90 | | Total
which suggests that: we shouldn't worry about apply, just use it, at
least for CMUCL. if you are worried about apply for your implementation
then the napply* above is not a bad place to start. If you use reduce,
it isn't so bad either...
note: if your lisp doesn't optimize the tail call in my napply, just put
in an explicit go tag and go to the beginning of the loop again... or
ignore it. Shoot it's only logarithmically deep, and the base of the
logarithm is essentially the number of arguments allowed... this
probably isn't your hotspot...
Sent via Deja.com http://www.deja.com/
Before you buy.
yuk, my code indenting got thoroughly mangled by the deja posting
process... sorry if it's hard to read...
lemme see if I can get a better version...
(defun napply* (f arguments)
(labels
((getnthcdr (n l) ;; this ensures that we never call (cdr nil) a
;; bunch of times like (nthcdr 1000 nil) will in
;; CMUCL
(if (< n 0)
(error "getnthcdr called for n < 0")
(do ((count 0 (1+ count))
(thecdr l (cdr thecdr)))
((or (not thecdr ) (= count n))
thecdr)))))
(let ((accumulate '()))
(do* ((top arguments bottom)
(endtop (getnthcdr (1- call-arguments-limit) top)
(getnthcdr (1- call-arguments-limit) top))
(bottom (cdr endtop) (cdr endtop)))
((not top) (if (cdr accumulate)
(napply* f (nreverse accumulate))
;; whoo hope it optimizes away tail recursion,
;; but if not, then we could stick in an
;; explicit loop here. at the very least, this
;; should go to log n depth right?
;; below is commented out a go which works just
;; as well as the tail recursion above, but is
;; guaranteed not to increase the stack depth.
;;;(progn
;;;(setf top (nreverse accumulate))
;;;(go tail-recurse))
(car accumulate)))
(if (consp endtop)
(setf (cdr endtop) nil))
(push (apply f top) accumulate)
tail-recurse))))
Sent via Deja.com http://www.deja.com/
Before you buy.