Hi,
I need to destructively remove the last item of a list.
I've written this macro for it:
(defmacro dellast (lst)
`(setf ,lst (reverse (cdr (reverse ,lst)))))
Now since I do two reverse operations, I doubt this is an efficient
solution.
What would be the most efficient solution?
By the way, this is NOT a school assignment. Don't insult me by saying it
is. My school assignment is solving n-queens using chronological
backtracking and now I'm optimizing my code.
Thanks,
- Wouter
"Wouter Lievens" <·········@telefragged.com> wrote in message
······························@news.skynet.be...
> Hi,
>
> I need to destructively remove the last item of a list.
> I've written this macro for it:
>
> (defmacro dellast (lst)
> `(setf ,lst (reverse (cdr (reverse ,lst)))))
>
> Now since I do two reverse operations, I doubt this is an efficient
> solution.
> What would be the most efficient solution?
How are you building the list? If you're working on chronological
backtracking,
I assume you are appending to the end of the list. Why not add to the front
of the list
and just use REST to shorten the list instead, both operations are a lot
more
efficient than working on the end of a list. You can always use REVERSE
on the result when you need to display it
--
Geoff
"Wouter Lievens" <·········@telefragged.com> writes:
> I need to destructively remove the last item of a list.
> I've written this macro for it:
>
> (defmacro dellast (lst)
> `(setf ,lst (reverse (cdr (reverse ,lst)))))
First, this operator is not destructive in the normal (lisp) sense of
that word. Dellast will modify a _variable_ (well, actually, a place),
but the list that the variable originally held will not be modified.
Second, in terms of optimizing lisp code, this is a poor attempt since
you actually copy the list twice (by reverse), when no copying is
necessary. Since you're explicitly looking for a destructive
operation, at least use the destructive version of reverse, nreverse.
Third, removing a tail from a list is already supported in lisp, both
in destructive (nbutlast) and non-destructive (butlast) mode. This is
how you destructively remove the last item of a list:
(setf <var> (nbutlast <var>))
--
Frode Vatvedt Fjeld
"Frode Vatvedt Fjeld" <······@cs.uit.no> schreef in bericht
···················@vserver.cs.uit.no...
> "Wouter Lievens" <·········@telefragged.com> writes:
>
> > I need to destructively remove the last item of a list.
> > I've written this macro for it:
> >
> > (defmacro dellast (lst)
> > `(setf ,lst (reverse (cdr (reverse ,lst)))))
>
> First, this operator is not destructive in the normal (lisp) sense of
> that word. Dellast will modify a _variable_ (well, actually, a place),
> but the list that the variable originally held will not be modified.
>
> Second, in terms of optimizing lisp code, this is a poor attempt since
> you actually copy the list twice (by reverse), when no copying is
> necessary. Since you're explicitly looking for a destructive
> operation, at least use the destructive version of reverse, nreverse.
>
> Third, removing a tail from a list is already supported in lisp, both
> in destructive (nbutlast) and non-destructive (butlast) mode. This is
> how you destructively remove the last item of a list:
>
> (setf <var> (nbutlast <var>))
>
> --
> Frode Vatvedt Fjeld
Thanks for the help. In fact I found out a few minutes after I asked it
here, that setf on butlast is what I need. I used a macro to easen the
typing.
My program finds all 92 8-queens solutions in 110 ms (compiled, in ACL6.2).
Is that a good result?
"Wouter Lievens" <·········@telefragged.com> writes:
> My program finds all 92 8-queens solutions in 110 ms (compiled, in ACL6.2).
> Is that a good result?
If you need all 92 answers in less than 10ms, that's terrible, but if
there is no urgency, 110 ms ought to be adequate.
Joe Marshall <···@ccs.neu.edu> writes:
> "Wouter Lievens" <·········@telefragged.com> writes:
>
> > My program finds all 92 8-queens solutions in 110 ms (compiled, in
> > ACL6.2). Is that a good result?
>
> If you need all 92 answers in less than 10ms, that's terrible, but
> if there is no urgency, 110 ms ought to be adequate.
For very nervous and impatient people, here is a solution that runs
faster:
(defconstant +all+ #xFF)
(deftype row ()
`(unsigned-byte 8))
(deftype board ()
`(simple-array row (8)))
(deftype board-index ()
`(integer 0 7))
(defparameter *solutions* nil)
(defun try (ld cols rd buf depth)
(declare (row ld cols rd)
(board buf)
(board-index depth))
(if (= cols +all+)
(push (copy-seq buf) *solutions*)
(let ((poss (logand +all+
(lognot (logior ld cols rd)))))
(declare (row poss))
(loop until (zerop poss) do
(let ((bit (logand poss (- poss))))
(declare (row bit))
(decf poss bit)
(setf (aref buf depth) bit)
(try (logand +all+ (ash (logior ld bit) 1))
(logior cols bit)
(logand +all+ (ash (logior rd bit) -1))
buf
(1+ depth)))))))
(defun solve ()
(let ((*solutions* nil)
(buf (make-array 8 :element-type 'row :initial-element 0)))
(try 0 0 0 buf 0)
*solutions*))
(defun print-solutions (solutions)
(dolist (solution solutions)
(loop for byte across solution do
(format t "~&~8,'0B" byte))
(fresh-line)
(terpri)))
Invoke (print-solutions (solve)). It uses ideas from
http://www.cl.cam.ac.uk/users/mr/backtrk.pdf
QUEENS 38 > (time (length (solve)))
Timing the evaluation of (LENGTH (SOLVE))
user time = 0.000
system time = 0.000
Elapsed time = 0:00:00
Allocation = 2976 bytes standard / 1012 bytes fixlen
0 Page faults
92
If that is still too slow, you might add an OPTIMIZE declaration ;-)
There are also two LOGAND calls that can still be optimized away, for
instance (but correct some type declarations, then).
Regards,
--
Nils G�sche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
Nils Goesche <······@cartan.de> writes:
> (let ((poss (logand +all+
> (lognot (logior ld cols rd)))))
Sorry, but I simply cannot let this *ugliness* go uncorrected.
As I have already told some people by Email, this should be
written as
> (let ((poss (logandc2 +all+ (logior ld cols rd))))
I have no idea why I still think in C when bit-fiddling,
especially as the Assembler I usually deal with /has/ an opcode
for LOGANDC2 (called `bic�) and Lisp's bit-fiddling functions are
much more useful and powerful than C's :-(
Sorry,
--
Nils G�sche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID #xD26EF2A0
"Wouter Lievens" <·········@telefragged.com> wrote in message
······························@news.skynet.be...
> Hi,
>
> I need to destructively remove the last item of a list.
CL-USER 11 > (setf foo (list 'a 'b 'c))
(A B C)
CL-USER 12 > (nbutlast foo)
(A B)
CL-USER 13 > foo
(A B)
Should do the trick!
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
"Coby Beck" <·····@mercury.bc.ca> schreef in bericht
··················@otis.netspace.net.au...
>
> "Wouter Lievens" <·········@telefragged.com> wrote in message
> ······························@news.skynet.be...
> > Hi,
> >
> > I need to destructively remove the last item of a list.
>
> CL-USER 11 > (setf foo (list 'a 'b 'c))
> (A B C)
>
> CL-USER 12 > (nbutlast foo)
> (A B)
>
> CL-USER 13 > foo
> (A B)
>
> Should do the trick!
>
> --
> Coby Beck
> (remove #\Space "coby 101 @ bigpond . com")
That was fast!
Thanks!!!
"Coby Beck" <·····@mercury.bc.ca> schreef in bericht
··················@otis.netspace.net.au...
>
> "Wouter Lievens" <·········@telefragged.com> wrote in message
> ······························@news.skynet.be...
> > Hi,
> >
> > I need to destructively remove the last item of a list.
>
> CL-USER 11 > (setf foo (list 'a 'b 'c))
> (A B C)
>
> CL-USER 12 > (nbutlast foo)
> (A B)
>
> CL-USER 13 > foo
> (A B)
>
> Should do the trick!
>
> --
> Coby Beck
> (remove #\Space "coby 101 @ bigpond . com")
I'm sorry, in fact it doesn't do the trick.
I do need to set the list variable with an altered (ie without last item)
cope of the original list.
So I'm going for the macro. Is there a NON-destructive version of NBUTLAST?
Bye and thanks,
"Wouter Lievens" <·········@telefragged.com> writes:
> "Coby Beck" <·····@mercury.bc.ca> schreef:
> >
> > "Wouter Lievens" <·········@telefragged.com> wrote:
> > >
> > > I need to destructively remove the last item of a list.
> >
> > CL-USER 11 > (setf foo (list 'a 'b 'c))
> > (A B C)
> >
> > CL-USER 12 > (nbutlast foo)
> > (A B)
> >
> > CL-USER 13 > foo
> > (A B)
> >
> > Should do the trick!
>
>
> I'm sorry, in fact it doesn't do the trick.
> I do need to set the list variable with an altered (ie without last item)
> cope of the original list.
It would seem easier to just use a setq or setf with nbutlast. The
difference between
(dellast my-var)
and
(setq my-var (nbutlast my-var))
is really small, and it makes both the destructive nature of the
operation and the side effect of altering the variable value immediately
explicit in the code.
> So I'm going for the macro. Is there a NON-destructive version of NBUTLAST?
BUTLAST is the non-destructive version.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
"Coby Beck" <·····@mercury.bc.ca> schreef in bericht
··················@otis.netspace.net.au...
>
> "Wouter Lievens" <·········@telefragged.com> wrote in message
> ······························@news.skynet.be...
> > Hi,
> >
> > I need to destructively remove the last item of a list.
>
> CL-USER 11 > (setf foo (list 'a 'b 'c))
> (A B C)
>
> CL-USER 12 > (nbutlast foo)
> (A B)
>
> CL-USER 13 > foo
> (A B)
>
> Should do the trick!
>
> --
> Coby Beck
> (remove #\Space "coby 101 @ bigpond . com")
Okay I got it now, it's BUTLAST. Thanks.
[Wouter Lievens]
: Hi,
:
: I need to destructively remove the last item of a list.
: I've written this macro for it:
:
: (defmacro dellast (lst)
: `(setf ,lst (reverse (cdr (reverse ,lst)))))
You have already learned about BUTLAST, but there is another issue you
should be aware of; multiple evaluation. As tempting it is to define the
macro as
(defmacro dellast (lst)
`(setf ,lst (butlast ,lst))
this is dangerous, in fact, it is plain wrong. It is the dangerous kind
of wrongness that will work in 99.5% of the cases and then have you
bug-hunting for hours or days when you encounter a case from the last 0.5%
that doesn't work. Consider the example (dellast (aref a (incf i))), and
notice that i will be incremented twice.
Defining macros on top of SETF is generally tricky business. For a good
overview, I recommend the chapter on generalized variables from Paul
Graham's "On Lisp". In this particular case, there is a simple solution:
(define-modify-macro dellast () butlast)
This does all the magic of avoiding multiple evaluation for you. For
completeness, you should probably do this:
(define-modify-macro dellast (&optional (n 1)) butlast)
so that DELLAST matches the behavior of BUTLAST, e.g (dellast x 3) deletes
the last 3 elements.
--
Knut Arild Erstad
Don't try to solve serious matters in the middle of the night.
-- Philip K. Dick
"Wouter Lievens" <·········@telefragged.com> wrote in message news:<·························@news.skynet.be>...
> Hi,
>
> I need to destructively remove the last item of a list.
> I've written this macro for it:
>
> (defmacro dellast (lst)
> `(setf ,lst (reverse (cdr (reverse ,lst)))))
This is not destructive on the list; it destructively modifies the
place denoted by the expression LST.
A destructive list manipulation would be one which would actually
modify the second to last cons cell of the list to set its CDR field
to NIL. You are here computing a new list, and then assigning it to
the place which pointed to the old one.
Anyway, Lisp already has the function you are looking for; look up
BUTLAST in the HyperSpec. What you are trying to do can be coded as:
(setf list (butlast list))
Note that you can use the symbol LIST as a variable name, by the way;
you don't need to invent contractions.