push
Josef Eschgfaeller
Graham says "The combination of push and nreverse ... is the standard
Lisp idiom for accumulating a list." Thus:
(defun copy-if (f a)
(let ((acc nil)) (dolist (x a) (if (funcall f x) (push x acc)))
(nreverse acc)))
But is nreverse not expensive? I tried:
(defun copy-if (f a)
(let ((acc (list 1))) (dolist (x a (rest acc))
(if (funcall f x) (nconc acc (list x))))))
Is nconc + list slower than push?
I initialized here acc as (list 1) using (rest acc) as result, in
order to have a starting point for nconc. It there a better trick?
J. Eschgfaeller
Stig Hemmer
So it is, but it is only called once, which makes the cost acceptable
in most cases. It is linear on the length of the list.
> Is nconc + list slower than push?
The problem with NCONC is that it has to traverse down to the end of
the list before doing anything. This is done every time through the
loop giving a total cost proportional to the square of the length of
the list. Not nice for longer lists.
One can make a better solution by remembering the last cons cell of
the list to avoid all the traversing, using (SETF (CDR ...)) instead
of NCONC. This is the _other_ standard idiom for collecting lists.
These days I would suggest using LOOP COLLECT and simply assume that
this macro is as optimized as it can get for your implementation.
Paul Graham doesn't like LOOP, but don't let that stop you.
> I initialized here acc as (list 1) using (rest acc) as result, in
> order to have a starting point for nconc. It there a better trick?
Not really. If you macroexpand LOOP, you will probably see similar
code.
Stig Hemmer,
Jack of a Few Trades.
Erik Naggum
| But is nreverse not expensive?
yes, but the other options are more expensive. in some cases, it is even
cost-effective to use REVERSE because of gargage collector issues.
| Is nconc + list slower than push?
yes. NCONC traverses the entire list every time, and you end up with
quadratic behavior. PUSH is constant, so you end up with linear behavior.
if you want to avoid PUSH, you start off with a CONS of two NIL's, and
destructively modify the CDR to point to a fresh singleton list (CONS of
the element and NIL), and then set a helper variable to point to the new
CONS, just like PUSH would. at the end, you return the CDR of the first
CONS, like you do with your inefficient NCONC example. note that this is
one consing, one destructive, and one assignment operation, but needs two
variables. PUSH is one consing and one assignment operation, and one
variable. you earn points to use against reversing in the difference.
it may be instructive for you to study how NCONC, NREVERSE, and REVERSE
are implemented. note that NREVERSE can modify the CAR or the CDR of the
cons cell at liberty.
| I initialized here acc as (list 1) using (rest acc) as result, in order
| to have a starting point for nconc. It there a better trick?
no, that's the trick, but "1" looks like it has some inherent meaning,
which you avoid by using the more common NIL. (note that the other
alternatives are to treat the first element specially, or to test for a
null value in every iteration. it sometimes makes sense to treat the
first value specially.)
#:Erik
--
@1999-07-22T00:37:33Z -- pi billion seconds since the turn of the century
David Bakhash
> cost-effective to use REVERSE because of gargage collector issues.
can you elaborate? maybe with an example, or is this something you can only
know from profiling?
dave
Paul Rudin
> Graham says "The combination of push and nreverse ... is the standard
> Lisp idiom for accumulating a list." Thus:
>
> (defun copy-if (f a)
> (let ((acc nil)) (dolist (x a) (if (funcall f x) (push x acc)))
> (nreverse acc)))
>
> But is nreverse not expensive? I tried:
>
> (defun copy-if (f a)
> (let ((acc (list 1))) (dolist (x a (rest acc))
> (if (funcall f x) (nconc acc (list x))))))
This is probably not a good idea, nconc will presumably have to
traverse acc each time to find its end?
>
> Is nconc + list slower than push?
>
> I initialized here acc as (list 1) using (rest acc) as result, in
> order to have a starting point for nconc. It there a better trick?
I'd guess that in most cases the fastest thing is to maintain a
pointer to the end of your accumulator and use RPLACD. LOOP may well
do this for you - check the macro expansion in the lisp you're using.
BTW, in this particular case there's already a lisp function, namely
REMOVE-IF-NOT, that does what copy-if does, and hopefully this has
been reasonably well implemented by the people that wrote the
compiler...
Johan Kullstam
as i understand it, modern generational garbage collectors do not
impose nearly the penalty on consing as older collectors did. short
lived objects don't cost much to reap.
i think profiling is the key. bottlenecks are tricky to predict a
priori. profile comparison is a sure way to know how much something
costs and if it needs optimizing.
--
J o h a n K u l l s t a m
[kull...@ne.mediaone.net]
Don't Fear the Penguin!
Nick Levine
Stig Hemmer wrote in message ...
>These days I would suggest using LOOP COLLECT and simply assume that
>this macro is as optimized as it can get for your implementation.
It generally is (in my experience - check your macroexpansion if you're in
doubt).
>Paul Graham doesn't like LOOP, but don't let that stop you.
I think the point is that
(loop for x in y collect (foo x))
is dead safe and if you prefer it to mapcar then go ahead and use it.
Loop really becomes a problem when you start jumbling a whole load of FOR,
WITH, FINALLY, WHEN and heaven knows what other clauses. In some
circumstances (which ellude me right now, sorry) it's pretty hard for
implementors to tell from the spec what it ought to do, or for users to
guess quite what the implementors did. If it's really complex, I use the
simple loop macro, with let, setq, if and return (and friends of the above)
to control the lot. Less compact, but gets my intention to work much more
reliably.
- n
Erik Naggum
| in some cases, it is even cost-effective to use REVERSE because of
| gargage collector issues.
* David Bakhash <da...@teracorp.com>
| can you elaborate? maybe with an example, or is this something you can
| only know from profiling?
two issues if the list is accumulated over a long time relative to other
consing: its locality of reference is vastly improved with REVERSE and
thus the cost of future accesses goes down, and crossing the old/new
space line is more expensive than cosing, all counted.
I made the point to show that this is not a trivial issue, that it is
very hard to predict the behavior without good knowledge of the system.