Hi!
Suppose I have a list (possible a list of lists) and want to insert a
new element (possibly a list) at top level.
What is the most efficient way of doing this given that I know the
position that I am to insert in?
The brute force solution is of course to copy the elements one by one
upto position, append the new element and then append the rest of the
list, but I do not want to do this. Is there a simple and efficient solution?
Thanks,
--Raman
--
T. V. Raman <·····@cs.cornell.edu>Tel: (607)255-9202 R 272-3649
Office: 4116 Upson Hall,
Department of Computer Science, Cornell University Ithaca NY 14853-6201
Res: 226 Bryant Avenue Ithaca NY 14850
In article <······················@cs.cornell.edu>, ·····@cs.cornell.edu (T. V. Raman) writes:
|> What is the most efficient way of [inserting an element into a list]
|> given that I know the position that I am to insert in?
If you are really concerned with efficiency, then you should consider using a
data structure that facilitates search better than the singly-linked lists of
Lisp.
|> The brute force solution is of course to copy the elements one by one
|> upto position, append the new element and then append the rest of the
|> list, but I do not want to do this. Is there a simple and efficient solution?
Simple and efficient may be mutually exclusive ;-) Here's a solution that avoids
list copying altogether, but requires the use of RPLACD--a dangerous and
aesthetically distasteful function. Also, the length of the list must be computed
for the average case. This value could be maintained by your program and then
passed to the INSERT function as an argument.
> (setq my-list '(a (b c) e f))
(A (B C) E F)
> (setq pos 2) ;known insertion position
2
> (defun insert (item list n)
;;no error checking for negative value of n
(cond ((zerop n)
(cons item list))
((> n (1- (list-length list)))
(nconc list (list item)))
(t
(let ((tail (nthcdr (1- n) list)))
(rplacd tail (cons item (cdr tail)))
list))))
INSERT
> (insert 'd my-list pos)
(A (B C) D E F)
ObCL: Why is there no built-in SETF method for NTHCDR?
..................................................
Len Charest, Jr.
JPL Artificial Intelligence Group
·······@aig.jpl.nasa.gov
In article <······················@jpl-devvax.jpl.nasa.gov>, ·······@Aig.Jpl.Nasa.Gov (Len Charest) writes:
|> In article <······················@cs.cornell.edu>, ·····@cs.cornell.edu (T. V. Raman) writes:
|>
|> |> What is the most efficient way of [inserting an element into a list]
|> |> given that I know the position that I am to insert in?
|>
|> If you are really concerned with efficiency, then you should consider using a
|> data structure that facilitates search better than the singly-linked lists of
|> Lisp.
|>
|> |> The brute force solution is of course to copy the elements one by one
|> |> upto position, append the new element and then append the rest of the
|> |> list, but I do not want to do this. Is there a simple and efficient solution?
|>
|> Simple and efficient may be mutually exclusive ;-) Here's a solution that avoids
|> list copying altogether, but requires the use of RPLACD--a dangerous and
|> aesthetically distasteful function. Also, the length of the list must be computed
|> for the average case. This value could be maintained by your program and then
|> passed to the INSERT function as an argument.
|>
|> > (setq my-list '(a (b c) e f))
|> (A (B C) E F)
|> > (setq pos 2) ;known insertion position
|> 2
|> > (defun insert (item list n)
|> ;;no error checking for negative value of n
|> (cond ((zerop n)
|> (cons item list))
|> ((> n (1- (list-length list)))
|> (nconc list (list item)))
|> (t
|> (let ((tail (nthcdr (1- n) list)))
|> (rplacd tail (cons item (cdr tail)))
|> list))))
|> INSERT
|> > (insert 'd my-list pos)
|> (A (B C) D E F)
|>
|> ObCL: Why is there no built-in SETF method for NTHCDR?
|> ..................................................
|> Len Charest, Jr.
|> JPL Artificial Intelligence Group
|> ·······@aig.jpl.nasa.gov
If 1 <= n <= length(list) then this function would iterate the list twice
-- once to determine the length of the list and the a second time, which
in the worst case would be the entire list, to do the insert. You should
use a DO loop and only iterate down the list each time incrementing a counter.
The main loop in the function body should be something like
(do ((tail l (cdr tail))
(i 0 (1+ i)))
((or (null tail) (= i n))
...)
...)
Also the (nconc list (list item)) is a bug (?). E.g., let A = (1 2 3), ITEM = Z,
and N = 5. Your function yields (1 2 3 Z) instead of (1 2 3 <foo> <foo> Z).
Also, The nconc causes a second transversal of the list when n > length(list).
There's nothing wrong, nor "aesthetically distasteful", with using shared structures. If anything I think its distasteful to constantly copy objects
instead of reusing them. Most Lisp programmers don't take the time to
write efficient Lisp programs and that is the main reason for Lisp being
"inefficient".
|^^^^^^| The Official Dirt Riders Motto...
| | (According to Bart, that is)
| |
| (o)(o) _____________________________
@ _) _ / Pain is temporary, | Kirk Kandt
| ,___| /__ Bones heal, | M/S 525-3660
| / \ Chicks dig scars & | Jet Propulsion Laboratory
/___\ \ Glory is forever!!! | 4800 Oak Grove Drive
/ \ \___________________________| Pasadena, CA 91109
"To disarm the people - that was the best and most effective way
to enslave them ...."
- George Mason ( Framer of the Declaration of Rights, Virginia,
1776, which became the basis for the U.S. Bill of Rights )
3 Elliot, Debate at 380.
"No free man shall ever be debarred the use of arms. The strongest reason
for the people to retain the right to keep and bear arms is, as a last
resort, to protect themselves against tyranny in government."
- Thomas Jefferson, Proposal Virginia Constitution, June 1776
1 Thomas Jefferson Papers, 334 (C. J. Boyd, Ed., 1950).
From: Barry Margolin
Subject: Re: Inserting elements into a list at a specified position:
Date:
Message-ID: <1cn92kINN1b7@early-bird.think.com>
In article <······················@cs.cornell.edu> ·····@cs.cornell.edu (T. V. Raman) writes:
>Suppose I have a list (possible a list of lists) and want to insert a
>new element (possibly a list) at top level.
Why do you think it's relevant (or even noteworthy ) that the elements of
the list or the new element could be lists? Your mention that the new
element could be a list almost made me think you want to splice it in as a
sublist, rather than as a single element.
>What is the most efficient way of doing this given that I know the
>position that I am to insert in?
I wanted to suggest:
(push new-element (nthcdr n list))
Unfortunately, NTHCDR isn't a standard SETF location (it works on a
Symbolics, though).
(push new-element (cdr (nthcdr (1- n) list)))
will work for non-zero N. So, the following should work pretty well:
(defun insert (new-element list position)
(if (zerop position)
(push new-element list)
(push new-element (cdr (nthcdr (1- position)) list)))
list)
Because of the zero case, make sure you always use this for value, not just
side effect.
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
Date: Wed, 28 Oct 1992 13:06 EST
From: "T. V. Raman" <·····@cs.cornell.edu>
Suppose I have a list (possible a list of lists) and want to insert a
new element (possibly a list) at top level.
What is the most efficient way of doing this given that I know the
position that I am to insert in?
The brute force solution is of course to copy the elements one by one
upto position, append the new element and then append the rest of the
list, but I do not want to do this. Is there a simple and efficient solution?
If it's efficiency you want, I'm going to assume you're acknowledging the
possibility of side-effect.
In implementations that permit it, (push thing (nthcdr n x)) is pretty handy.
Unfortunately, neither CLtL nor dpANS CL defines NTHCDR as a place, so this
isn't likely to be portable. (There's still time to make a Public Review comment,
though... :-)
The conceptual difficulty is that you kind of have to do different things for
NTHCDR 0 than for other places. In the NTHCDR 0 case, you do (push thing x)
and in the NTHCDR n>0 case, you do (push thing (cdr (nthcdr (1- n) x))), which
effectively RPLACD's that location.
If you don't want to rely on non-portable stuff, you might try writing something like:
(defun insert-before-element-n-destructively (n thing list)
(if (= n 0)
(cons thing list) ;There's no way to be destructive in this case, so just cons.
(let ((tail (nthcdr (1- n) list)))
(if (null tail) (error "There is no position ~D in ~S." n list))
(push thing (cdr tail))
list)))