Subject: Re: push From: Erik Naggum <erik@naggum.no> Date: 1999/06/18 Newsgroups: comp.lang.lisp Message-ID: <3138716162296905@naggum.no> * Josef Eschgfaeller <esg@felix.unife.it> | 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