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