Hello everyone!
I have written the following procedure in Lisp:
(defun copy (STRUCTURE)
(if (null STRUCTURE) nil
(if (not (listp STRUCTURE))
STRUCTURE
(if (listp (car STRUCTURE))
(cons (copy (car STRUCTURE)) (copy (cdr STRUCTURE)))
(cons (car STRUCTURE) (copy (cdr STRUCTURE)))))))
which should make a new copy of a structure.
It works, but it's relatively slow.
Is there any way to make it faster?
(except avoiding the first "if" - I just saw that it should work without,
but this won't save much time)
Thanks in advance!
"Luke" <···················@gmx.de> writes:
> I have written the following procedure in Lisp:
>
> (defun copy (STRUCTURE)
> (if (null STRUCTURE) nil
> (if (not (listp STRUCTURE))
> STRUCTURE
> (if (listp (car STRUCTURE))
> (cons (copy (car STRUCTURE)) (copy (cdr STRUCTURE)))
> (cons (car STRUCTURE) (copy (cdr STRUCTURE)))))))
>
> which should make a new copy of a structure.
>
> It works, but it's relatively slow.
> Is there any way to make it faster?
> (except avoiding the first "if" - I just saw that it should work without,
> but this won't save much time)
>
> Thanks in advance!
[I hope this isn't homework. If it is, you should say so.]
What you have is adequately efficient, although lacks a bit in style.
If it's running slowly, it may be because you haven't compiled it?
If you are working interactively, some implementations will compile
definitions you make incrementally and others will not. You can,
when working interpreted, do
(compile 'copy)
to force the COPY definition you've just typed in to get compiled.
Stylistically, instead of testing (listp (car structure)) you should
do the test as part of coy itself to avoid the awkward IF at the end.
Consider
(defun copy-shrub (structure)
(typecase structure
((null) nil)
((cons) (cons (copy-shrub (car structure))
(copy-shrub (cdr structure))))
(otherwise structure)))
However, you might want to check out the built-in function COPY-TREE.
Before you do a lot of programming with this kind of "blind copying",
though, I recommend you take some time out to think about the
philosophical issues raised in:
http://www.nhplace.com/kent/PS/EQUAL.html
Kent M Pitman <······@world.std.com> writes:
> (typecase structure
> ((null) nil)
> ((cons) (cons (copy-shrub (car structure))
> (copy-shrub (cdr structure))))
> (otherwise structure)))
Oops. As Barry points out, the first case isn't needed, since it's the
same as the otherwise case.
Btw, I wanted to add another remark: A list is an abstraction that does
not "peer into" its elements. The subject line here talks about copying
"lists". When you copy a list [see COPY-LIST], you are only copying the
toplevel backbone of conses, not descending into the cars of any of the
lists. When you copy a tree, you are descending both right and left halves
of conses without respecting the tree abstraction. Resist the urge to
think of a list as containing the elements of its elements. That is,
the list ((A B) (C D)) does not contain any of A, B, C, or D. It only
contains two lists--the list (A B) and the list (C D). Whereas the tree
abtsraction ((A B) (C D)) contains the tree ((A B) . ((C D))),
the left half of which contains the tree (A . (B)) and the right half of
which contains the tree ((C D)). (A . (B)) is a tree with left half A
and right half (B), while ((C D)) is a tree with left half (C D) and right
half NIL. And so on. So the tree ((A B) (C D)) does contain A, B, C, and
D, and NIL as terminal leaf nodes, as well as (A B), ((C D)), (C D), (B),
and (D) as non-terminal branches.
In article <············@online.de>, Luke <···················@gmx.de> wrote:
>Hello everyone!
>
>I have written the following procedure in Lisp:
>
>(defun copy (STRUCTURE)
> (if (null STRUCTURE) nil
> (if (not (listp STRUCTURE))
> STRUCTURE
> (if (listp (car STRUCTURE))
> (cons (copy (car STRUCTURE)) (copy (cdr STRUCTURE)))
> (cons (car STRUCTURE) (copy (cdr STRUCTURE)))))))
>
>which should make a new copy of a structure.
>
>It works, but it's relatively slow.
Compared to what? It's basically equivalent to the built-in COPY-TREE.
>Is there any way to make it faster?
>(except avoiding the first "if" - I just saw that it should work without,
>but this won't save much time)
You don't need the third IF. Just recurse into the CAR -- if it's not a
list, COPY will simply return it.
You can also use CONSP instead of LISTP, and then get rid of the NULL test.
(defun copy (structure)
(if (consp structure)
(cons (copy (car structure)) (copy (cdr structure)))
structure))
--
Barry Margolin, ··············@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
> (except avoiding the first "if" - I just saw that it should work without,
> but this won't save much time)
It won't work without the first "if", becuase nil is a list!
"Luke" <···················@gmx.de> wrote in message
·················@online.de...
> Hello everyone!
>
> I have written the following procedure in Lisp:
>
> (defun copy (STRUCTURE)
> (if (null STRUCTURE) nil
> (if (not (listp STRUCTURE))
> STRUCTURE
> (if (listp (car STRUCTURE))
> (cons (copy (car STRUCTURE)) (copy (cdr STRUCTURE)))
> (cons (car STRUCTURE) (copy (cdr STRUCTURE)))))))
A few remarks:
1) The code is not correctly indented, which makes it quite hard to
understand.
2) The function name "COPY" makes the reader think it can copy any kind of
data, which is wrong. It copies trees (lists that may contain lists), so it
would be better named COPY-TREE.
3) The parameter name "STRUCTURE" makes the reader think s/he can pass a
structure (record) to the function, which is wrong.
4) The code can be simplified:
(defun copy-tree (tree)
(if (atom tree)
tr
(cons (copy-tree (car tr))
(copy-tree (cdr tr)))))
5) The function COPY-TREE already exists in Common Lisp:
http://www.lispworks.com/reference/HyperSpec/Body/f_cp_tre.htm#copy-tree
--
Matthieu Villeneuve
Eero Torri <··········@pandora.be> writes:
> Luke,
>
> Would this be any faster?
>
> (defun cpy ( x )
> (mapcar #'(lambda(i) (if (consp i) (cpy i) i)) x))
This assumes that it will be given non-atoms to start with.
It also assumes that every non-atom is a proper list (does not loop
forever circularly, does not end in a non-null atom).
As to speed, you're talking issues that vary per implementation. It
is not reasonable or appropriate to talk about speed absent discussion
of specific implementations. What is fast on one implementation may
not be as fast on another. On the other hand, the kinds of minute
differences we're talking about are such that the variation really
doesn't matter in 99% of cases anyway...
Kent M Pitman wrote:
>This assumes that it will be given non-atoms to start with.
>
>It also assumes ...
>
Sure, but I don't know what implementation Luke was using and what is
the exact nature of the question (homework/real work/quick-n'-dirty).
Luke asked for speed and not safety? My proposal might or might not be
faster for Luke in his environment. That's why I asked if it is faster
for him.
--
Eero Torri