The at the end of this post surprised me (not too much because I
figured last would have to be optimized in order for it to be used so
frequently). The fact that last does not slow down with larger lists
means it's not defined recursively like:
(defun slow-last (l)
(cond ((null l) nil)
((null (cdr l)) (list (car l)))
(t (slow-last (cdr l))))
My question is what is going on behind the scenes in the
implementation of #'last here? Does the implementation have access to
data structures I don't know about?
Below was my test to "prove" last doesn't use recursion
(defvar *long-list* '(0))
(defvar *short-list* '(1 2 3 4))
(dotimes (i 10000)
(append *long-list*
(1+ (car (last *long-list*)))))
(defun last-long(iter)
(dotimes (i iter)
(last *long-list*)))
(defun last-short(iter)
(dotimes (i iter)
(last *short-list*)))
;;(compile-file "test-last.lisp")
;;(load "test-last.fasl")
CL-USER> (time (last-long 10000000))
Evaluation took:
0.325 seconds of real time
0.304019 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
2,736 bytes consed.
NIL
CL-USER> (time (last-short 10000000))
Evaluation took:
0.328 seconds of real time
0.300019 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
jrwats <······@gmail.com> writes:
> The at the end of this post surprised me (not too much because I
> figured last would have to be optimized in order for it to be used so
> frequently). The fact that last does not slow down with larger lists
> means it's not defined recursively like:
>
> (defun slow-last (l)
> (cond ((null l) nil)
> ((null (cdr l)) (list (car l)))
> (t (slow-last (cdr l))))
>
> My question is what is going on behind the scenes in the
> implementation of #'last here? Does the implementation have access to
> data structures I don't know about?
No. It is linear.
The problem is that your test doesn't prove what you think it does.
Hint:
Evaluate *long-list* and *short-list* after loading your file.
Extra credit assignment: Build up *long-list* more efficiently.
> Below was my test to "prove" last doesn't use recursion
>
> (defvar *long-list* '(0))
> (defvar *short-list* '(1 2 3 4))
>
> (dotimes (i 10000)
> (append *long-list*
> (1+ (car (last *long-list*)))))
>
>
> (defun last-long(iter)
> (dotimes (i iter)
> (last *long-list*)))
>
> (defun last-short(iter)
> (dotimes (i iter)
> (last *short-list*)))
>
> ;;(compile-file "test-last.lisp")
> ;;(load "test-last.fasl")
>
> CL-USER> (time (last-long 10000000))
> Evaluation took:
> 0.325 seconds of real time
> 0.304019 seconds of user run time
> 0.0 seconds of system run time
> 0 calls to %EVAL
> 0 page faults and
> 2,736 bytes consed.
> NIL
> CL-USER> (time (last-short 10000000))
> Evaluation took:
> 0.328 seconds of real time
> 0.300019 seconds of user run time
> 0.0 seconds of system run time
> 0 calls to %EVAL
> 0 page faults and
> 0 bytes consed.
> NIL
--
Thomas A. Russ, USC/Information Sciences Institute
umm...
CL-USER> *long-list*
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
27
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
51
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
75
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
117
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
135
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
153
...
CL-USER> *short-list*
(1 2 3 4)
yeah just realized I had updated/debugged my code *after* I copied and
pasted
My code *was*
(dotimes (i 10000)
(setf *long-list*
(append *long-list*
(list (1+ (car (last *long-list*)))))))
when I tested - and before I copied and pasted the times. The times
are still roughly the same:
CL-USER> (time (last-long 1000000))
Evaluation took:
0.036 seconds of real time
0.028002 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
CL-USER> (time (last-short 1000000))
Evaluation took:
0.035 seconds of real time
0.036002 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
Changed definitions of last-long and last-short to not take arguments
but have a fixed dotimes number:
CL-USER> (compile-file "workspace/fun/lisp/test-last.lisp")
; compiling file "/home/johnw/workspace/fun/lisp/test-
last.lisp" (written 19 SEP 2008 01:01:37 AM):
; compiling (DEFPARAMETER *LONG-LIST* ...)
; compiling (DEFPARAMETER *SHORT-LIST* ...)
; compiling (PRINT "appending *long-list*")
; compiling (DOTIMES (I 10000) ...)
; compiling (PRINT "done appending *long-list*")
; compiling (DEFUN LAST-LONG ...)
; compiling (DEFUN LAST-SHORT ...)
; compiling (DEFUN BAD-LAST ...)
; /home/johnw/workspace/fun/lisp/test-last.fasl written
; compilation finished in 0:00:00
#P"/home/johnw/workspace/fun/lisp/test-last.fasl"
NIL
NIL
CL-USER> (load "workspace/fun/lisp/test-last.fasl")
"appending *long-list*"
"done appending *long-list*"
STYLE-WARNING: redefining LAST-LONG in DEFUN
STYLE-WARNING: redefining LAST-SHORT in DEFUN
STYLE-WARNING: redefining BAD-LAST in DEFUN
T
CL-USER> (length *long-list*)
10001
CL-USER> (length *short-list*)
4
CL-USER> (time (last-short))
Evaluation took:
0.813 seconds of real time
0.808051 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
CL-USER> (time (last-long))
Evaluation took:
0.644 seconds of real time
0.632039 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
and I'm still impressed that last is unaffected - a bit bewildered
actually. Even if it doesn't use recursion - it's still cdr-ing down
the list (in a loop) and seemingly running (- (length *long-lsit*)
(length *short-list*)) iterations on EACH for loop...
In article
<····································@z11g2000prl.googlegroups.com>,
jrwats <······@gmail.com> wrote:
> umm...
> CL-USER> *long-list*
> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
> 27
> 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
> 51
> 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
> 75
> 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
> 99
> 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
> 117
> 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
> 135
> 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
> 153
> ...
> CL-USER> *short-list*
> (1 2 3 4)
CL-USER 30 > (defparameter *l1* (list 1 2 3 4))
*L1*
CL-USER 31 > (defparameter *l2* (loop repeat 1000000 collect 1))
*L2*
CL-USER 32 > (defun test (list) (last list))
TEST
CL-USER 33 > (compile 'test)
TEST
NIL
NIL
CL-USER 34 > (time (test *l1*))
Timing the evaluation of (TEST *L1*)
User time = 0.000
System time = 0.000
Elapsed time = 0.001
Allocation = 0 bytes
0 Page faults
(4)
CL-USER 35 > (time (test *l2*))
Timing the evaluation of (TEST *L2*)
User time = 0.004
System time = 0.000
Elapsed time = 0.005
Allocation = 0 bytes
0 Page faults
the first example is supposed to be very fast.
it is certainly faster than the resolution of TIME.
The second example shows that LAST called with
a million element list takes 0.004 seconds
on my computer (a Core 2 Duo MacBook Pro).
You can imagine that some of the speed depends somehow
on the nature of the list. If it is fresh allocated
and the CONS cells are allocated one after another,
then it will be faster than a list whose cons
cells are randomly spread over the memory. The
latter could mean cache/page misses.
You can see that Lisp nowadays is quite fast and even
costly operations like LAST on long lists
sometimes does not matter. Still it is useful to
understand that LAST has a time complexity of O(n).
There is no magic behind LAST. It just happens
to run on 'fast' computers nowadays.
--
http://lispm.dyndns.org/
j> and I'm still impressed that last is unaffected - a bit bewildered
j> actually.
you cannot measure abstract performance in vacuum if you're dealing
with optimizing compiler -- compiler can detect you're doing nothing
(result from your function is always NIL)
and actually do nothing, exactly what you mean!
you can trick compiler into actually doing computations if you
actually return computation result from your function.
for example:
(defun test (list)
(let (r)
(dotimes (i 1000)
(setf r (last list)))
r)
CL-USER> (length *l1*)
4
CL-USER> (length *l2*)
1000000
CL-USER> (time (test *l1*))
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
(4)
CL-USER> (time (test *l2*))
Evaluation took:
2.826 seconds of real time
2.824177 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
8,904 bytes consed.
(1)
now, for example, simplier test function that returns NIL:
(defun test (list)
(let (r)
(dotimes (i 1000)
(setf r (last list))))
and compiler can optimize it eliminating LAST calls:
STIXOBJ> (time (test *l2*))
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
NIL
> (defun test (list)
> (let (r)
> (dotimes (i 1000)
> (setf r (last list)))
> r)
So this was the source of my bewilderment. A fancy sbcl compiler.
Thanks everyone for the responses. Rainer and Pascal, thanks for the
fine code.
P� Thu, 18 Sep 2008 17:45:38 +0200, skrev jrwats <······@gmail.com>:
> The at the end of this post surprised me (not too much because I
> figured last would have to be optimized in order for it to be used so
> frequently). The fact that last does not slow down with larger lists
> means it's not defined recursively like:
>
> (defun slow-last (l)
> (cond ((null l) nil)
> ((null (cdr l)) (list (car l)))
> (t (slow-last (cdr l))))
>
> My question is what is going on behind the scenes in the
> implementation of #'last here? Does the implementation have access to
> data structures I don't know about?
>
> Below was my test to "prove" last doesn't use recursion
>
> (defvar *long-list* '(0))
> (defvar *short-list* '(1 2 3 4))
>
> (dotimes (i 10000)
> (append *long-list*
> (1+ (car (last *long-list*)))))
>
>
No it's tail recursive. So the compiler compiles it into a loop.
http://siddhi.blogspot.com/2006/04/recursion-part-2-tail-recursion.html
--------------
John Thingstad
In article
<····································@k36g2000pri.googlegroups.com>,
jrwats <······@gmail.com> wrote:
> The at the end of this post surprised me (not too much because I
> figured last would have to be optimized in order for it to be used so
> frequently). The fact that last does not slow down with larger lists
> means it's not defined recursively like:
>
> (defun slow-last (l)
> (cond ((null l) nil)
> ((null (cdr l)) (list (car l)))
> (t (slow-last (cdr l))))
>
> My question is what is going on behind the scenes in the
> implementation of #'last here? Does the implementation have access to
> data structures I don't know about?
>
> Below was my test to "prove" last doesn't use recursion
>
> (defvar *long-list* '(0))
> (defvar *short-list* '(1 2 3 4))
>
> (dotimes (i 10000)
> (append *long-list*
> (1+ (car (last *long-list*)))))
>
>
> (defun last-long(iter)
> (dotimes (i iter)
> (last *long-list*)))
>
> (defun last-short(iter)
> (dotimes (i iter)
> (last *short-list*)))
>
> ;;(compile-file "test-last.lisp")
> ;;(load "test-last.fasl")
>
> CL-USER> (time (last-long 10000000))
> Evaluation took:
> 0.325 seconds of real time
> 0.304019 seconds of user run time
> 0.0 seconds of system run time
> 0 calls to %EVAL
> 0 page faults and
> 2,736 bytes consed.
> NIL
> CL-USER> (time (last-short 10000000))
> Evaluation took:
> 0.328 seconds of real time
> 0.300019 seconds of user run time
> 0.0 seconds of system run time
> 0 calls to %EVAL
> 0 page faults and
> 0 bytes consed.
> NIL
You need to make sure that you measure something useful.
APPEND is a function without side effects. It
returns a new list.
You have actually appended something, but forgot
to update the variable. So the list is not long and
it is not even a proper list.
Second: if you want to append two lists, then
you have to pass two lists. Your second argument
to APPEND is a number, not a list.
Third: using APPEND in a loop or a recursive function is
bad bad bad.
Use something like:
(defparameter *long-list* (loop for i below 10000 collect i))
or
(defvar *long-list* nil)
(dotimes (i 10000) (push i *long-list*))
LAST will not use recursion. Because recursion is limited
by the maximum stack depth. LAST will be implemented
by some loop.
Like this implementation of LAST from CCL:
(defun last (list &optional (n 1))
"Return the last N conses (not the last element!) of a list."
(if (and (typep n 'fixnum)
(>= (the fixnum n) 0))
(locally (declare (fixnum n))
(do* ((checked-list list (cdr checked-list))
(returned-list list)
(index 0 (1+ index)))
((atom checked-list) returned-list)
(declare (type index index))
(if (>= index n)
(pop returned-list))))
(if (and (typep n 'bignum)
(> n 0))
(require-type list 'list)
(report-bad-arg n 'unsigned-byte))))
--
http://lispm.dyndns.org/
jrwats <······@gmail.com> writes:
> The at the end of this post surprised me (not too much because I
> figured last would have to be optimized in order for it to be used so
> frequently). The fact that last does not slow down with larger lists
> means it's not defined recursively like:
It does slow down on long lists. Whatever the implementation, be it
recursive or iterative. (Let's assume the implementation knows
whether it can use the stack to process random data).
> (defun slow-last (l)
> (cond ((null l) nil)
> ((null (cdr l)) (list (car l)))
> (t (slow-last (cdr l))))
>
> My question is what is going on behind the scenes in the
> implementation of #'last here?
LAST is specified to
... returns the last n conses (not the last n elements) of list).
Not the last cons of _some_ new list, but of its argument.
So a correct recursive implementation of LAST would be:
(defun recursive-last (list &optional (n 1))
(labels ((recur (list)
(if (atom list)
(values list n)
(multiple-value-bind (result count) (recur (cdr list))
(if (zerop count)
(values result count)
(values list (1- count)))))))
(values (recur list))))
C/USER[59]> (let ((list '(1 2 3 4 5 6))) (dotimes (n 8 (values)) (print (list list (RECURSIVE-LAST list n)))))
((1 2 3 4 5 6) NIL)
((1 2 3 4 5 . #1=(6)) #1#)
((1 2 3 4 . #1=(5 6)) #1#)
((1 2 3 . #1=(4 5 6)) #1#)
((1 2 . #1=(3 4 5 6)) #1#)
((1 . #1=(2 3 4 5 6)) #1#)
(#1=(1 2 3 4 5 6) #1#)
(#1=(1 2 3 4 5 6) #1#)
C/USER[60]>
Here is an iterative-last using O(n) in space and O(length(list)) in time.
(defun iterative-last (list &optional (n 1))
(when (plusp n)
(loop
:with lasts = (make-array (1+ n))
:with r = (- n)
:with l = 0
:for cell :on list
;; :do (print (list n r l cell))
:do (setf (aref lasts l) cell
l (if (= n l) 0 (1+ l))
r (if (= n r) 0 (1+ r)))
:finally (return (if (minusp r)
list ; (< (length list) n)
(aref lasts r))))))
ITERATIVE-LAST
C/USER[77]> (let ((list '(1 2 3 4 5 6))) (dotimes (n 8 (values)) (print (list list (iterative-last list n)))))
((1 2 3 4 5 6) NIL)
((1 2 3 4 5 . #1=(6)) #1#)
((1 2 3 4 . #1=(5 6)) #1#)
((1 2 3 . #1=(4 5 6)) #1#)
((1 2 . #1=(3 4 5 6)) #1#)
((1 . #1=(2 3 4 5 6)) #1#)
(#1=(1 2 3 4 5 6) #1#)
(#1=(1 2 3 4 5 6) #1#)
C/USER[78]>
> Does the implementation have access to
> data structures I don't know about?
No.
--
__Pascal Bourguignon__