Page 1 of 2
moving an element of a list to another list
Posted: Thu Oct 28, 2010 1:31 pm
by vernonsolo
Let's say i need to remove the nth element of the list "l" and push it at the beginning of list "out".
The best i could figure out is :
Code: Select all
(progn
(push (nth n l) out)
(setf l (delete (nth n l) l))
But it looks pretty inefficient to me. "(nth n l)" is evaluated twice and "(delete (nth n l) l)" doesn't sound good.
Is there a better way to do that ?
Re: moving an element of a list to another list
Posted: Thu Oct 28, 2010 2:12 pm
by nuntius
Is there a better way? Yes, but you have to write it at a lower level (doing your own loop over the list, your own cdr manipulations, etc.).
If this isn't a performance issue, I would focus on getting the rest of your code working before worrying about this. At that time, the answer may be to optimize this code, or it may be to use a different data structure.
Re: moving an element of a list to another list
Posted: Thu Oct 28, 2010 5:38 pm
by gugamilare
Destructive:
Code: Select all
(if (zerop n)
(progn (push (car l) out)
(setf l (cdr l)))
(let ((prevcdr (nthcdr (- n 1) l)))
(push (cadr prevcdr) out)
(setf (cdr prevcdr) (cddr prevcdr))))
Non-destructive:
Code: Select all
(progn
(push (nth n l) out)
(setf l (nconc (subseq l 0 n) (nthcdr (1+ n) l))))
I'd say that the biggest problem with that code is not preformance, but it will delete multiple copies of the same element if it is found. If that is what you want, use let to store the nth value instead of computing it twice.
Re: moving an element of a list to another list
Posted: Fri Oct 29, 2010 12:33 am
by vernonsolo
Thanks Gugamilare, the first one look like what i was looking for.
I was hoping there was a standard function that could help in this kind of case. Something like "pop" but which can work in the middle of a list. But now i realize that the "one way" nature of the lists makes this difficult to do.
gugamilare wrote:
I'd say that the biggest problem with that code is not preformance, but it will delete multiple copies of the same element if it is found. If that is what you want, use let to store the nth value instead of computing it twice.
Good point ! In my case this was not an issue, i forgot to mention that all the elements of l are different. But it is sure something to be aware of.
Re: moving an element of a list to another list
Posted: Fri Oct 29, 2010 4:06 am
by gugamilare
vernonsolo wrote:Thanks Gugamilare, the first one look like what i was looking for.
I was hoping there was a standard function that could help in this kind of case. Something like "pop" but which can work in the middle of a list. But now i realize that the "one way" nature of the lists makes this difficult to do.
Haven't you learned Lisp yet?
Non-destructive:
Code: Select all
(defmacro pop-nth (n l)
(with-gensyms (nvar lvar ncdr)
`(let* ((,nvar ,n)
(,lvar ,l)
(,nthcdr (nthcdr ,nvar ,lvar)))
(prog1 (car ,nthcdr)
(setf ,l (nconc (subseq ,lvar 0 ,nvar)
(cdr ,nthcdr)))))))
Destructive:
Code: Select all
(defmacro npop-nth (n l)
(with-gensyms (nvar lvar prevcdr)
`(let ((,nvar ,n)
(,lvar ,l))
(if (zerop ,nvar)
(prog1 (car ,lvar)
(setf ,l (cdr ,lvar)))
(let ((,prevcdr (nthcdr (- ,nvar 1) ,varl)))
(prog1 (cadr ,prevcdr)
(setf (cdr ,prevcdr) (cddr ,prevcdr))))))))
Note that I just wrote that, I didn't test anything, but that might be enough to get the idea
Re: moving an element of a list to another list
Posted: Fri Oct 29, 2010 9:57 am
by vernonsolo
gugamilare wrote:
Haven't you learned Lisp yet?
I just started few days ago
I tried the non-destructive one in my program, but i had problem with 'with-gensyms' so i modified it to :
Code: Select all
(defmacro pop-nth (n l)
(let ((nvar (gensym)) (lvar (gensym)) (ncdr (gensym)))
`(let* ((,nvar ,n)
(,lvar ,l)
(,ncdr (nthcdr ,nvar ,lvar)))
(prog1 (car ,ncdr)
(setf ,l (nconc (subseq ,lvar 0 ,nvar)
(cdr ,ncdr)))))))
then my ugly code is replaced by :
and it works ! it's even like 5 or 10% faster
It is my first macro
Thanks for your help
PS: then i tried the destructive one and gained 20% speed from the original
Re: moving an element of a list to another list
Posted: Fri Oct 29, 2010 11:12 am
by gugamilare
vernonsolo wrote:PS: then i tried the destructive one and gained 20% speed from the original
If you try it with bigger lists, the performance gain will be even greater
Re: moving an element of a list to another list
Posted: Thu Nov 04, 2010 8:35 pm
by Warren Wilkinson
I probably wouldn't write a macro for this problem, I would isolate the problem of 'stealing' an item from a list:
Code: Select all
(defmacro awhen (test &rest code)
`(let ((it ,test))
(when it ,@code)))
(defun steal (n list)
(awhen (nthcdr (1- n) list)
(prog1 (cadr it) (rplacd it (cddr it)))))
And it is used like this:
Code: Select all
(defvar *test-input* '(a b c d e f g))
(steal 1 *test-input*) ;; Returns 'b, *test-output* is now (a c d e f g)
There is one problem --- what happens if you steal item 0 from a list? It won't work, and it cannot be made to work because steal is a utility function, and it would be unwise to hardcode it so it would setf *test-input* to (cdr *test-input*) for the zero case. However, we can write a function using steal that has this knowledge.
Code: Select all
(defvar *input* '(a b c d e))
(defvar *output* nil)
(defun steal/pop (n)
(if (and *test-input* (zerop n))
(setf *output* (cons (car *input*) *output*)
*input* (cdr *input*))
(and (< n (length *input*)) (push (steal n *input*) *output*))))
This method does exactly what you describe. It steals the Nth element from *input*, and pushes it onto *output*, I also made it do bounds checking so it won't do anything if N is larger than *input*. The routine is hardcoded to reference those external variables, which is ideal because its simple.
If you have a number of lists that you need to modify, and you don't want to have a customized steal routine for each one, you can use a sentinal value like so:
Code: Select all
(defvar *new-input* '(sentinal a b c d e))
By putting a sentinal value in as item 0, we have no reason to ever require a (steal 0 *new-input*). This works fine so long as we remember to perform all other operations (like length, find, position, etc) upon (cdr *new-input*) and not the full *new-input*.
Re: moving an element of a list to another list
Posted: Fri Nov 05, 2010 4:49 am
by vernonsolo
Thanks Warren for the suggestions, it was very interesting. I think it is always good to know more than one way to do something
This "awhen" macro... I cannot count how many time i had to use this mechanism and yet i never thought of doing a macro out of it, thanks for that too
Re: moving an element of a list to another list
Posted: Fri Nov 05, 2010 10:12 am
by Warren Wilkinson
The 'a' stands for anamorphic. Paul Graham's 'On Lisp' has it (and anamorphic if, cond, etc), but I think the technique is older than that still. PG also has the definition of 'with-gensyms'. I won't go into details since PG explains it in that book, which is freely available as a downloadable pdf at
http://www.paulgraham.com/onlisp.html.