wilk@fife.cs.cornell.edu (Michael Wilk) (10/14/90)
Here are some timing results on suggested solutions for the "mirror" function:
I won't reveal the huge list I tried this on, but trust me: It was big.
-------------------------------------------------------------------------------
My effort:
(defun mirror (x)
(if (atom x)
x
(let ((result nil))
(dolist (item x)
(push (mirror item) result))
result)))
Elapsed Real Time = 10.66 seconds
Total Run Time = 10.57 seconds
User Run Time = 10.55 seconds
System Run Time = 0.02 seconds
Process Page Faults = 131
Dynamic Bytes Consed = 0
Ephemeral Bytes Consed = 1,693,584
-------------------------------------------------------------------------------
By Eliot Handelman and Raja Sooriamurthi, modified slightly:
(defun mirror (x)
(if (atom x)
x
(append (mirror (rest x)) (list (mirror (first x))))))
Elapsed Real Time = 6.52 seconds
Total Run Time = 6.43 seconds
User Run Time = 6.43 seconds
System Run Time = 0.00 seconds
Process Page Faults = 1
Dynamic Bytes Consed = 0
Ephemeral Bytes Consed = 2,030,088
-------------------------------------------------------------------------------
By Noritake Yonezawa:
(defun mirror (x)
(if (atom x)
x
(reverse (mapcar #'mirror x))))
Elapsed Real Time = 2.62 seconds
Total Run Time = 2.52 seconds
User Run Time = 2.52 seconds
System Run Time = 0.00 seconds
Process Page Faults = 5
Dynamic Bytes Consed = 0
Ephemeral Bytes Consed = 986,984
-------------------------------------------------------------------------------
-Michael Wilk (wilk@cs.cornell.edu)raja@copper.ucs.indiana.edu (Raja Sooriamurthi) (10/14/90)
wilk@fife.cs.cornell.edu (Michael Wilk) writes: > Here are some timing results on suggested solutions for the "mirror" > function: I won't reveal the huge list I tried this on, but trust me: > It was big. [stats. deleted] Here is a CPSed form of the mirror function. Now all calls to the auxillary function mir are properly tail recursive and a scheme implementation (and some CL implementations) would optimize the recursive calls into jumps. Just out of curiosity I'd like to see how this version compares with the other ones. The code below is in Scheme where in I've used scheme's equivalent of the Y combinator, rec, to define mir. Could you convert this into Common Lisp and run it on your data set. - Raja raja@cs.indiana.edu (define mirror/k (lambda (l) ((rec mir (lambda (l k) (cond [(atom? l) (k l)] [else (mir (car l) (lambda (a) (mir (cdr l) (lambda (d) (k (append d (list a)))))))]))) l (lambda (v) v))))
yonezawa@cs.uiuc.edu (Noritake Yonezawa) (10/14/90)
In article <raja.655852887@copper> raja@copper.ucs.indiana.edu (Raja Sooriamurthi) writes: > Here is a CPSed form of the mirror function. Now all calls to the > auxillary function mir are properly tail recursive and a scheme > implementation (and some CL implementations) would optimize the > recursive calls into jumps. Here is another form of the mirror function. The auxillary functions are CPSed, but not tail recursive. I avoided using 'append'. Does anyone know better solution? (defun mirror (x) (labels ((f1 (x c) (if (atom x) (funcall c x) (f2 x nil c))) (f2 (x y c) (if (null x) (funcall c y) (f1 (car x) #'(lambda (z) (f2 (cdr x) (cons z y) c)))))) (f1 x #'identity))) -- Noritake Yonezawa [yonezawa@cs.uiuc.edu] Department of Computer Science University of Illinois at Urbana-Champaign