* paul_ru...@scientia.com | At the risk of rehashing old ground: what is "unnecessary" waste is | partly a matter of opinion. The space and/or time efficiency of lots of | code can be improved on. The question is how much effort one wants to | invest in doing so.
I can understand why you cons up new articles with the same old defense for the same old unskilled Lisp style rather than reuse existing defenses by reference...
> Tim Bradshaw wrote: > But nested lists are trees. :-) At least you can look at them that > way in this context, removing the nesting.
Yes, they are, but you get a choice over which side (car or cdr) you recurse on and which you iterate over. Quite apart from being just wrong (sigh), my answer recurses on the cdr and iterates (assuming the system does TRO, which before anyone picks me up, I know is not a safe assumption) on the car. So if I want something which deals with things I'm thinking of as `lists' -- ie things which are probably deep in the cdr direction but not in the car direction then that's a bad choice, because I'd like my program not to blow up however long the list is.
--tim
(I think what I'd write is actually something like
(defun collapse-list (list) (let ((a '()) (at nil)) (labels ((collect (x) (if at (setf (cdr at) (list x) at (cdr at)) (setf a (list x) at a))) (clist (l) (dolist (e l a) (if (atom e) (collect e) (clist e))))) (clist list))))
In article <7g2ccl$su...@nnrp1.dejanews.com>, Vassil Nikolov <vniko...@poboxes.com> wrote:
> Not that hard, perhaps. What if, by the law of perverse solutions, > the backquote construct is implemented so that for `(,x) it does > a REPLACA on the cons produced by the reader when it processed the > opening parenthesis. I'd like to be corrected that this is illegal.
No I think you're right; a quick look at Steele suggests that anything EQUAL to (list x) would be OK here.
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <slrn7i2s0b.oj4.ktur...@pug1.sprocketshop.com>, ktur...@pug1.sprocketshop.com says...
>particularly concerned with performance. I would like to see a simple >and elegant solution.
I can't say if this one is simple or eligant, but it seams to work...
(defun collapse-list (l) (loop with result = (list nil) with result-tail = result for item in l if (atom item) do (rplacd result-tail (list item)) (setq result-tail (cdr result-tail)) else do (rplacd result-tail (collapse-list item)) (setq result-tail (last result-tail)) end finally return (cdr result)))
(setq l '((nil a nil (((((((((((nil))))))))))) s d nil) q w r (d f (4 r t 6 (h j s l) r k l (d g)) sv) s f j c ()))
CL-USER 76 > (collapse-list l) (NIL A NIL NIL S D NIL Q W R D F 4 R T 6 H J S L R K L D G SV S F J C NIL)
BTW, I came up with this solution after looking at the results of (pprint (macroexpand '(loop for item in l collect item)))
Kent M Pitman wrote: > ... You want #'(lambda (x) (funcall fn x)) > in situations like this. [Or if you have the lisp machine's circular-list > function, (mapcar #'funcall (circular-list fn) lists). Admittedly > obscure, but some use it idiomatically--almost to the point that I think > the compiler should have had an optimizer for it that turned it back > into something that didn't waste the single cons needed to make the circular > list.]
paul_ru...@scientia.com writes: > In article <7g2ccl$su...@nnrp1.dejanews.com>, > Vassil Nikolov <vniko...@poboxes.com> wrote: > > Not that hard, perhaps. What if, by the law of perverse solutions, > > the backquote construct is implemented so that for `(,x) it does > > a REPLACA on the cons produced by the reader when it processed the > > opening parenthesis. I'd like to be corrected that this is illegal.
> No I think you're right; a quick look at Steele suggests that anything EQUAL > to (list x) would be OK here.
The critical thing is that (list x) conses fresh structure. (eq (list x) (list x)) is guaranteed to yield false. Not so for (eq (rplaca x 'a) (rplaca x 'b)), which yields true.
Further, if you changed the car of the cons which was (,x), where would you remember the ,x part in case the form was evaluated a second time?
> Kent M Pitman wrote: > > ... You want #'(lambda (x) (funcall fn x)) > > in situations like this. [Or if you have the lisp machine's circular-list > > function, (mapcar #'funcall (circular-list fn) lists). Admittedly > > obscure, but some use it idiomatically--almost to the point that I think > > the compiler should have had an optimizer for it that turned it back > > into something that didn't waste the single cons needed to make the circular > > list.]
> > In article <7g2ccl$su...@nnrp1.dejanews.com>, > > Vassil Nikolov <vniko...@poboxes.com> wrote: > > > Not that hard, perhaps. What if, by the law of perverse solutions, > > > the backquote construct is implemented so that for `(,x) it does > > > a REPLACA on the cons produced by the reader when it processed the > > > opening parenthesis. I'd like to be corrected that this is illegal.
> > No I think you're right; a quick look at Steele suggests that anything EQUAL > > to (list x) would be OK here.
> The critical thing is that (list x) conses fresh structure. > (eq (list x) (list x)) is guaranteed to yield false. > Not so for (eq (rplaca x 'a) (rplaca x 'b)), which yields true.
I think we're at cross purposes: by "OK here" I was meant to say that any such value would be a valid implementation for the result of the backquote form, not that it would neccessarily be the right thing in the oringinal function defn.
As you say, if mapcan is being used it is desirable that you have fresh lists. My error was that I hadn't appreciated that the precise identity of the object constructed by `(,x) is implementation dependent, provided it's EQUAL to (list x).
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <slrn7i2s0b.oj4.ktur...@pug1.sprocketshop.com>, ktur...@pug1.sprocketshop.com (Kenneth P. Turvey) wrote:
> As part of another project I had need of a function to collapse a > possibly nested list into an unnested version containing the same atoms. > After finishing my first hack at it I thought, "There has got to be a > better way". I was hoping some of you Lisp experts (I'm mediocre in > this language, at best) would be able to help me out. I am not > particularly concerned with performance. I would like to see a simple > and elegant solution.
...
Here is an iterative form to complement all the elegant recursive solutions. It is pontentially less efficient.
(defun flatten (x) (do ((result nil) (last nil) (this (copy-list x))) ((null this) result) (if (listp (car this)) (setq this (append (car this) (cdr this))) (setq last (if last (setf (cdr last) this) (setq result this)) this (cdr this)))))
In article <ey31zh7w6d3....@lostwithiel.tfeb.org>, Tim Bradshaw <t...@tfeb.org> wrote: (...)
> Quite apart from being just > wrong (sigh), my answer
(...)
Why?
-- Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov (You may want to cc your posting to me if I _have_ to see it.) LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <7g2ccl$su...@nnrp1.dejanews.com>, Vassil Nikolov <vniko...@poboxes.com> wrote:
> Not that hard, perhaps. What if, by the law of perverse solutions, > the backquote construct is implemented so that for `(,x) it does > a REPLACA on the cons produced by the reader when it processed the > opening parenthesis. I'd like to be corrected that this is illegal.
In article <sfwiuaigmgi....@world.std.com>, Kent M Pitman <pit...@world.std.com> wrote:
> The critical thing is that (list x) conses fresh structure. > (eq (list x) (list x)) is guaranteed to yield false. > Not so for (eq (rplaca x 'a) (rplaca x 'b)), which yields true.
Yes, but what in the language definition specifically implies that `(,x) must be fresh? (Apart from the fact that everybody knows it is the Wrong Thing if it is not fresh.)
> Further, if you changed the car of the cons which was (,x), where > would you remember the ,x part in case the form was evaluated > a second time?
`(,X) must be read as a form which, when evaluated, produces a list of one element which is the value of X, right? (The canonical such form is (LIST X).) I had in mind reading that as the following form
or something like that. Evaluating this form evaluates X and returns a list whose car is the value of X thus produced.
Once again: I am not advocating such a perverse way of doing it (and can't think of a reason that would justify it); I just want to learn if and how this is illegal (and not just ugly and counterproductive).
-- Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov (You may want to cc your posting to me if I _have_ to see it.) LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Vassil Nikolov <vniko...@poboxes.com> writes: > `(,X) must be read as a form which, when evaluated, produces a list > of one element which is the value of X, right? (The canonical such > form is (LIST X).) I had in mind reading that as the following form
> or something like that. Evaluating this form evaluates X and > returns a list whose car is the value of X thus produced.
Well, I can't say wether such an implementation would be technically legal or not, but it sure would break a lot of existing code.
The problem is that a second call to this form would destroy the result of the first one. People tend to rely on this not happening.
If you read back you will find that Kent wasn't talking about _legality_ but about _clearity_.
Consider `(,X Y).
An implementation could rewrite that as (CONS X '(Y)), with the '(Y) being a shared constant.
In this case, a call to the form would not destroy previous results, but it would still be a bad thing to give this to NCONC.
While it is hard to imagine `(,X) giving that sort of problems, it is still good to use (LIST X) to make it clear to _human_ readers that we want new structure.
> An implementation could rewrite that as (CONS X '(Y)), with the '(Y) > being a shared constant.
> In this case, a call to the form would not destroy previous results, > but it would still be a bad thing to give this to NCONC.
> While it is hard to imagine `(,X) giving that sort of problems, it is > still good to use (LIST X) to make it clear to _human_ readers that we > want new structure.
This is exactly what I meant, yes. Thanks for holding the fort while I'm working on my scifi novel... Back to the grind.
* Vassil Nikolov wrote: > In article <ey31zh7w6d3....@lostwithiel.tfeb.org>, > Tim Bradshaw <t...@tfeb.org> wrote: > (...) >> Quite apart from being just >> wrong (sigh), my answer > (...) > Why?
Why was it wrong? Because it didn't deal with NIL right as Kent pointed out. I make this mistake all the time.
> USER(84): (setq *test* '(((a) nil) b (((c) d) (e (f (g nil))) nil (h (i)) nil))) > (((A) NIL) B (((C) D) (E (F (G NIL))) NIL (H (I)) NIL)) > USER(85): (flatten-tree *test*) > (A B C D E F G H I) > USER(86): (flatten-tree *test* :preserve-nil t) > (A NIL B C D E F G NIL NIL H I NIL) > USER(87): (flatten-tree *test* :preserve-nil t :depth 1) > ((A) NIL B ((C) D) (E (F (G NIL))) NIL (H (I)) NIL) > USER(88): (flatten-tree *test* :preserve-nil nil :depth 1) > ((A) B ((C) D) (E (F (G NIL))) (H (I))) > USER(89): (flatten-tree *test* :preserve-nil t :depth 3) > (A NIL B C D E F (G NIL) NIL H I NIL) > USER(90):
which, in my tests (and using ":preserve-nil t" to be able to compare it), is about 15-20% *slower* than Pitman's, but conses almost 40% less.
barranqu...@laley-actualidad.es (Juanma Barranquero) writes: > in my tests (and using ":preserve-nil t" to be able to compare > it), is about 15-20% *slower* than Pitman's, but conses almost 40% > less.
Uh, you should talk to Franz about why mine would not do optimal consing. I don't see any gratuitous consing in the source code. I see no reason LOOP shouldn't be able to do a completely optimal job on that part.
And make sure you don't use keyword argument passing when doing any of this, because that's going to potentially dwarf the time spent doing the other parts. I haven't seen how Franz compiles them, and I'm just speaking generally about the language, but while keyword calls buy important flexibilty in non-mission-critical interfaces, and some people (e.g. Paul Graham) are big fans of their use in a great many situations, they are real potentials for slow code in tight loops and the decision to use them for code maintenance reasons has to be traded against the potential difficulty of compiling them efficiently. Most compilers I've used could do a lot better than they do in compiling keyword calls than they do, too, so you're often not even seeing optimal treatment. I'm pretty sure CLIM, for example, has massive numbers of compiler macros to try to get those keyword calls out of the runtime code because it's such a potential bottleneck. Compiler macros were added to CL specifically to help in such cases.
In article <ekv4sm1t4n5....@ra.pvv.ntnu.no>, Stig Hemmer <s...@pvv.ntnu.no> wrote:
> Vassil Nikolov <vniko...@poboxes.com> writes: > > `(,X) must be read as a form which, when evaluated, produces a list > > of one element which is the value of X, right? (The canonical such > > form is (LIST X).) I had in mind reading that as the following form
> > or something like that. Evaluating this form evaluates X and > > returns a list whose car is the value of X thus produced.
> Well, I can't say wether such an implementation would be technically > legal or not, but it sure would break a lot of existing code.
> The problem is that a second call to this form would destroy the > result of the first one. People tend to rely on this not happening.
I did write `perverse,' `ugly,' *and* `counterproductive,' didn't I?
> If you read back you will find that Kent wasn't talking about > _legality_ but about _clearity_.
Indeed he wasn't; it was me who took the occasion to ask about legality.
> Consider `(,X Y).
> An implementation could rewrite that as (CONS X '(Y)), with the '(Y) > being a shared constant.
A literal constant that may be shared, you mean, of course.
> In this case, a call to the form would not destroy previous results, > but it would still be a bad thing to give this to NCONC.
> While it is hard to imagine `(,X) giving that sort of problems, it is > still good to use (LIST X) to make it clear to _human_ readers that we > want new structure.
Absolutely. Now, back to my question:
Can you or anyone confirm or contradict that the above RPLACA implementation is legal? If it is, it might break people's code, but people should not rely on implementations not doing legal things, shouldn't they? Please understand me correctly: I'd rather have that illegal, but I can't see it illegal in the language specification.
-- Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov (You may want to cc your posting to me if I _have_ to see it.) LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <ey3btg9b2lc....@lostwithiel.tfeb.org>, Tim Bradshaw <t...@tfeb.org> wrote:
> * Vassil Nikolov wrote: > > In article <ey31zh7w6d3....@lostwithiel.tfeb.org>, > > Tim Bradshaw <t...@tfeb.org> wrote: > > (...) > >> Quite apart from being just > >> wrong (sigh), my answer > > (...)
> > Why?
> Why was it wrong? Because it didn't deal with NIL right as Kent > pointed out. I make this mistake all the time.
Thanks for replying. I thought I had missed some real bug. The way your solution dealt with NIL may or may not be wrong---depends on the purpose. And it is not difficult to change it from one functionality to the other.
-- Vassil Nikolov <vniko...@poboxes.com> www.poboxes.com/vnikolov (You may want to cc your posting to me if I _have_ to see it.) LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
On Thu, 29 Apr 1999 15:22:46 GMT, Kent M Pitman <pit...@world.std.com> wrote:
>Uh, you should talk to Franz about why mine would not do optimal >consing. I don't see any gratuitous consing in the source code. I >see no reason LOOP shouldn't be able to do a completely optimal job >on that part.
Well, there's definitely a difference in consing between the two functions.
I've now tested with:
; my function, simplified to have the same interface as yours (defun flatten-tree (tree) (labels ((walk (branch accum) (dolist (item branch accum) (if (atom item) (push item accum) (setq accum (walk item accum)))))) (nreverse (walk tree '()))))
; your function (defun collapse-list (tree) (loop for item in tree when (atom item) collect item else nconc (collapse-list item)))
and the following test data (not very significative, I know):
nil (nil) ((((((((((((((((((((a)))))))))))))))))))) (a b c d e f g h i j k l m n o p q r s t u v w x y z) ((((((((((a) b) c) d) e) f) g) h) i) j) (a (b (c (d (e (f (g (h (i (j)))))))))) (((((((((((a)))))))))) ((((((((((b))))))))))) (a (b (c (d (e (f (g (h (i) j) k) l) m) n) o) p) q) (a nil (b ((c d (nil) e (f (g) h) nil) (i j) k) l) (((m))) nil) ((j u a n m a) (b a r r a n q u e r o)))
in a 1,000,000 iterations loop. The results I get, with
USER(30): (time (test-fun1)) ;; flatten-tree ; cpu time (non-gc) 92,738 msec (00:01:32.738) user, 0 msec system ; cpu time (gc) 10,621 msec user, 0 msec system ; cpu time (total) 103,359 msec (00:01:43.359) user, 0 msec system ; real time 103,358 msec (00:01:43.358) ; space allocation: ; 101,001,351 cons cells, 0 symbols, 4,928 other bytes, 0 static bytes
USER(34): (time (test-fun2)) ;; collapse-list ; cpu time (non-gc) 92,904 msec (00:01:32.904) user, 0 msec system ; cpu time (gc) 19,808 msec user, 0 msec system ; cpu time (total) 112,712 msec (00:01:52.712) user, 0 msec system ; real time 112,712 msec (00:01:52.712) ; space allocation: ; 188,000,000 cons cells, 0 symbols, 5,312 other bytes, 0 static bytes
so they're about equal in speed but mine consed 54% of what yours did. I sure don't know why. Maybe Duane Retting is reading us and can offer any hint?
>And make sure you don't use keyword argument passing when doing any >of this, because that's going to potentially dwarf the time spent >doing the other parts.
Thanks for your informative post about keyword arguments. I didn't know any of that.
>Well, there's definitely a difference in consing between the two >functions.
>(defun collapse-list (tree) > (loop > for item in tree > when (atom item) > collect item > else > nconc (collapse-list item)))
The difference in consing is probably explained by the way (I suppose) loop COLLECTs values without doing nreverse. It probably destructively modifies the tail of the result list, which itself is initialized using one cons-cell to simplify the update code. Consequently, you'd get an overhead of one additional cons-cell per call. Depending on the details, the overhead could as well be more than one cell. Looking at the macro-expanded code might further clarify this issue. But anyway, the additional consing seems worth (cf. runtimes). There once was this slogan "Consing is cheap", which I think should be rephrased into "Consing can be cheap" (given you know what you do and have a well- implemented generational garbage collector at your disposal).
A problem with all solutions proposed so far is recursion over the substructures which is not tail-recursive. So the call stack might overflow for deep enough structures. The following iterative version manages its own stack (including tail-recursion optimization). As only each non-last-position substructure necessitates a stack-push, this version will never cons more than the original loop-based one.
(defun collapse-list (list) (loop with stack = nil for item = (cond (list (pop list)) (stack (setq list (pop stack)) (pop list)) (t (loop-finish))) if (atom item) collect item else do (when list (push list stack)) (setf list item)))
Bernhard -- -------------------------------------------------------------------------- Bernhard Pfahringer Austrian Research Institute for http://www.ai.univie.ac.at/~bernhard/ Artificial Intelligence bernh...@ai.univie.ac.at
Not in my example, as both routines were approx. equal in speed.
>A problem with all solutions proposed so far is recursion over the >substructures which is not tail-recursive. So the call stack might >overflow for deep enough structures.
Yes, you're right. I tried an iterative version, but it wasn't half as clever as yours (nor half as obscure, OTOH ;)
>The following iterative version manages its own stack (including >tail-recursion optimization). As only each non-last-position >substructure necessitates a stack-push, this version will never cons >more than the original loop-based one.
It stills conses (in my Allegro) about 36% more than my best recursive version, but is also 44% faster, and as you say it doesn't have to worry about stack depth. Pretty impressive. Thanks.
