Page 2 of 2
Re: stuck
Posted: Sun Aug 29, 2010 8:53 pm
by nuntius
burton wrote:(dolist (sum (lst)
(sum 0))
(if (t(oddp lst))
(setq sum (+ 1 sum)
(
)
im not sure..
Close, but there are still a few oddities in your code.
DOLIST doesn't take the same parameter list as DO. The function prototype is
(DOLIST (var list [result]) body), where the result-form is optional. Use LET to create a counter outside the loop:
(let ((count 0)) ...). Then iterate over each item in a list:
(dolist (item list) ...).
I'm not sure what the first clause in your IF does. It should look something like
(if (oddp item) (incf count)), or preferably use WHEN for IF statements with no "else" clause.
[OT]: Recursion is the "Schemey" way to write code. It is not so popular in common lisp.
Re: stuck
Posted: Sun Aug 29, 2010 9:53 pm
by s-imp
Got'cha
Re: stuck
Posted: Mon Aug 30, 2010 3:18 pm
by findinglisp
s-imp wrote:Yeah, I thought about 'length', but I knew to avoid creating cons cells for a new list as you do get a performance penalty for it.
Thank you both for the info on tail-recursion. So my function is not tail recursive (as it calls #'+ last). I traced it and then disassembled it to see what was going on. Very interesting.
It should also be said that Common Lisp makes no guarantees around tail recursion; implementations are not required to be properly tail recursive. In practice, some are, but that's really outside the dictum of the standard. That stands in strong contrast to Scheme where every conforming implementation to RxRS is required to be properly tail recursive. As a result, Scheme tends to rely much more heavily on tail recursion to implement loops, whereas CL has a stronger set of iteration constructs (e.g., DO, DO*, DOLIST, LOOP, etc.).
Re: stuck
Posted: Mon Aug 30, 2010 3:21 pm
by Warren Wilkinson
Here are 5 ways of doing it. I added timing for SBCL on my computer without tweaking any optimization stuff.
Code: Select all
;; using a reduction
(defun odd-count1 (list) (reduce #.(lambda (acc i) (if (oddp i) (1+ acc) acc)) list :initial-value 0))
;; using 'loop'
(defun odd-count2 (list) (loop for i in list counting (oddp i)))
;; Using recursion
(defun odd-count3 (lst)
(if (null lst)
0
(+ (if (oddp (first lst)) 1 0)
(odd-count3 (rest lst)))))
;; using tail recursion
(defun odd-count4 (lst count) (if (null lst) count (odd-count4 (cdr lst) (if (oddp (car lst)) (1+ count) count))))
;; using destructive updates and jumps
(defun odd-count5 (lst)
(let ((count (the fixnum 0)))
(tagbody :start (when lst (when (oddp (car lst)) (incf count)) (setf lst (cdr lst)) (go :start)))
count))
(defvar *data* (loop repeat 1024 collecting (random 256)))
(time (dotimes (i 1000)(odd-count1 *data*))) ;; 0.038 seconds
(time (dotimes (i 1000)(odd-count2 *data*))) ;; 0.023 seconds
(time (dotimes (i 1000)(odd-count3 *data*))) ;; 0.048 seconds
(time (dotimes (i 1000)(odd-count4 *data* 0))) ;; 0.031 seconds
(time (dotimes (i 1000)(odd-count5 *data*))) ;; 0.023 seconds
Re: stuck
Posted: Mon Aug 30, 2010 3:31 pm
by findinglisp
Warren Wilkinson wrote:Here are 5 ways of doing it. I added timing for SBCL on my computer without tweaking any optimization stuff.
Code: Select all
(time (dotimes (i 1000)(odd-count1 *data*))) ;; 0.038 seconds
(time (dotimes (i 1000)(odd-count2 *data*))) ;; 0.023 seconds
(time (dotimes (i 1000)(odd-count3 *data*))) ;; 0.048 seconds
(time (dotimes (i 1000)(odd-count4 *data* 0))) ;; 0.031 seconds
(time (dotimes (i 1000)(odd-count5 *data*))) ;; 0.023 seconds
The LOOP macro typically expands into a TAGBODY/GO under the hood, which explains why its performance is similar. If I remember right, SBCL also implements proper tail recursion, so ODD-COUNT4 also does well. Real recursion and REDUCE involve lots of true function calls, so there's higher overhead there.
IMO, LOOP is almost always a win and I tend to use it in preference to other styles, unless the problem screams for recursion (whether tail-recursion or not).
That said, find your style. Lisp allows a lot of different styles. Most code is not performance-critical.
-- Dave