Hoy to copy a struct that represents a tree.
in [Lisp]
|
Prev: Reader ?
Next: translating cmucl command line to sbcl
From: Pascal J. Bourguignon on 23 Oct 2009 00:28 Vassil Nikolov <vnikolov(a)pobox.com> writes: > On Fri, 23 Oct 2009 03:22:21 +0200, pjb(a)informatimago.com (Pascal J. Bourguignon) said: >> ... >> (defun collect-nodes (tree) >> (if (null tree) >> '() >> (cons tree (append (collect-nodes (my-tree-l tree)) >> (collect-nodes (my-tree-c tree)) >> (collect-nodes (my-tree-r tree)))))) > > APPEND?! Do you have a use case where more performance is needed? Until then, APPEND. -- __Pascal Bourguignon__
From: Wade on 23 Oct 2009 01:01 I think the exercise is meant to use the existing structure capabilities. (defstruct (mytree (:conc-name) (:constructor make-mytree) (:constructor clone-tree (tree &aux (element (element tree)) (left (and (left tree) (clone-tree (left tree)))) (center (and (center tree) (clone-tree (center tree)))) (right (and (right tree) (clone-tree (right tree))))))) element (right nil) (center nil) (left nil)) CL-USER> (defparameter tree #s(mytree :element 1 :right #s(mytree :element 2 :right #s(mytree :element 4) :center #s(mytree :element 5) :left #s(mytree :element 6)) :center #s(mytree :element 3 :right #s(mytree :element 8) :center #s(mytree :element 9) :left #s(mytree :element 10)) :left #s(mytree :element 4 :right #s(mytree :element 11) :center #s(mytree :element 12)))) TREE CL-USER> (equal (clone-tree tree) tree) NIL CL-USER> (equalp (clone-tree tree) tree) T CL-USER> (pprint tree) #S(MYTREE :ELEMENT 1 :RIGHT #S(MYTREE :ELEMENT 2 :RIGHT #S(MYTREE :ELEMENT 4 :RIGHT NIL :CENTER NIL :LEFT NIL) :CENTER #S(MYTREE :ELEMENT 5 :RIGHT NIL :CENTER NIL :LEFT NIL) :LEFT #S(MYTREE :ELEMENT 6 :RIGHT NIL :CENTER NIL :LEFT NIL)) :CENTER #S(MYTREE :ELEMENT 3 :RIGHT #S(MYTREE :ELEMENT 8 :RIGHT NIL :CENTER NIL :LEFT NIL) :CENTER #S(MYTREE :ELEMENT 9 :RIGHT NIL :CENTER NIL :LEFT NIL) :LEFT #S(MYTREE :ELEMENT 10 :RIGHT NIL :CENTER NIL :LEFT NIL)) :LEFT #S(MYTREE :ELEMENT 4 :RIGHT #S(MYTREE :ELEMENT 11 :RIGHT NIL :CENTER NIL :LEFT NIL) :CENTER #S(MYTREE :ELEMENT 12 :RIGHT NIL :CENTER NIL :LEFT NIL) :LEFT NIL)) ; No value CL-USER>
From: Andy Chambers on 23 Oct 2009 08:29 On Oct 23, 5:27 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > > While using bare lists for random data structures such as tree nodes > is indeed practical for Q&D code and exploratory code, soon enough in > real applications you need a distinct data type such as a real > structure or a class. Please could you expand on what it is about structs/classes that makes them more suitable for real apps? Is it a performance thing? I just tried this on CLISP and was surprised to find that (getf plist :a) was faster than (my-struct-a struct :a). (defstruct my-struct a b c) (let ((struct (make-my-struct :a 1 :b 2 :c 3)) (plist (list :a 1 :b 2 :c 3)) (count 100000)) (time (progn (format t "Using plist...") (dotimes (n count) (getf plist :a)))) (time (progn (format t "Using struct...") (dotimes (n count) (my-struct-a struct))))) Cheers, Andy
From: Raffael Cavallaro on 23 Oct 2009 09:16 On 2009-10-23 08:29:05 -0400, Andy Chambers <achambers.home(a)googlemail.com> said: > Please could you expand on what it is about structs/classes that makes > them more suitable for real apps? He gave one reason at the end of his post: "But these lists cannot be discriminated by generic functions." -- Raffael Cavallaro
From: Pascal J. Bourguignon on 23 Oct 2009 10:12
Andy Chambers <achambers.home(a)googlemail.com> writes: > On Oct 23, 5:27�am, p...(a)informatimago.com (Pascal J. Bourguignon) > wrote: >> >> While using bare lists for random data structures such as tree nodes >> is indeed practical for Q&D code and exploratory code, soon enough in >> real applications you need a distinct data type such as a real >> structure or a class. > > Please could you expand on what it is about structs/classes that makes > them more suitable for real apps? > > Is it a performance thing? No, I had in mind generic functions, or in general, the ability to distinguish the types of your structures. For example, if you use lists or vectors instead of real structures or classes, you cannot define a distinct print-object method to display your data concisely and clearly. While debugging, it will be inconvenient to dump sometimes big, and indiscriminate lists. > I just tried this on CLISP and was surprised to find that (getf > plist :a) > was faster than (my-struct-a struct :a). > > (defstruct my-struct > a > b > c) > > (let ((struct (make-my-struct :a 1 :b 2 :c 3)) > (plist (list :a 1 :b 2 :c 3)) > (count 100000)) > (time > (progn > (format t "Using plist...") > (dotimes (n count) > (getf plist :a)))) > > (time > (progn > (format t "Using struct...") > (dotimes (n count) > (my-struct-a struct))))) With clisp interpreted code, timing may indeed give strange results. Once you compile you must also take care of dead-code removal: since the loops return NIL without any side effect, they're removed, so you're just timing formating two strings... ----(s.lisp)---------------------------------------------------------- (defstruct my-struct a b c) (let ((struct (make-my-struct :a 1 :b 2 :c 3)) (plist (list :a 1 :b 2 :c 3)) (count 100000)) (time (let ((i 0)) (format t "Using plist...") (dotimes (n count i) (incf i (getf plist :a))))) (time (let ((i 0)) (format t "Using struct...") (dotimes (n count i) (incf i (my-struct-a struct)))))) ------------------------------------------------------------------------ * (load (compile-file "/tmp/s.lisp")) ; compiling file "/private/tmp/s.lisp" (written 23 OCT 2009 03:59:05 PM): ; ... ; /tmp/s.fasl written ; compilation finished in 0:00:00.216 Using plist... Evaluation took: 0.001 seconds of real time 0.001507 seconds of total run time (0.001484 user, 0.000023 system) 200.00% CPU 3,049,365 processor cycles 0 bytes consed Using struct... Evaluation took: 0.000 seconds of real time 0.000714 seconds of total run time (0.000713 user, 0.000001 system) 100.00% CPU 1,302,653 processor cycles 0 bytes consed T * In clisp compiled code, the break even point is around the sixth slot, probably because of the type check in the structure accessors. But in any case, instead of using plist, it would be better to use (defstruct (... (:type list)) ...) or (defstruct (... (:type vector)) ....) for more than 3 elements, if you need the performance. (defstruct (... (:type list)) ...) will be twice faster than plists. -- __Pascal Bourguignon__ |