Novice question -- inserting element in list
Gregory Santos
I have a newbie question to which one of you who has gone down these
well-worn paths certainly has an answer.
I would simply like to insert an element into the central portion
of a list (not the beginning or end) with the highest degree of
efficiency possible, knowing only the node after or before
which I wish to insert the new node. Presumably, this means a
destructive operation of some kind, with minimal (if any) copying.
After casting about a bit in CLtLv2, I came up with the following
routine:
(defun Insert-Node (theList node1 node2 &optional (a nil))
(let ((index (position node1 theList :test #'eq)))
(when index
(setq pos (if a (1+ index) index))
(setf theList
(nconc (subseq theList 0 pos)
(list node2)
(nthcdr pos theList))))))
which seems clumsy, or at least not optimal, being as I am
unfamiliar with the 700+ functions available in Common Lisp.
Any thoughts appreciated!
gregory
Geert-Jan van Opdorp
[...]
>
> (defun Insert-Node (theList node1 node2 &optional (a nil))
> (let ((index (position node1 theList :test #'eq)))
^^^^ 1st walk
> (when index
> (setq pos (if a (1+ index) index))
> (setf theList
> (nconc (subseq theList 0 pos)
^^^^^ 2walk + copy!
> (list node2)
> (nthcdr pos theList))))))
^^^^ 3 walk
1) Subseq makes a copy
2) The insertion spot is walked to 3 times. Lists
are not vectors!
(defun Insert-Node (theList node1 node2 &optional (a nil))
(let ((spot (member node1 theList :test #'eq)))
(when spot
(if a
;; destructively update cdr behind node1
(push node2 (cdr spot))
;; destructively update both car & cdr;
(push (shiftf (car spot) node2)
(cdr spot))))))
Geert-Jan
--
Geert-Jan van Opdorp
AI-Engineering
Amsterdam, The Netherlands
ge...@aie.nl
Stefan K. Bamberger
<time...@electriciti.com> wrote:
;;; YOUR FUNCTION:
(defun Insert-Node (theList node1 node2 &optional (a nil))
(let ((index (position node1 theList :test #'eq))
pos)
(when index
(setq pos (if a (1+ index) index))
(setf theList
(nconc (subseq theList 0 pos)
(list node2)
(nthcdr pos theList))))))
#|
(defparameter liste nil)
(setq liste (list 'a 'b 'c 'd 'e 'f 'g 'h 'i 'j))
(time
(progn
(setq liste (list 'a 'b 'c 'd 'e 'f 'g 'h 'i 'j))
(dotimes (var 5000)
(insert-node liste 'f 'z)
)
)
)
IN MCL 2.0.1 on quadra 900
(Progn (Setq Liste (List 'A 'B 'C 'D 'E 'F 'G 'H 'I 'J)) (Dotimes (Var
5000) (Insert-Node Liste 'F 'Z)))
took 753 milliseconds (0.753 seconds) to run.
Of that, 9 milliseconds (0.009 seconds) were spent in The Cooperative
Multitasking Experience.
240.080 bytes of memory allocated.
|#
MY GUESS:
This version is highly destructive, i.e., in contrary to your function the
value of variable LISTE in the example below will be changed.
Slightly change of specification: I always insert behind the node!! The
alternative should be easy.
(defun my-insert-node (thelist node1 node2)
(cond ((consp thelist)
(let ((the_rest thelist)
(new_element (list node2))
)
(loop
(when (eq (first the_rest) node1)
(setf (cdr new_element) (cdr the_rest))
(setf (cdr the_rest) new_element)
(return thelist)
)
(setf the_rest (rest the_rest))
)
))
(t
;; or NIL as <node1> couldn't be found
(list node2)
)
))
#|
(setq liste (list 'a 'b 'c 'd 'e 'f 'g 'h 'i 'j))
(time
(progn
(setq liste (list 'a 'b 'c 'd 'e 'f 'g 'h 'i 'j))
(dotimes (var 5000)
(my-insert-node liste 'f 'z)
)
)
)
IN MCL 2.0.1 on quadra 900
(Progn (Setq Liste (List 'A 'B 'C 'D 'E 'F 'G 'H 'I 'J)) (Dotimes (Var
5000) (My-Insert-Node Liste 'F 'Z)))
took 81 milliseconds (0.081 seconds) to run.
Of that, 1 milliseconds (0.001 seconds) were spent in The Cooperative
Multitasking Experience.
40080 bytes of memory allocated.
RESULT: 1/10 of time, 1/6 of size
|#
- stefan
_____________________________________________________________________
*** Support bacteria -- it's the only culture some people have! ****
_____________________________________________________________________
Stefan K. Bamberger email: ba...@informatik.uni-wuerzburg.de
Lehrstuhl f"ur Informatik VI voice : ++49 931 7056114
Universit"at W"urzburg / Germany Fax : ++49 931 7056120
_____________________________________________________________________
Erik Naggum
| I would simply like to insert an element into the central portion of a
| list (not the beginning or end) with the highest degree of efficiency
| possible, knowing only the node after or before which I wish to insert
| the new node.
(defun insert-after (newelt list index)
"Insert NEWELT in LIST after the INDEXth cell.
Returns LIST."
(let ((cell (nthcdr index list)))
(setf (cdr cell) (cons newelt (cdr cell))))
list)
#<Erik 3032612850517114>
--
BEOL and ENDOL: the ultimate general purpose programming languages
Thomas A. Russ
> I would simply like to insert an element into the central portion
> of a list (not the beginning or end) with the highest degree of
> efficiency possible, knowing only the node after or before
> which I wish to insert the new node. Presumably, this means a
> destructive operation of some kind, with minimal (if any) copying.
You analysis is correct. You will need to use destructive list
operations to accomplish your goal. There won't be any copying
required. The standard method is to go down the list and then modify
the cons cells at the point where you want to splice in the new value.
> After casting about a bit in CLtLv2, I came up with the following
> routine:
>
> (defun Insert-Node (theList node1 node2 &optional (a nil))
> (let ((index (position node1 theList :test #'eq)))
> (when index
> (setq pos (if a (1+ index) index))
> (setf theList
> (nconc (subseq theList 0 pos)
> (list node2)
> (nthcdr pos theList))))))
>
>
> which seems clumsy, or at least not optimal, being as I am
> unfamiliar with the 700+ functions available in Common Lisp.
>
> Any thoughts appreciated!
The first thing to do is to write your own search routine rather than
using position. The reason for doing this is that you want to keep
pointers into the list rather than running down the list multiple times
(once for position, once for subseq, once for nthcdr...).
One tricky part is that you will need to do the setf of theList on the
outside of the routine. There is otherwise no way to handle the first insertion
into the list. There is no destructive operation on nil that will do what you want.
(defun insert-node (theList target new-node &optional (after-p nil))
;;; Insert "new-node" into "theList" before "target" if "after-p" is
;;; nil and after "target" of "after-p" is non-nil.
;;; If "target" cannot be found, then add "new-node" to the end of the list.
;; First handle the special case of a nil value of "theList"
(cond ((null theList) (list new-node))
;; Next handle the need to put something onto the front of the list.
((and (eq target (car theList)) (not after-p))
(cons new-node theList))
;; Finally go down the list, keeping an appropriate pointer to the
;; last item found so that we can do a destructive insertion.
;; Tricky: "previous-item" is only nil for the first item, and we already
;; handled the case of needing to insert at the start of the list.
(t (let ((previous-item nil) (current-item theList))
(loop while current-item
do (when (eq target (car current-item))
(if after-p
(setf (cdr current-item) (cons new-node (cdr current-item)))
(setf (cdr previous-item) (cons new-node current-item)))
(return-from insert-node theList))
(setf previous-item current-item
current-item (cdr current-item)))
;; "target" was not found. Add after "previous-item" which now points
;; at the last item in the list.
(setf (cdr previous-item) (list new-node)))
theList)))
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
Bernhard Pfahringer
Erik Naggum <er...@naggum.no> wrote:
>[Gregory Santos]
>
>| I would simply like to insert an element into the central portion of a
>| list (not the beginning or end) with the highest degree of efficiency
>| possible, knowing only the node after or before which I wish to insert
>| the new node.
>
> "Insert NEWELT in LIST after the INDEXth cell.
>Returns LIST."
> (let ((cell (nthcdr index list)))
> (setf (cdr cell) (cons newelt (cdr cell))))
> list)
>
Beautiful solution that can be rewritten to an even more concise form:
(defun insert-after (newelt list index)
"Insert NEWELT in LIST after the INDEXth cell.
Returns LIST."
(push newelt (cdr (nthcdr index list)))
list)
--
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence bern...@ai.univie.ac.at
Richard A. O'Keefe
>I would simply like to insert an element into the central portion
>of a list (not the beginning or end) with the highest degree of
>efficiency possible, knowing only the node after or before
>which I wish to insert the new node.
If you know the NODE, I take it this means that you have or can have
a variable bound to (a typical Lisp hidden pointer to) the node, not
the position of the node in the list.
For example, I take it that you mean something like
(setf whole-list (list 'a 'b 'c 'd' 'e))
=> (A B C D E
Exercise: why did I use list instead of '(a b c d e f)?
(setf the-node (member 'c whole-list))
=> (C D E)
Now the-node is (points to) the cons cell containing the key we looked for.
To insert after it,
(setf (cdr the-node) (cons 'AFTER (cdr the-node)))
To insert before it is in general impossible. But we can move the current
element down one and replace the current element with the new one, getting
the same effect.
(progn
;; move current down
(setf (cdr the-node) (cons (car the-node) (cdr the-node)))
;; insert new element
(setf (car the-node) 'BEFORE))
Now, after doing those steps,
the-node
=> (BEFORE C AFTER D E)
whole-list
=> (A B BEFORE C AFTER D E)
Hence
(defun insert-after (Item Node)
(assert (consp Node))
(setf (cdr Node) (cons Item (cdr Node)))
(cdr Node)) ; return node containing new element
(define insert-before (Item Node)
(assert (consp Node))
(setf (cdr Node) (cons (car Node) (cdr Node)))
(setf (car Node) Item)
Node) ; return node containing new element
which work wherever the Node is in the list, even at the beginning.
With the utmost possible respect, and as gently as possible, I would
like to suggest that it is a good idea to avoid this kind of programming.
For example,
(defun insert-before (Item Key Seq)
(assert (consp Seq))
(if (eql Key (car Seq))
(cons Item Seq)
(cons (car Seq) (insert-before Item Key (cdr Seq)) )))
(defun insert-after (Item Key Seq)
(assert (consp Seq))
(if (eql Key (car Seq))
(cons (car Seq) (cons Item (cdr Seq)))
(cons (car Seq) (insert-after Item Key (cdr Seq)) )))
do more copying, but they are easier to invent, and are likely to give you
fewer nastier surprises, and things like
(insert-before 'BEFORE 'C
(insert-after 'AFTER 'C
'(A B C D E)))
work properly.
--
"conventional orthography is ... a near optimal system for the
lexical representation of English words." Chomsky & Halle, S.P.E.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.
Gregory Santos
my question. Apparently, there is no CL function that addresses
list insertion directly, but thanks to your in-depth knowledge,
creating such a routine is trivial!
Gregory Santos
time...@electriciti.com
P.S. Richard O'Keefe did a perfect job of summing up the
problem, issues, and solution in his previous post. g.s.