hello,
I am wondering how to efficiently implement non destructive operations
on lists. Am i supposed to invoque copy-list and then destructively
work on this copy ?
Eg imagine I want to define a my-butlast function that behaves quite
such as the butlast one. I could do something like this:
(defun my-butlast (list &optional (n 1))
(if (> (length list) n)
(let ((working-copy (copy-list list)))
(setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
working-copy)
nil))
Is that correct and does this make sense ?
-Nicolas
············@gmail.com writes:
> hello,
>
> I am wondering how to efficiently implement non destructive operations
> on lists. Am i supposed to invoque copy-list and then destructively
> work on this copy ?
> Eg imagine I want to define a my-butlast function that behaves quite
> such as the butlast one. I could do something like this:
>
> (defun my-butlast (list &optional (n 1))
> (if (> (length list) n)
> (let ((working-copy (copy-list list)))
> (setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
> working-copy)
> nil))
>
> Is that correct and does this make sense ?
Well, you could use that approach. I note that in the algorithm you
show above, that you have to traverse the input LIST roughly FOUR
times. Two times for LENGTH (although you could save that in a variable
and eliminate one of the calls), once for COPY-LIST and essentially
another time for NTHCDR -- under the assumption that N is small in
comparison to the length of the input list.
A simpler solution that only traverses the list slightly less than TWO
times and coincidentally avoids (overt)* destructive operations entirely
is the following. Note that it makes use of the fact that REPEAT is
defined for negative values. This version is also robust enough to
properly handle negative values of N.
(defun my-butlast2 (list &optional (n 1))
(loop repeat (- (length list) n)
for item in list
collect item))
This, by the way, would be a good choice for you to re-implement using
DOTIMES and doing your own destructive handling of the tail pointer. It
will be a bit more complicated than the example above, since the hidden
machinery of the LOOP macro will need to be duplicated.
Another choice that also comes close in performance is the following
very simple formulation which goes through the list TWO times, again
ignoring N as being likely to be small. It doesn't even need to compute
the length. It will throw an error for negative values of N.
(defun my-butlast3 (list &optional (n 1))
(nreverse (nthcdr n (reverse list))))
* I added "overt" because LOOP almost certainly uses destructive
operations internally to efficiently concatenate values onto the end
of the collection list.
--
Thomas A. Russ, USC/Information Sciences Institute
On 22 mai, 19:30, ····@sevak.isi.edu (Thomas A. Russ) wrote:
> ············@gmail.com writes:
> > hello,
>
> > I am wondering how to efficiently implement non destructive operations
> > on lists. Am i supposed to invoque copy-list and then destructively
> > work on this copy ?
> > Eg imagine I want to define a my-butlast function that behaves quite
> > such as the butlast one. I could do something like this:
>
> > (defun my-butlast (list &optional (n 1))
> > (if (> (length list) n)
> > (let ((working-copy (copy-list list)))
> > (setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
> > working-copy)
> > nil))
>
> > Is that correct and does this make sense ?
>
> Well, you could use that approach. I note that in the algorithm you
> show above, that you have to traverse the input LIST roughly FOUR
> times. Two times for LENGTH (although you could save that in a variable
> and eliminate one of the calls), once for COPY-LIST and essentially
> another time for NTHCDR -- under the assumption that N is small in
> comparison to the length of the input list.
>
> A simpler solution that only traverses the list slightly less than TWO
> times and coincidentally avoids (overt)* destructive operations entirely
> is the following. Note that it makes use of the fact that REPEAT is
> defined for negative values. This version is also robust enough to
> properly handle negative values of N.
>
> (defun my-butlast2 (list &optional (n 1))
> (loop repeat (- (length list) n)
> for item in list
> collect item))
>
> This, by the way, would be a good choice for you to re-implement using
> DOTIMES and doing your own destructive handling of the tail pointer. It
> will be a bit more complicated than the example above, since the hidden
> machinery of the LOOP macro will need to be duplicated.
>
> Another choice that also comes close in performance is the following
> very simple formulation which goes through the list TWO times, again
> ignoring N as being likely to be small. It doesn't even need to compute
> the length. It will throw an error for negative values of N.
>
> (defun my-butlast3 (list &optional (n 1))
> (nreverse (nthcdr n (reverse list))))
>
> * I added "overt" because LOOP almost certainly uses destructive
> operations internally to efficiently concatenate values onto the end
> of the collection list.
>
Ok, so (and iterating collecting) or clever reuse of good old standard
functions ;)
Thanks.
············@gmail.com wrote:
> hello,
>
> I am wondering how to efficiently implement non destructive operations
> on lists. Am i supposed to invoque copy-list and then destructively
> work on this copy ?
> Eg imagine I want to define a my-butlast function that behaves quite
> such as the butlast one. I could do something like this:
>
> (defun my-butlast (list &optional (n 1))
> (if (> (length list) n)
> (let ((working-copy (copy-list list)))
> (setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
> working-copy)
> nil))
>
> Is that correct and does this make sense ?
a. You are aware that butlast is non-destructive, right? ie, You are
just asking this as an example?
b. The above looks OK (I did not check for bugs) but why copy the whole
list and then truncate, why not copy as much as needed?
(loop for i below n
for elt in list
collect elt)
(not tested)
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
On 22 mai, 18:13, Ken Tilton <···········@optonline.net> wrote:
> ············@gmail.com wrote:
> > hello,
>
> > I am wondering how to efficiently implement non destructive operations
> > on lists. Am i supposed to invoque copy-list and then destructively
> > work on this copy ?
> > Eg imagine I want to define a my-butlast function that behaves quite
> > such as the butlast one. I could do something like this:
>
> > (defun my-butlast (list &optional (n 1))
> > (if (> (length list) n)
> > (let ((working-copy (copy-list list)))
> > (setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
> > working-copy)
> > nil))
>
> > Is that correct and does this make sense ?
>
> a. You are aware that butlast is non-destructive, right? ie, You are
> just asking this as an example?
indeed
> b. The above looks OK (I did not check for bugs) but why copy the whole
> list and then truncate, why not copy as much as needed?
>
> (loop for i below n
> for elt in list
> collect elt)
>
Of course i should have taken another example. The one I choosed is
the worst ever!
Instead, consider implementing a function such as remove-if (for list
only).
-Nicolas
············@gmail.com writes:
> On 22 mai, 18:13, Ken Tilton <···········@optonline.net> wrote:
> > ············@gmail.com wrote:
> > > hello,
> >
> > > I am wondering how to efficiently implement non destructive operations
> > > on lists. Am i supposed to invoque copy-list and then destructively
> > > work on this copy ?
> > > Eg imagine I want to define a my-butlast function that behaves quite
> > > such as the butlast one. I could do something like this:
> >
> > > (defun my-butlast (list &optional (n 1))
> > > (if (> (length list) n)
> > > (let ((working-copy (copy-list list)))
> > > (setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
> > > working-copy)
> > > nil))
> >
> > > Is that correct and does this make sense ?
> >
> > a. You are aware that butlast is non-destructive, right? ie, You are
> > just asking this as an example?
>
> indeed
>
> > b. The above looks OK (I did not check for bugs) but why copy the whole
> > list and then truncate, why not copy as much as needed?
> >
> > (loop for i below n
N is the number of items to remove from the end of the list, not the
number to keep. It would have to be (- (length list) n) instead.
> > for elt in list
> > collect elt)
> >
>
> Of course i should have taken another example. The one I choosed is
> the worst ever!
Not necessarily. See my other post recommending a DOTIMES approach to
learn how to use the destructive list operations for it.
> Instead, consider implementing a function such as remove-if (for list
> only).
(defun my-remove-if (list test)
(loop for elt in list
unless (funcall test elt)
collect elt))
with elaboration for key function, count, etc., if you want the full
common lisp function.
--
Thomas A. Russ, USC/Information Sciences Institute
P� Thu, 22 May 2008 18:43:38 +0200, skrev <············@gmail.com>:
> Instead, consider implementing a function such as remove-if (for list
> only).
Think of it as collect-if-not and you see the best way immediately.
(defun my-remove-if (function list)
(let (result)
(dolist (element list)
(when (not (funcall function element))
(push element result))
(nreverse result)) ; destructive operation is fine here as we are
working on a copy already
For example (untested).
For loopers
(loop for element in list when (not (funcall function element)) collect
element)
Non destructive functions generally iterate over the list and create a new
one rather than make a copy and destructively modify the copy.
--------------
John Thingstad
On 22 mai, 19:35, "John Thingstad" <·······@online.no> wrote:
> På Thu, 22 May 2008 18:43:38 +0200, skrev <············@gmail.com>:
>
> > Instead, consider implementing a function such as remove-if (for list
> > only).
>
> Think of it as collect-if-not and you see the best way immediately.
>
> (defun my-remove-if (function list)
> (let (result)
> (dolist (element list)
> (when (not (funcall function element))
> (push element result))
> (nreverse result)) ; destructive operation is fine here as we are
> working on a copy already
>
> For example (untested).
>
> For loopers
> (loop for element in list when (not (funcall function element)) collect
> element)
>
> Non destructive functions generally iterate over the list and create a new
> one rather than make a copy and destructively modify the copy.
>
Iterating and collecting makes very much sense.
Thanks.
-Nicolas
From: Kent M Pitman
Subject: Re: non destructive operations on lists
Date:
Message-ID: <ulk21zw2x.fsf@nhplace.com>
············@gmail.com writes:
> hello,
>
> I am wondering how to efficiently implement non destructive operations
> on lists.
(Is this for homework?)
Your question has nothing to do with Lisp, really, it has to do with
algorithms. Lisp is just the vehicle of implementation for whatever
strategy you attempt. The answer would be the same the same in most
languages if they had equivalent data structures (by which I don't
mean equivalently-named data structures; some other languages offer a
list datatype that isn't like a lisp list and so is algorithmically
different do deal with).
> Am i supposed to invoque copy-list and then destructively
> work on this copy ?
There is no "supposed to" here. Common Lisp supports a number of choices.
> Eg imagine I want to define a my-butlast function that behaves quite
> such as the butlast one. I could do something like this:
>
> (defun my-butlast (list &optional (n 1))
> (if (> (length list) n)
> (let ((working-copy (copy-list list)))
> (setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
> working-copy)
> nil))
>
> Is that correct and does this make sense ?
Very minor point: Always beware of SETF of CDR of something when the
possibility exists of a NIL getting in there. Although it's probably
not a case that matters a lot to you, (my-butlast '(a) -1) doesn't
work so well in your code above. That doesn't make your general
approach bad--it just means there's an extra case to watch for.
Both the above and the one I offer below are O(m), where m is the
length of the list, though there may be minor degrees of difference in
the detail that is below the algorthmic complexity radar and yet still
may matter once in a while. The main difference here is just
stylistic, but maybe this is the kind of thing you're looking for:
(defun my-butlast (list &optional (n 1))
(check-type n (integer 0) "a valid list index")
(do ((rabbit (nthcdr n list) (cdr rabbit))
(hare list (cdr hare))
(result '() (cons (first hare) result)))
((null rabbit) (nreverse result))))
Of course, if you wanted to not use destructive operations for some
religious reason, you could substitute reverse for nreverse and you'd
still be O(m).
On May 23, 2:46 am, Kent M Pitman <······@nhplace.com> wrote:
> ············@gmail.com writes:
> > hello,
>
> > I am wondering how to efficiently implement non destructive operations
> > on lists.
>
> (Is this for homework?)
No. I have to make a tool for internal use and they let me the choice
in the language. I decided to turn this into a nice way to learn Lisp
(although I could have use programing languages I am already familiar
with); reading books is fine but useless without practice.
> Your question has nothing to do with Lisp, really, it has to do with
> algorithms. Lisp is just the vehicle of implementation for whatever
> strategy you attempt. The answer would be the same the same in most
> languages if they had equivalent data structures (by which I don't
> mean equivalently-named data structures; some other languages offer a
> list datatype that isn't like a lisp list and so is algorithmically
> different do deal with).
>
> > Am i supposed to invoque copy-list and then destructively
> > work on this copy ?
>
> There is no "supposed to" here. Common Lisp supports a number of choices.
As for quite a lot of other programing languages. This was meant to be
understood as a request for idiomatic Lisp ways. I have imperative
programing deeply anchored in mind and would like to avoid Lisp
conventional pitfalls.
>
> > Eg imagine I want to define a my-butlast function that behaves quite
> > such as the butlast one. I could do something like this:
>
> > (defun my-butlast (list &optional (n 1))
> > (if (> (length list) n)
> > (let ((working-copy (copy-list list)))
> > (setf (cdr (nthcdr (- (length list) n 1) working-copy)) nil)
> > working-copy)
> > nil))
>
> > Is that correct and does this make sense ?
>
> Very minor point: Always beware of SETF of CDR of something when the
> possibility exists of a NIL getting in there. Although it's probably
> not a case that matters a lot to you, (my-butlast '(a) -1) doesn't
> work so well in your code above. That doesn't make your general
> approach bad--it just means there's an extra case to watch for.
Yes, that was an not tested/optimized example. Just note the butlast
function (at least on my machine and using sbcl) also raise an error
with your example.
>
> Both the above and the one I offer below are O(m), where m is the
> length of the list, though there may be minor degrees of difference in
> the detail that is below the algorthmic complexity radar and yet still
> may matter once in a while. The main difference here is just
> stylistic, but maybe this is the kind of thing you're looking for:
>
> (defun my-butlast (list &optional (n 1))
> (check-type n (integer 0) "a valid list index")
> (do ((rabbit (nthcdr n list) (cdr rabbit))
> (hare list (cdr hare))
> (result '() (cons (first hare) result)))
> ((null rabbit) (nreverse result))))
>
> Of course, if you wanted to not use destructive operations for some
> religious reason, you could substitute reverse for nreverse and you'd
> still be O(m).
Rabbits and hares ... I missed the point, sorry. Could you please
explain ?
-Nicolas
From: Kent M Pitman
Subject: Re: non destructive operations on lists
Date:
Message-ID: <uk5hlw3yt.fsf@nhplace.com>
············@gmail.com writes:
> > (defun my-butlast (list &optional (n 1))
> > (check-type n (integer 0) "a valid list index")
> > (do ((rabbit (nthcdr n list) (cdr rabbit))
> > (hare list (cdr hare))
> > (result '() (cons (first hare) result)))
> > ((null rabbit) (nreverse result))))
> >
> > Of course, if you wanted to not use destructive operations for some
> > religious reason, you could substitute reverse for nreverse and you'd
> > still be O(m).
>
> Rabbits and hares ... I missed the point, sorry. Could you please
> explain ?
Oh, sorry, that's a bit random as variable names go, I suppose. Once
in a while, I get a little fanciful on that. There's an algorithm for
detecting circularity that involves a tortoise (slow) and a hare
(fast) in a race, where if the hare finds the tortoise ahead of him,
you know that it's because there was a circularity. And I was
thinking in that mode when i wrote this.
In this case, I had two runners racing down the same list and they're
really of about the same speed, so I picked the approximate synonyms
of rabbit and hare. [Probably someone will chime in and tell me these
denote different species and that my naming is bad, but I won't worry
about it.] Anyway, I put them in a race and gave one a head start
over the other [the by the number of elements to omit]. The favored
one [I chose the rabbit for this] will see the end of the list at the
right time to signal the other [the hare, who is equal in speed, but
lagging behind] to give up and stop. The results are accumulated by
the hare, so he ends up accumulating all but the last n results.