Hoy to copy a struct that represents a tree.
in [Lisp]
|
Prev: Reader ?
Next: translating cmucl command line to sbcl
From: Vassil Nikolov on 24 Oct 2009 01:14 On Fri, 23 Oct 2009 06:28:41 +0200, pjb(a)informatimago.com (Pascal J. Bourguignon) said: > 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? Large trees. Avoiding excessive consing is perfectly straightforward in the above function just by replacing APPEND with NCONC (it is immediately obvious that none of the conses that would be destructively modified are shared with anything else). And then (defun collect-nodes-in-linear-time (tree) (labels ((collect (tree a) (if (null tree) a (cons tree (collect (my-tree-l tree) (collect (my-tree-c tree) (collect (my-tree-r tree) a))))))) (collect tree '()))) is also quite easy. ---Vassil. -- "Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Pascal J. Bourguignon on 24 Oct 2009 01:20 Vassil Nikolov <vnikolov(a)pobox.com> writes: > On Fri, 23 Oct 2009 06:28:41 +0200, pjb(a)informatimago.com (Pascal J. Bourguignon) said: > >> 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? > > Large trees. If you implement a unit test for real-copy-my-tree which works on trees of depth 3, do you really need to further test it on trees of depth 100? > [s/append/nconc/] It's harder to prove the correctness of collect-nodes with mutation. (Perhaps it's only one inference, but it's one inference I did not need to think about to write the unit test). We want the functions used in unit tests to be proved very easily to be quite sure the tests are good. -- __Pascal Bourguignon__
From: Vassil Nikolov on 24 Oct 2009 01:23 On Fri, 23 Oct 2009 05:29:05 -0700 (PDT), Andy Chambers <achambers.home(a)googlemail.com> said: > ... > what it is about structs/classes that makes > them more suitable for real apps? Perhaps the most important thing is proper support for data abstraction. (By the way, note that if the programmer keeps the names of slot accessors unchanged, as one normally would, switching between structures and classes will not involve any changes to the calls to those accessors. Similarly, in most cases a constructor for a class can be defined with the same name and signature as a constructor for a structure, so calls to the constructor will not need to change, either.) ---Vassil. -- "Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Pascal J. Bourguignon on 24 Oct 2009 01:32 Vassil Nikolov <vnikolov(a)pobox.com> writes: > On Fri, 23 Oct 2009 05:29:05 -0700 (PDT), Andy Chambers <achambers.home(a)googlemail.com> said: >> ... >> what it is about structs/classes that makes >> them more suitable for real apps? > > Perhaps the most important thing is proper support for data abstraction. Notice that if upon delivery of the application you notice that it's more efficient to use lists or vectors than structures, and as long as you don't need to dispatch on the type of your structures (no method defined on them), you can always add very easily (:type list) or (:type vector). So you can have both more discriminating data inspection while debugging, and better speed on deployment. -- __Pascal Bourguignon__
From: Kaz Kylheku on 24 Oct 2009 11:38
On 2009-10-24, Vassil Nikolov <vnikolov(a)pobox.com> wrote: > > On Fri, 23 Oct 2009 05:29:05 -0700 (PDT), Andy Chambers <achambers.home(a)googlemail.com> said: >> ... >> what it is about structs/classes that makes >> them more suitable for real apps? > > Perhaps the most important thing is proper support for data abstraction. But a TREE struct with slots C, L and R is not a superior data abstraction to a CONS with slots CAR and CDR. |