Dimitry Shuster (·······@umbc.edu) wrote:
: Can someone tell me what is wrong with this code? I have been
: working at it for 9 hours and I just cant get it. I feel like
: i am going to throw this computer out the window!!!
: please help
: what I am trying to do is count the depth of a list!!!
: (defun depth (S1)
: (cond
: ((null S1) 0)
: ((listp (car S1)
: (+ 1(depth(car S1)))))
: (t (depth (cdr S1)))))
: I am off by one always and I have no clue how to fix it!!!!!
: Thanks to anyone who can tell me whats wrong!!!!
Hello Dimitri, isn't Lisp beautiful? Do you know the meaning of
Lisp? Lots of Stupids and Irritating Parenthesis!
Well, the problem with your function is that it only calculates the depth of
the first sublist (if any). You must remember that there may exist others.
For example, for the list ((a) (a (b))) the result of your function is 2
and not 3. The problem is the recursion, always the recursion. I saw the answer
from Peter that is an iterative solution. Now, I'll give you a possible
purely recursive one. "Programming in Lisp is a kind of art".
------------------- code -------------------
; iterative function from Peter
(defun depth2 (s)
(cond ((null s) 0)
((atom s) 0)
((listp s)
(1+ (apply #'max (mapcar #'depth2 s))))
(t 'error)))
; (my) recursive function
(defun rec-depth (s1)
(cond ((null s1) 0)
((atom s1) 0)
(t (max (1+ (rec-depth (car s1)))
(rec-depth (cdr s1))))))
--------------------------------------------
Pay attention to the recursive call in the end of my function.
And now, just for fun, here it is a "small" comparison between the two
functions, running on a Sparc Station, on Allegro Cl 4.1. As you will
notice, after compiling the two functions, the recursive one proves to be more
efficient.
----------------- the result of the tests ----------------
dribbling to file "/mnt/users/pcr/Inesc/jspell/values.txt"
NIL
USER(2): (load "teste.lsp")
; Loading /mnt/users/pcr/Inesc/jspell/teste.lsp.
T
USER(3): (setf a '(a (b) (a (b (c (d e))))))
(A (B) (A (B (C (D E)))))
USER(4): (depth2 a)
5
USER(5): (rec-depth a)
5
USER(6): (time (depth2 a))
cpu time (non-gc) 0 msec user, 0 msec system
cpu time (gc) 0 msec user, 0 msec system
cpu time (total) 0 msec user, 0 msec system
real time 8 msec
space allocation:
139 cons cells, 0 symbols, 448 other bytes,
5
USER(7): (time (rec-depth a))
cpu time (non-gc) 0 msec user, 0 msec system
cpu time (gc) 0 msec user, 0 msec system
cpu time (total) 0 msec user, 0 msec system
real time 11 msec
space allocation:
241 cons cells, 0 symbols, 832 other bytes,
5
USER(8): (compile 'depth2)
DEPTH2
NIL
NIL
USER(9): (compile 'rec-depth)
REC-DEPTH
NIL
NIL
USER(10): (time (depth2 a))
cpu time (non-gc) 0 msec user, 0 msec system
cpu time (gc) 0 msec user, 0 msec system
cpu time (total) 0 msec user, 0 msec system
real time 1 msec
space allocation:
19 cons cells, 0 symbols, 32 other bytes,
5
USER(11): (time (rec-depth a))
cpu time (non-gc) 0 msec user, 0 msec system
cpu time (gc) 0 msec user, 0 msec system
cpu time (total) 0 msec user, 0 msec system
real time 1 msec
space allocation:
1 cons cell, 0 symbols, 32 other bytes,
5
USER(12): (dribble)
--------------------------------------------
Best Regards and have fun with Lisp,
Paulo Reis.
-------------------------------------------------------------
Paulo Cesar Sobral dos Reis
Instituto de Engenharia de Sistemas e Computadores
Rua Alves Redol, no 9 Lisboa - Portugal
Tel: 3100000 ext: 305
------------------------------------------------------------
In article <············@mondas.demon.co.uk> Peter Ward <····@mondas.demon.co.uk> writes:
> As a naive lisp user I find it useful to see how code is
> optimised for speed/consing. Is I right to assume that the
> additional memory usage of depth2 is because mapcar creates
> a list just to hold the results of the recursive aplication?
Yes, you are right. Rather than build up the list of results and
apply max to the result, it is better to build up the resulting sum as
you go. This is done explicitly in the "recursive" solution, and can
also be done by using reduce rather than apply:
(defun depth3 (s)
(if (atom s)
0
(+ 1 (reduce #'max s :key #'depth3))))
In English, this says "The depth of s is 0 if s is an atom, otherwise
it is one more than the maximum of the depths of the elements of s."
One measure of good style is how closely the English paraphrase of the code
you write matches the English specification of the original problem.
Notes:
(1) Some older implementations of reduce do not support the :key keyword.
(2) (apply fn list) is only guaranteed to work for lists of length up to
call-arguments-limit, which can be as small as 50.
(3) Versions of depth using reduce and apply fail for arguments like (1 . 2).
(4) Every object is either an atom or a list.
--
Peter Norvig | Phone: 415-833-4022 FAX: 415-833-4111
Harlequin Inc. | Email: ······@harlequin.com
1010 El Camino Real, #310 | http://www.harlequin.com
Menlo Park CA 94025 | http://www.cs.berkeley.edu/~russell/norvig.html
In article <··········@inesc.pt> ···@snail "Paulo Cesar Reis" writes:
> ; iterative function from Peter
> (defun depth2 (s)
> (cond ((null s) 0)
> ((atom s) 0)
> ((listp s)
> (1+ (apply #'max (mapcar #'depth2 s))))
> (t 'error)))
>
> ; (my) recursive function
> (defun rec-depth (s1)
> (cond ((null s1) 0)
> ((atom s1) 0)
> (t (max (1+ (rec-depth (car s1)))
> (rec-depth (cdr s1))))))
[snip performance results]
> Paulo Reis.
Thank you Paulo. I would like to say that my solution is
_recursive_ on sublists, and the iteration is implicit by
use of mapcar and apply, which could be implemented recursively.
As a naive lisp user I find it useful to see how code is
optimised for speed/consing. Is I right to assume that the
additional memory usage of depth2 is because mapcar creates
a list just to hold the results of the recursive aplication?
--
Peter Ward ····@mondas.demon.co.uk
+44 1932 828822
Becareful when doing such experiments since results can be misleading.
Generally both your test DEPTH2 function and the function that calls TIME
should be compiled. The test function should iterated enough time to make
the times reported meaningful. I hope to have a future ACM Lisp Pointers
article on this.
--
Ken Anderson
Internet: ·········@bbn.com
BBN ST Work Phone: 617-873-3160
10 Moulton St. Home Phone: 617-643-0157
Mail Stop 6/4a FAX: 617-873-2794
Cambridge MA 02138
USA
In article <······················@lager.bbn.com>
········@lager.bbn.com (Ken Anderson) writes:
>Becareful when doing such experiments since results can be misleading.
Ken has an award-winning (*) paper on Lisp benchmarking/profiling that
I would recommend, except that the FTP site where I got it
(wheaton.bbn.com) is no longer accessible.
(*) Cleverest-title Award: "Courage in Profiles" :-)
>Generally both your test DEPTH2 function and the function that calls TIME
>should be compiled. The test function should iterated enough time to make
>the times reported meaningful.
On the other hand, this is a nontrivial matter also. If the function
you are timing is small, a LOOP can skew your results, since the LOOP
overhead is included in your timing. Furthermore, if you compile a
LOOP, the compiler is free to take out things that don't affect the
result. For instance, (loop repeat 10000 do (* Var1 (+ Var2 (sqrt Var3))))
could be taken out altogether at compile time and replaced by NIL.
What I typically use is a macro that expands into a PROGN repeating
the function call N times. Here it is:
;;; Part of http://www.apl.jhu.edu/~hall/lisp/Simple-Metering.lisp
;;;===========================================================================
;;; Time-Form: Takes a single form and optionally an integer N (default 20). It
;;; ========= runs the form N times and prints out the average time. Useful
;;; for timing very small, fast functions when the time-step of
;;; the builtin TIME function is too coarse.
;;; > (Time-Form (Foo)) ; Call (Foo) 20 times + print avg time
;;; > (Time-Form (Bar) 100) ; Call (Bar) 100 times + print avg time
;;; 1994 Marty Hall.
(defmacro Time-Form (Form &optional (Repetitions 20))
"Runs FORM N times, printing avg execution time and returning FORM's value"
(declare (optimize speed (safety 1) (compilation-speed 0)))
`(let* ((Start (get-internal-run-time))
(Value (progn ,@(loop for I from 1 to Repetitions collecting Form)))
(Stop (get-internal-run-time)))
(format t "~%Time to do ~S is ~0,5F sec."
',Form
(float (/ (- Stop Start)
(* ,Repetitions internal-time-units-per-second))))
Value))
Example: (pprint (macroexpand-1 '(Time-Form (Foo 1 2 3) 10)))
(LET* ((START (GET-INTERNAL-RUN-TIME))
(VALUE
(PROGN
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)
(FOO 1 2 3)))
(STOP (GET-INTERNAL-RUN-TIME)))
(FORMAT T "~%Time to do ~S is ~0,5F sec." '(FOO 1 2 3)
(FLOAT
(/ (- STOP START) (* 10 INTERNAL-TIME-UNITS-PER-SECOND))))
VALUE)
Note that if you really care, you could subtract off the time of one
call to get-internal-run-time. But since this only happens once, not
for each N, I usually ignore it.
- Marty
(proclaim '(inline skates))
In article <··········@aplcenmp.apl.jhu.edu> ····@aplcenmp.apl.jhu.edu (Marty Hall) writes:
> Ken has an award-winning (*) paper on Lisp benchmarking/profiling that
> I would recommend, except that the FTP site where I got it
> (wheaton.bbn.com) is no longer accessible.
>
> (*) Cleverest-title Award: "Courage in Profiles" :-)
>
You can not get that another other performance related stuff from
openmap.bbn.com pub/kanderson in directories faster94 and faster95.
--
Ken Anderson
Internet: ·········@bbn.com
BBN ST Work Phone: 617-873-3160
10 Moulton St. Home Phone: 617-643-0157
Mail Stop 6/4a FAX: 617-873-2794
Cambridge MA 02138
USA
········@lager.bbn.com (Ken Anderson) writes:
>>
>> (*) Cleverest-title Award: "Courage in Profiles" :-)
>>
>You can not get that another other performance related stuff from
>openmap.bbn.com pub/kanderson in directories faster94 and faster95.
I copied the profile.ps file, but neither ghostview nor any
PostScipt printer I can find is able to deal with it. This is
odd, since it seems to have been produced by dvips.
Anyway, I'm not any kind of PostScript expert, so at this point
I have to give up.
-- jeff
From: Arthur Lemmens
Subject: Re: Lisp faster than C (profile.ps)
Date:
Message-ID: <45dnlv$e0b@News.Simplex.NL>
In <··········@cogsci.ed.ac.uk>, ····@cogsci.ed.ac.uk (Jeff Dalton) writes:
>>You can get that and other performance related stuff from
>>openmap.bbn.com pub/kanderson in directories faster94 and faster95.
>
>I copied the profile.ps file, but neither ghostview nor any
>PostScipt printer I can find is able to deal with it. This is
>odd, since it seems to have been produced by dvips.
>
>Anyway, I'm not any kind of PostScript expert, so at this point
>I have to give up.
Maybe something went wrong during copying. I also downloaded
profile.ps and had no problems printing it with Ghostscript (on OS/2)
on a HP Laserjet 4L.
Try again, it's an interesting article.
-----------------------------------
Arthur Lemmens (·······@simplex.nl)