I need to write a Lisp function which takes a list and returns a replicate
of the list n times. i.e. (setq l'(a b c d)) and suppouse n=3 then the
output
is (a b c d a b c d a b c d)
Thanks
Steven Acosta
--
Support free trade
In article <···················@sacosta.port.net>, ·······@interport.net wrote:
> I need to write a Lisp function which takes a list and returns a replicate
> of the list n times. i.e. (setq l'(a b c d)) and suppouse n=3 then the
> output
> is (a b c d a b c d a b c d)
That's an easy question. Which School is it?
Rainer Joswig
In article <···················@sacosta.port.net> ··@itt.com (MaC_Q) writes:
> I need to write a Lisp function which takes a list and returns a replicate
> of the list n times. i.e. (setq l'(a b c d)) and suppouse n=3 then the
> output is (a b c d a b c d a b c d)
(defun replicate (n l)
(loop repeat n append l))
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
MaC_Q (··@itt.com) wrote:
: I need to write a Lisp function which takes a list and returns a replicate
: of the list n times. i.e. (setq l'(a b c d)) and suppouse n=3 then the
: output
: is (a b c d a b c d a b c d)
(defun replicate (list n)
(when (<= n 0)
(return nil)
)
(append (replicate list (1- n)) list)
)
Ciao
Chris
--
+------------------------------------------------------+
| Christian Betz Artificial Intelligence |
| beats real stupidy |
| e-mail ····@ki-server.informatik.uni-wuerzburg.de |
| 97737 Gem"unden - Tel: 09351/8976 - Fax: 09351/8569 |
+------------------------------------------------------+
In article <··········@winx03.informatik.uni-wuerzburg.de>,
betz%/etc/HOSTNAME (Christian Betz) wrote:
> MaC_Q (··@itt.com) wrote:
> : I need to write a Lisp function which takes a list and returns a replicate
> : of the list n times. i.e. (setq l'(a b c d)) and suppouse n=3 then the
> : output
> : is (a b c d a b c d a b c d)
>
> (defun replicate (list n)
> (when (<= n 0)
> (return nil)
> )
> (append (replicate list (1- n)) list)
> )
This is not valid Common Lisp and it is slow as hell.
> Error: While compiling REPLICATE :
> Can't RETURN-FROM block : NIL.
> Type Command-. to abort.
See the Restarts� menu item for further choices.
Given that you can deliver a working version,
can you do it without APPEND?
What is the complexity of your REPLICATE function?
(defun replicate (list n)
(if (<= n 0)
nil
(append (replicate list (1- n)) list)))
(let ((list '(1 2 3 4 5 6 7 8 9 10)))
(loop for n in '(10 20 40 80 160 320)
do (time (replicate list n)))
(values))
(REPLICATE LIST 10) took 2 milliseconds (0.002 seconds) to run.
3,600 bytes of memory allocated.
(REPLICATE LIST 20) took 3 milliseconds (0.003 seconds) to run.
15,200 bytes of memory allocated.
(REPLICATE LIST 40) took 43 milliseconds (0.043 seconds) to run.
Of that, 27 milliseconds (0.027 seconds) was spent in GC.
62,400 bytes of memory allocated.
(REPLICATE LIST 80) took 258 milliseconds (0.258 seconds) to run.
Of that, 102 milliseconds (0.102 seconds) were spent in The Cooperative
Multitasking Experience.
72 milliseconds (0.072 seconds) was spent in GC.
252,800 bytes of memory allocated.
(REPLICATE LIST 160) took 697 milliseconds (0.697 seconds) to run.
Of that, 39 milliseconds (0.039 seconds) were spent in The Cooperative
Multitasking Experience.
350 milliseconds (0.350 seconds) was spent in GC.
1,017,600 bytes of memory allocated.
(REPLICATE LIST 320) took 3,110 milliseconds (3.110 seconds) to run.
Of that, 230 milliseconds (0.230 seconds) were spent in The Cooperative
Multitasking Experience.
1,670 milliseconds (1.670 seconds) was spent in GC.
4,083,200 bytes of memory allocated.
What does this mean?
A different implementation of REPLICATE gives:
(REPLICATE LIST 10) took 0 milliseconds (0.000 seconds) to run.
800 bytes of memory allocated.
(REPLICATE LIST 20) took 0 milliseconds (0.000 seconds) to run.
1,600 bytes of memory allocated.
(REPLICATE LIST 40) took 1 milliseconds (0.001 seconds) to run.
Of that, 1 milliseconds (0.001 seconds) were spent in The Cooperative
Multitasking Experience.
3,200 bytes of memory allocated.
(REPLICATE LIST 80) took 1 milliseconds (0.001 seconds) to run.
6,400 bytes of memory allocated.
(REPLICATE LIST 160) took 7 milliseconds (0.007 seconds) to run.
12,800 bytes of memory allocated.
(REPLICATE LIST 320) took 3 milliseconds (0.003 seconds) to run.
25,600 bytes of memory allocated.
Lisp is slow??? Yes, if you use APPEND without knowing what you
are doing!
Rainer Joswig
Rainer Joswig (······@lavielle.com) wrote:
: In article <··········@winx03.informatik.uni-wuerzburg.de>,
: betz%/etc/HOSTNAME (Christian Betz) wrote:
: (defun replicate (list n)
: (if (<= n 0)
: nil
: (append (replicate list (1- n)) list)))
: (let ((list '(1 2 3 4 5 6 7 8 9 10)))
: (loop for n in '(10 20 40 80 160 320)
: do (time (replicate list n)))
: (values))
: What does this mean?
: A different implementation of REPLICATE gives:
: (REPLICATE LIST 10) took 0 milliseconds (0.000 seconds) to run.
: 800 bytes of memory allocated.
: (REPLICATE LIST 20) took 0 milliseconds (0.000 seconds) to run.
: 1,600 bytes of memory allocated.
: (REPLICATE LIST 40) took 1 milliseconds (0.001 seconds) to run.
: Of that, 1 milliseconds (0.001 seconds) were spent in The Cooperative
: Multitasking Experience.
: 3,200 bytes of memory allocated.
: (REPLICATE LIST 80) took 1 milliseconds (0.001 seconds) to run.
: 6,400 bytes of memory allocated.
: (REPLICATE LIST 160) took 7 milliseconds (0.007 seconds) to run.
: 12,800 bytes of memory allocated.
: (REPLICATE LIST 320) took 3 milliseconds (0.003 seconds) to run.
: 25,600 bytes of memory allocated.
: Lisp is slow??? Yes, if you use APPEND without knowing what you
: are doing!
(defun my-replicate2 (list n)
(let ((new-list nil)
(help-list (reverse list)))
(dotimes (i n)
(dolist (elem help-list)
(setq new-list (cons elem new-list))
)
)
new-list
)
)
;-)
Chris
--
+------------------------------------------------------+
| Christian Betz Artificial Intelligence |
| beats real stupidy |
| e-mail ····@ki-server.informatik.uni-wuerzburg.de |
| 97737 Gem"unden - Tel: 09351/8976 - Fax: 09351/8569 |
+------------------------------------------------------+
In article <··········@winx03.informatik.uni-wuerzburg.de>,
····@cip.informatik.uni-wuerzburg.de (Christian Betz) wrote:
> (defun my-replicate2 (list n)
> (let ((new-list nil)
> (help-list (reverse list)))
>
> (dotimes (i n)
> (dolist (elem help-list)
> (setq new-list (cons elem new-list))
> )
> )
> new-list
> )
> )
>
> ;-)
How about something like (given that the CL compiler can optimize
this):
(defun replicate (list n)
(labels ((replicate-internal (new-list n)
(if (zerop n)
new-list
(replicate-internal (append list new-list) (1- n)))))
(replicate-internal nil n)))
The original version with a small modification is also
not that bad.
(defun replicate (list n)
(if (<= n 0)
nil
(append list (replicate list (1- n)))))
Rainer Joswig
Christian Betz wrote:
>(defun replicate (list n)
> (when (<= n 0)
> (return nil)
> )
> (append (replicate list (1- n)) list)
>)
Well, if you are going to do his homework for him, make it tail-recursive,
like every other definition in his textbook.
(append list (replicate list (1- n)))
In article <··········@news2.delphi.com>,
John Strohm <·············@BIX.com> wrote:
...
...
>
>Well, if you are going to do his homework for him, make it tail-recursive,
>like every other definition in his textbook.
>
> (append list (replicate list (1- n)))
The above won't make the original code tail recursive. The recursive
call to REPLICATE will be invoked before the call to APPEND does.
Therefore there is "work" still pending... therefore not tail.
However, Macintosh Common Lisp will ( and others perhaps could ) take
that non-tail version, do the tail transformation, and compile to the
equivalent tail code automagically for you.... :-) You'll get negligible
differences is you compile both (tail and augmentive) versions of the
the above code with MCL.
As pointed out in another post the above will at least give modest
improvements over the "original" version even if the compiler isn't
as "smart" as MCL's. You only have to deal with the stack overhead
at that point.
In case folks haven't written their own version of APPEND ( or read the
specification for it ) the first argument to the function is duplicated.
In the original version, the result of the recursive call is duplicated at
each step. A significant amount of redundant computation is therefore
performed. Since the argument "order" doesn't matter in this case, simply
switching them is the prudent course of action.
--
Lyman S. Taylor Scully: "The answers are there, you just have
(·····@cc.gatech.edu) to know where to look for them."
Mulder: "That's why they put the "I" in FBI."