On page 103 of Norvig's "Tutorial on Good Lisp Programming Style" one of the
functions listed under "red flags" is append. I would have thought append was
fine; it's non-destructive so its good for functional style and so forth. The
only downside I could think of is performance, and we don't want to fall into
the trap of optimizing too early. Norvig does not say why he doesn't like
append; can anybody tell me what might be wrong with it?
KanZen
······@mail.com (KanZen) writes:
> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style" one of the
> functions listed under "red flags" is append. I would have thought append was
> fine; it's non-destructive so its good for functional style and so forth. The
> only downside I could think of is performance, and we don't want to fall into
> the trap of optimizing too early. Norvig does not say why he doesn't like
> append; can anybody tell me what might be wrong with it?
Because it is non-destructive it has to copy all the lists except the
last. Consequently the more you append the longer it takes. Thus it's
an easy way to screw up the big-O complexity of your code. Think about
how many cons cells get created when evaluating this code:
(let ((x nil))
(setf x (append x (list 0)))
(setf x (append x (list 1)))
(setf x (append x (list 2)))
x)
vs this:
(let ((x nil))
(setf x (cons 0 x))
(setf x (cons 1 x))
(setf x (cons 2 x))
(nreverse x))
Though that last would more concisely and idiomatically be written:
(let ((x nil))
(push 0 x)
(push 1 x)
(push 2 x)
(nreverse x))
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Peter Seibel wrote:
> ······@mail.com (KanZen) writes:
>
>
>>On page 103 of Norvig's "Tutorial on Good Lisp Programming Style" one of the
>>functions listed under "red flags" is append. I would have thought append was
>>fine; it's non-destructive so its good for functional style and so forth. The
>>only downside I could think of is performance, and we don't want to fall into
>>the trap of optimizing too early. Norvig does not say why he doesn't like
>>append; can anybody tell me what might be wrong with it?
>
>
> Because it is non-destructive it has to copy all the lists except the
> last. Consequently the more you append the longer it takes. Thus it's
> an easy way to screw up the big-O complexity of your code. Think about
> how many cons cells get created when evaluating this code:
I like the part where you say "think". What needs a red flag is the idea
that either nconc or append are the level at which one should be
discriminating. We have had others make the opposite/same mistake of
red-flagging "nconc". It's all bad. Especially because it is so easy to
work out when to use the appropriate one: did my little function just
gen the structure? If so, I can do what I want. Else, I cannot.
kt
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
On 8705 day of my life Peter Seibel wrote:
> ······@mail.com (KanZen) writes:
>
>> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style"
>> one of the functions listed under "red flags" is append.
>
> Because it is non-destructive it has to copy all the lists except the
> last. Consequently the more you append the longer it takes. Thus it's
> an easy way to screw up the big-O complexity of your code.
Both NCONC and APPEND are O(n) :)
Yes, APPEND is slower than NCONC, but it doesn't change big-O
complexity. :)
P.S. I hope I am not too boring :)
--
Ivan Boldyrev
Onions have layers. Unix has layers too.
Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> wrote in message news:<··············@ibhome.cgitftp.uiggm.nsc.ru>...
> On 8705 day of my life Peter Seibel wrote:
> > ······@mail.com (KanZen) writes:
> >
> >> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style"
> >> one of the functions listed under "red flags" is append.
> >
> > Because it is non-destructive it has to copy all the lists except the
> > last. Consequently the more you append the longer it takes. Thus it's
> > an easy way to screw up the big-O complexity of your code.
>
> Both NCONC and APPEND are O(n) :)
>
> Yes, APPEND is slower than NCONC, but it doesn't change big-O
> complexity. :)
I sometimes wonder if it would be useful to denote two, separate,
kinds of complexity: complexity of space and complexity of time.
Append is O(n) in both.
Nconc is O(n) in time but only O(1) in space.
I suppose the space complexity is upper-bounded by the time complexity
as it would be hard to make any use of N^2 space without taking at
least N^2 time. But, still, I think the distinction could be
useful.... maybe.... as the value you place on each kind of complexity
relates to how much of it you have to spare...
> P.S. I hope I am not too boring :)
If they thought /you/ were boring, I can only imagine what they must
think of me. ;-)
Justin Dubs
On 8708 day of my life Justin Dubs wrote:
>> >> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style"
>> >> one of the functions listed under "red flags" is append.
>> >
>> > Because it is non-destructive it has to copy all the lists except the
>> > last. Consequently the more you append the longer it takes. Thus it's
>> > an easy way to screw up the big-O complexity of your code.
>>
>> Both NCONC and APPEND are O(n) :)
>>
>> Yes, APPEND is slower than NCONC, but it doesn't change big-O
>> complexity. :)
>
> I sometimes wonder if it would be useful to denote two, separate,
> kinds of complexity: complexity of space and complexity of time.
Indeed, there is time complexity and space complexity. And as we have
P and NP, we have PS and NPS. Interesting fact: while we don't know
anything about fact P=NP, we can prove that PS=NPS. So, we know:
P subset of NP, NP is subset of NPS, and NPS equals to PS.
> Append is O(n) in both.
> Nconc is O(n) in time but only O(1) in space.
>
> I suppose the space complexity is upper-bounded by the time complexity
> as it would be hard to make any use of N^2 space without taking at
> least N^2 time.
It's true for Turing machine, but wrong for malloc-like functions that
do not initialize allocated data (MAKE-ARRAY may not initialize
elements in some implementations). But we can't say we actually use
that chunk of space...
> But, still, I think the distinction could be useful.... maybe.... as
> the value you place on each kind of complexity relates to how much
> of it you have to spare...
>> P.S. I hope I am not too boring :)
>
> If they thought /you/ were boring, I can only imagine what they must
> think of me. ;-)
I usually reply only when I see someone's mistake or misconception.
I know, such a poster may be annoying. :)
But may be most people of group do the same :)
--
Ivan Boldyrev
Sorry my terrible English, my native language is Lisp!
Ivan Boldyrev <···············@cgitftp.uiggm.nsc.ru> writes:
> On 8705 day of my life Peter Seibel wrote:
>> ······@mail.com (KanZen) writes:
>>
>>> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style"
>>> one of the functions listed under "red flags" is append.
>>
>> Because it is non-destructive it has to copy all the lists except the
>> last. Consequently the more you append the longer it takes. Thus it's
>> an easy way to screw up the big-O complexity of your code.
>
> Both NCONC and APPEND are O(n) :)
>
> Yes, APPEND is slower than NCONC, but it doesn't change big-O
> complexity. :)
>
> P.S. I hope I am not too boring :)
No, that's a good point. To the OP. The real point, as others have
explained, is APPEND is O(n) where N is the length of the list(s) to
which you are appending. Thus if you build up a list by appending you
are constantly retreading the same ground. The same argument, as Ivan
points out, applies to NCONC though it does slightly less total work
since it recycles the existing cons cells.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
······@mail.com (KanZen) wrote:
> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style" one of the
> functions listed under "red flags" is append. I would have thought append was
> fine; it's non-destructive so its good for functional style and so forth. The
> only downside I could think of is performance, and we don't want to fall into
> the trap of optimizing too early. Norvig does not say why he doesn't like
> append; can anybody tell me what might be wrong with it?
The problem is that it needs to unravel and re-ravel the lists.
That's O(n) on the size of the combination of the lists.
You're right that optimizing too early is dangerous; this is quite
likely to be something that would "bottleneck" pretty early...
--
let name="cbbrowne" and tld="ntlug.org" in String.concat ·@" [name;tld];;
http://cbbrowne.com/info/finances.html
Why do you need a driver's license to buy liquor when you can't drink
and drive?
······@mail.com (KanZen) wrote in message news:<····························@posting.google.com>...
> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style" one of the
> functions listed under "red flags" is append. I would have thought append was
> fine; it's non-destructive so its good for functional style and so forth. The
> only downside I could think of is performance, and we don't want to fall into
> the trap of optimizing too early. Norvig does not say why he doesn't like
> append; can anybody tell me what might be wrong with it?
I think there's a difference between premature opimization and things
that are complexity-classes worse than they need to be and that may be
in inner loops.
This kind of thing:
(let ((results nil))
(loop ...
do (setf results (append results x)))
results)
is a disaster waiting to happen. And you do see it fairly often in
things people write...
Tim Bradshaw <··········@tfeb.org> wrote:
+---------------
| I think there's a difference between premature opimization and things
| that are complexity-classes worse than they need to be and that may be
| in inner loops. This kind of thing:
| (let ((results nil))
| (loop ...
| do (setf results (append results x)))
| results)
| is a disaster waiting to happen. And you do see it fairly often in
| things people write...
+---------------
(sigh*) Yes, one does... Yet...
<rant intensity="mild">
I wonder if it might not happen so often if REDUCE had an additional
keyword argument, say :MAX-ARITY (default 2), which said how many
arguments the function being used to REDUCE the sequence could accept.
Then a lot of the sorts of LOOPs you note above could be performed
by calls to (REDUCE #'fcn sequence :MAX-ARITY CALL-ARGUMENTS-LIMIT),
allowing the work to be done safely in "big chunks".
</rant>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
··········@tfeb.org (Tim Bradshaw) writes:
> I think there's a difference between premature opimization and things
> that are complexity-classes worse than they need to be and that may be
> in inner loops.
That's a blurry line though. I often find that things which could be
optimized into a better complexity class actually work just fine in
practice. I've even taken to always writing the neatest version and
/never/ optimizing anything unless it becomes an observable problem.
Sounds crazy at first, but it's awfully pleasant, and it doesn't
actually lead to slow programs in my experience.
> This kind of thing:
>
> (let ((results nil))
> (loop ...
> do (setf results (append results x)))
> results)
>
> is a disaster waiting to happen. And you do see it fairly often in
> things people write...
For some value of disaster. Often it just means that you, the
programmer, notice it's slow and take a couple of minutes to rewrite
it. I do this all the time and I don't recall it being disastrous in
any meaningful sense (no lives lost! :-))
I actually find it very satisfying to go back and say "ah, this has to
be faster, and I can fix it very easily."
YMMV of course!
Cheers,
Luke
P.S., this notion is inherited from an Erlang programmer called Joe
Armstrong, who puts it "I must program as inefficiently as possible."
This is an ExtremeStatement along the lines of "YouArentGonnaNeedIt".
Both are profound in my opinion.
+ Luke Gorrie <····@bluetail.com>:
| I do this all the time and I don't recall it being disastrous in
| any meaningful sense (no lives lost! :-))
Well, being disastrous would actually mean making stars go bad,
and I have a hard time imagining any Lisp program having that
sort of effect.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
······@mail.com (KanZen) wrote in message news:<····························@posting.google.com>...
> On page 103 of Norvig's "Tutorial on Good Lisp Programming Style" one of the
> functions listed under "red flags" is append. I would have thought append was
> fine; it's non-destructive so its good for functional style and so forth. The
> only downside I could think of is performance, and we don't want to fall into
> the trap of optimizing too early. Norvig does not say why he doesn't like
> append; can anybody tell me what might be wrong with it?
Speaking of Norvig, check out his PAIP for sourcecode to make queues,
where repeated destructive concatenate isn't that slow. It's
implemented by having a list and a pointer to its end. It's notable
for employing a "clever trick" in order to remove one comparison.
(Just to be a badass.)