Hello.
I'm studying Lisp and to understand better consing, function call,
etc.,
I played with a classical example I found in the great book "ANSI
Common Lisp":
(defun map-int (fn n)
"map-int takes a function fn and an integer n, and
returns a list of the results of calling the function
on the integers from 0 to n-1.
Example: (map-int #'identity 10)"
(let ((acc nil))
(dotimes (i n)
(push (funcall fn i) acc))
(nreverse acc)))
I tried to modify map-int: same result but I don't use nreverse.
(defun map-int2 (fn n) ; slower than map-int
"map-int2 takes a function fn and an integer n, and
returns a list of the results of calling the function
on the integers from 0 to n-1.
(push obj lst) -> (setf lst (cons obj lst))
(append-tail lst obj) -> (append lst (list obj))
Example: (map-int #'identity 10)"
(let ((acc nil))
(dotimes (i n)
(setf acc (append acc (list (funcall fn i)))))
acc))
Profiling the functions map-int and map-int2 with time, it seems
map-int2 is slower than map-int. I don't understand that.
Maybe in map-int2 I do a lot of consing and there is a use of
garbage collection too much (I use OpenMCL rel. 1.0).
Please, can you explain it?
Thanks in advance,
Alberto Santini
"Alberto Santini" <··············@gmail.com> writes:
> Hello.
>
> I'm studying Lisp and to understand better consing, function call,
> etc.,
> I played with a classical example I found in the great book "ANSI
> Common Lisp":
>
> (defun map-int (fn n)
> "map-int takes a function fn and an integer n, and
> returns a list of the results of calling the function
> on the integers from 0 to n-1.
> Example: (map-int #'identity 10)"
> (let ((acc nil))
> (dotimes (i n)
> (push (funcall fn i) acc))
> (nreverse acc)))
>
> I tried to modify map-int: same result but I don't use nreverse.
>
> (defun map-int2 (fn n) ; slower than map-int
> "map-int2 takes a function fn and an integer n, and
> returns a list of the results of calling the function
> on the integers from 0 to n-1.
> (push obj lst) -> (setf lst (cons obj lst))
> (append-tail lst obj) -> (append lst (list obj))
> Example: (map-int #'identity 10)"
> (let ((acc nil))
> (dotimes (i n)
> (setf acc (append acc (list (funcall fn i)))))
> acc))
>
> Profiling the functions map-int and map-int2 with time, it seems
> map-int2 is slower than map-int. I don't understand that.
> Maybe in map-int2 I do a lot of consing and there is a use of
> garbage collection too much (I use OpenMCL rel. 1.0).
>
> Please, can you explain it?
APPEND copies all its arguments but the last, therefore its O(n).
Using APPEND in a loop gives O(n�).
If you want to avoid reverse, then generate the elements in reversed order:
(defun map-int (f n)
(do* ((i (1- n) (1- i))
(r (list (funcall f i)) (cons (funcall f i) r)))
((zerop i) r)))
If you must still call f with the elements in order, then keep a
pointer to the tail:
(defun map-int (f n)
(do* ((i 0 (1+ i))
(r (cons nil nil))
(tail r (cdr tail)))
((>= i n) (cdr r))
(setf (cdr tail) (cons (funcall f i) nil))))
Perhaps this is what LOOP does? Who knows?
(defun map-int (f n)
(loop :for i :below n :collect (funcall f i))) ; seems to use nreverse, here.
(defun map-int (f n)
(loop :for i :below n :nconc (cons (funcall f i) nil))) ; seems to keep
; a pointer to the tail, here.
Note that the both the tail pointer and the NREVERSE solutions have
the same time and space complexity, and that one or the other can be
better on a specific architecture, depending on the number of
registers and the size of the cache and of the data. In general,
NREVERSE gives better results.
--
__Pascal Bourguignon__ http://www.informatimago.com/
You're always typing.
Well, let's see you ignore my
sitting on your hands.
Pretty good, but try to break is up.
Suppose you had a function (let's call it IOTA, for APLers lurking
around) that produces a list of integers from 0 to N-1
cl-prompt> (iota 5)
(0 1 2 3 4)
then you function just becomes
(defun map-int (f n)
(mapcar f (iota n))
Cheers
--
Marco
Alberto Santini wrote:
> Hello.
>
> I'm studying Lisp and to understand better consing, function call,
> etc.,
> I played with a classical example I found in the great book "ANSI
> Common Lisp":
>
> (defun map-int (fn n)
> "map-int takes a function fn and an integer n, and
> returns a list of the results of calling the function
> on the integers from 0 to n-1.
> Example: (map-int #'identity 10)"
> (let ((acc nil))
> (dotimes (i n)
> (push (funcall fn i) acc))
> (nreverse acc)))
>
> I tried to modify map-int: same result but I don't use nreverse.
>
> (defun map-int2 (fn n) ; slower than map-int
> "map-int2 takes a function fn and an integer n, and
> returns a list of the results of calling the function
> on the integers from 0 to n-1.
> (push obj lst) -> (setf lst (cons obj lst))
> (append-tail lst obj) -> (append lst (list obj))
> Example: (map-int #'identity 10)"
> (let ((acc nil))
> (dotimes (i n)
> (setf acc (append acc (list (funcall fn i)))))
> acc))
>
> Profiling the functions map-int and map-int2 with time, it seems
> map-int2 is slower than map-int. I don't understand that.
> Maybe in map-int2 I do a lot of consing and there is a use of
> garbage collection too much (I use OpenMCL rel. 1.0).
>
> Please, can you explain it?
>
> Thanks in advance,
> Alberto Santini
>