From: Emre Sevinc
Subject: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <8764qrv3fc.fsf@ileriseviye.org>
As I'm going through Norvig's PAIP, in Ch. 17 (where he
describes "A Line-Labeling program using the Waltz algorithm")
I came across a matrix-transpose function:
(defun matrix-transpose (matrix)
"Turn a matrix on its side."
(if matrix (apply #'mapcar #'list matrix)))
and it works fine:
(defparameter m1
'((1 0 0 0)
(1 0 0 0)
(1 0 0 0)))
CL-USER> (matrix-transpose m1)
((1 1 1) (0 0 0) (0 0 0) (0 0 0))
However the use of apply completely puzzled me!
Why? Because, when I look at CLHS and think like that:
(apply #'+ '(1 2 3)) ----> (+ 1 2 3)
OK, that means I give some function to apply and then I give
the arguments that this function will be applied to. Simple,
easy and life's fine.
However when I see:
(apply #'mapcar #'list matrix)
oops, what does that exactly mean?
Again I try to understand CLHS:
http://www.lisp.org/HyperSpec/Body/fun_apply.html
*apply* /function &rest args+/ => //result/***/
"Applies the function to args."
Fine, a function and arguments, so does that mean?:
(mapcar #'list m1)
CL-USER> (mapcar #'list m1)
(((1 0 0 0)) ((1 0 0 0)) ((1 0 0 0)))
Nope, we didn't have the transpose of the matrix.
Which means
(apply #'mapcar #'list matrix) IS NOT EQUIVALENT TO (mapcar #'list matrix)
which means I'm completely missing something, some basic
points. Thus I cannont fully understand the elegant solution
Norvig had provided.
Can somebody explain that matrix-transpose'u a little bit
and fill in the blank in a step-by-step manner and enlighten
me?
(apply #'mapcar #'list matrix) IS EQUIVALENT TO _____________
Happy hacking,
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Hi,
when you do
GI> (apply #'mapcar #'list '((0 1 2)
(4 5 6)
(7 8 9)))
((0 4 7) (1 5 8) (2 6 9))
everything is fine as is when you do :
GI> (mapcar #'list '(0 1 2) '(4 5 6) '(7 8 9))
((0 4 7) (1 5 8) (2 6 9))
so apply at the beginning means that mapcar will see 3 lists because
'(() () ())
used with apply means (mapcar #'list '(..) '(..) '(..)) instead of
(mapcar #'list '((..) (..) (..))) and this way mapcar works on rows
directly, grouping their elements with list function.
Hope it helps.
Karol
Emre Sevinc wrote:
> (apply #'mapcar #'list matrix) IS EQUIVALENT TO _____________
The MAPCAR function takes a variable number of arguments.
In most examples, you see MAPCAR being used to filter a single list
through a function. Each element passes through the function, and the
results are collected into a new list, which is essentially an image of
the old list under the function.
But MAPCAR actually can take two or more lists. In that case, the
function passed into MAPCAR is expected to take two or more arguments:
exactly as many arguments as there are lists! If you pass two lists,
the function has to accept two arguments; if you pass three lists, the
function has to take three arguments, and so on.
When there are these multiple lists, they are traversed by MAPCAR in
parallel. At each iteration, the next item is taken from each of the N
lists, and these items form N arguments to the function. The function
is called, and its return value is collected into the resulting list.
This is like a "zipper" effect. In the case where there are two lists,
you can imagine that the elements are the teeth of a zipper coming
together, as this example shows:
;; ``zip'' together two lists!
(mapcar #'list '(a b c) '(1 2 3)) -> '((A 1) (B 2) (C 3))
MAPCAR stops when it encounters the end of the shortest one of the
lists, which isn't an issue here since the rows are all of equal
length.
The APPLY function is needed in order to break apart the matrix into
multiple lists, so that each of its rows is passed as a separate list
argument to MAPCAR. Since MAPCAR processes the matrix row lists in
parallel, the matching elements from each row constitute a matrix
column! So the #'LIST function is called on the elements of successive
columns. Each column is turned into a list, and MAPCAR collects these
columns into a bigger list. So the result is a list of the matrix
columns, which are lists of the column elements.
A matrix is defined, under Norvig's representation, as a list of rows.
But what you have now is a list of the columns of the original matrix.
Those columns are thus interpreted as rows now, and so you have a
matrix transpose. The columns have become rows; the rows have become
columns. Transpose!
Crack the outside list, sweep over the rows in parallel, creating
columns, wrap the result back into a list.
From: Thomas A. Russ
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <ymir79fozyt.fsf@sevak.isi.edu>
Emre Sevinc <·····@bilgi.edu.tr> writes:
>
>
> As I'm going through Norvig's PAIP, in Ch. 17 (where he
> describes "A Line-Labeling program using the Waltz algorithm")
> I came across a matrix-transpose function:
>
> (defun matrix-transpose (matrix)
> "Turn a matrix on its side."
> (if matrix (apply #'mapcar #'list matrix)))
...
> However the use of apply completely puzzled me!
>
> Why? Because, when I look at CLHS and think like that:
>
> (apply #'+ '(1 2 3)) ----> (+ 1 2 3)
>
...
> Fine, a function and arguments, so does that mean?:
>
> (mapcar #'list m1)
>
> CL-USER> (mapcar #'list m1)
> (((1 0 0 0)) ((1 0 0 0)) ((1 0 0 0)))
>
> Nope, we didn't have the transpose of the matrix.
>
> Which means
>
> (apply #'mapcar #'list matrix) IS NOT EQUIVALENT TO (mapcar #'list matrix)
Correct. And for the same reason that (apply #'+ '(1 2 3)) is not
equivalent to (+ '(1 2 3)) but is instead equivalent to (+ 1 2 3).
The key is that apply applies a function to a LIST OF ARGUMENTS instead
of to a single argument. Taking your initial example where
M1 = '((1 0 0 0) (1 0 0 0) (1 0 0 0))
Then (apply #'mapcar #'list '((1 0 0 0) (1 0 0 0) (1 0 0 0)))
is equivalent to (mapcar #'list '(1 0 0 0) '(1 0 0 0) '(1 0 0 0))
where the application to a list of arguments effectively "removes one
level of list structure".
The fanciness of Norvig's technique is that it exploits the fact that
both MAPCAR and LIST take arbitrary numbers of arguments.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87u0eb7ymi.fsf@ileriseviye.org>
>>>>> "TAR" == Thomas A Russ <···@sevak.isi.edu> writes:
TAR> Emre Sevinc <·····@bilgi.edu.tr> writes:
>> Which means
>>
>> (apply #'mapcar #'list matrix) IS NOT EQUIVALENT TO (mapcar
>> #'list matrix)
TAR> Correct. And for the same reason that (apply #'+ '(1 2 3))
TAR> is not equivalent to (+ '(1 2 3)) but is instead equivalent
TAR> to (+ 1 2 3).
TAR> The key is that apply applies a function to a LIST OF
TAR> ARGUMENTS instead of to a single argument. Taking your
TAR> initial example where
TAR> M1 = '((1 0 0 0) (1 0 0 0) (1 0 0 0))
TAR> Then (apply #'mapcar #'list '((1 0 0 0) (1 0 0 0) (1 0 0 0)))
TAR> is equivalent to (mapcar #'list '(1 0 0 0) '(1 0 0 0) '(1 0 0
TAR> 0)) where the application to a list of arguments effectively
TAR> "removes one level of list structure".
TAR> The fanciness of Norvig's technique is that it exploits the
TAR> fact that both MAPCAR and LIST take arbitrary numbers of
TAR> arguments.
Thanks to you and to everybody (including the ones who wanted
to transpose me right away [hmm, the Turkish mathematical term
fits better with the intended meaning of the joke, doesn't it?])
who helped me understand what's going in that short and interesting
piece of code.
Happy hacking,
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Arthur Lemmens
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <op.s0dyygwuwpmq96@news.xs4all.nl>
Emre Sevinc <·····@bilgi.edu.tr> wrote:
> (defun matrix-transpose (matrix)
> "Turn a matrix on its side."
> (if matrix (apply #'mapcar #'list matrix)))
Yeah, that's a classic. I suppose it's one of the most complicated
programs of such a small size ;-)
> Can somebody explain that matrix-transpose'u a little bit
> and fill in the blank in a step-by-step manner and enlighten
> me?
>
> (apply #'mapcar #'list matrix) IS EQUIVALENT TO _____________
If ARGS is bound to the list (A B C D), then
(apply #'function arg args)
is equivalent to
(function arg 'A 'B 'C 'D)
So if MATRIX is bound to ((1 0 0 0) (1 0 0 0) (1 0 0 0)), then
(apply #'mapcar #'list matrix)
is equivalent to
(mapcar #'list '(1 0 0 0) '(1 0 0 0) '(1 0 0 0))
I hope this helps.
From: Peder O. Klingenberg
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <ksy83nct72.fsf@beto.netfonds.no>
Emre Sevinc <·····@bilgi.edu.tr> writes:
> (apply #'+ '(1 2 3)) ----> (+ 1 2 3)
So far, so good. Observe what happens in the textual representation:
the + gets "moved into" the list of arguments. Apply sort of unpacks
the last list in its arglist.
> (apply #'mapcar #'list matrix) IS NOT EQUIVALENT TO (mapcar #'list matrix)
No, it's not. If it was, using apply here would be superfluous, and
as you have seen, there's a reason Norvig put it in there.
But you don't follow your own logic here. If you spell out m1, it's
perhaps easier to see.
(apply #'mapcar #'list '((1 0 0 0)
(1 0 0 0)
(1 0 0 0)))
----> (by your own transform, above)
(mapcar #'list '(1 0 0 0)
'(1 0 0 0)
'(1 0 0 0))
The outermost list in the last argument to apply is unpacked.
Evaluate that expression, and voila, the transposed matrix.
CL-USER> (mapcar #'list '(1 0 0 0)
'(1 0 0 0)
'(1 0 0 0))
((1 1 1) (0 0 0) (0 0 0) (0 0 0))
...Peder...
--
This must be Thursday. I never could get the hang of Thursdays.
From: Bulent Murtezaoglu
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <874q6b9z38.fsf@p4.internal>
>>>>> "ES" == Emre Sevinc <·····@bilgi.edu.tr> writes:
ES> As I'm going through Norvig's PAIP, in Ch. 17 (where he
ES> describes "A Line-Labeling program using the Waltz algorithm")
ES> I came across a matrix-transpose function:
I'll transpose you alright! Had I known you'd asked here I would not
have typed up a response on the Turkish list.
Anyway, folks, in addition to what the others explained I also pointed out
that this is _not_ guaranteed to work and might unnecessarily bump into
the call-arguments-limit. With all due respect to Norvig, I don't
consider this code elegant. Any more opinions?
cheers,
BM
From: Arthur Lemmens
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <op.s0d0jqgswpmq96@news.xs4all.nl>
Bulent Murtezaoglu <··@acm.org> wrote:
>>>>>> "ES" == Emre Sevinc <·····@bilgi.edu.tr> writes:
>
> ES> As I'm going through Norvig's PAIP, in Ch. 17 (where he
> ES> describes "A Line-Labeling program using the Waltz algorithm")
> ES> I came across a matrix-transpose function:
[snip]
> Anyway, folks, in addition to what the others explained I also pointed out
> that this is _not_ guaranteed to work and might unnecessarily bump into
> the call-arguments-limit. With all due respect to Norvig, I don't
> consider this code elegant. Any more opinions?
I agree. So a nice exercise for Emre would be to write a version that
works regardless of call-arguments-limit. I suppose it wouldn't be a
one-liner anymore ;-)
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87r79fuwrp.fsf@ileriseviye.org>
>>>>> "AL" == Arthur Lemmens <········@xs4all.nl> writes:
AL> Bulent Murtezaoglu <··@acm.org> wrote:
>>>>>>> "ES" == Emre Sevinc <·····@bilgi.edu.tr> writes:
>>
ES> As I'm going through Norvig's PAIP, in Ch. 17 (where he
ES> describes "A Line-Labeling program using the Waltz algorithm")
ES> I came across a matrix-transpose function:
AL> [snip]
>> Anyway, folks, in addition to what the others explained I also
>> pointed out that this is _not_ guaranteed to work and might
>> unnecessarily bump into the call-arguments-limit. With all due
>> respect to Norvig, I don't consider this code elegant. Any
>> more opinions?
AL> I agree. So a nice exercise for Emre would be to write a
AL> version that works regardless of call-arguments-limit. I
AL> suppose it wouldn't be a one-liner anymore ;-)
My first shot was something like:
(defun matrix-transpose (matrix)
(let ((number-of-rows (length matrix))
(number-of-columns (length (car matrix))))
(loop for j from 0 to (1- number-of-columns)
do (loop for i from 0 to (1- number-of-rows)
collect (nth j (nth i matrix))))))
which did not exactly what I wanted.
But at least, it isn't one-liner anymore, as it's supposed
to be (or not) :)
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Arthur Lemmens
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <op.s0d5acdrwpmq96@news.xs4all.nl>
Emre Sevinc <·····@bilgi.edu.tr> wrote:
> My first shot was something like:
>
> (defun matrix-transpose (matrix)
> (let ((number-of-rows (length matrix))
> (number-of-columns (length (car matrix))))
> (loop for j from 0 to (1- number-of-columns)
> do (loop for i from 0 to (1- number-of-rows)
> collect (nth j (nth i matrix))))))
>
>
>
> which did not exactly what I wanted.
I won't spoil the fun immediately, but you're pretty close
(ignoring efficiency concerns of course, but that's not
the purpose of this exercise I think).
Hint: your outer LOOP only DOES something, but it doesn't
create anything to return.
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87mzk39lvo.fsf@ileriseviye.org>
>>>>> "AL" == Arthur Lemmens <········@xs4all.nl> writes:
AL> Emre Sevinc <·····@bilgi.edu.tr> wrote:
>> My first shot was something like:
>>
>> (defun matrix-transpose (matrix) (let ((number-of-rows (length
>> matrix)) (number-of-columns (length (car matrix)))) (loop for j
>> from 0 to (1- number-of-columns) do (loop for i from 0 to (1-
>> number-of-rows) collect (nth j (nth i matrix))))))
>>
>>
>>
>> which did not exactly what I wanted.
AL> I won't spoil the fun immediately, but you're pretty close
AL> (ignoring efficiency concerns of course, but that's not the
AL> purpose of this exercise I think).
AL> Hint: your outer LOOP only DOES something, but it doesn't
AL> create anything to return.
I'm still struggling with LOOP:
(defun matrix-transpose (matrix)
(let ((number-of-rows (length matrix))
(number-of-columns (length (car matrix)))
(my-list '()))
(loop for j from 0 to (1- number-of-columns)
do (loop for i from 0 to (1- number-of-rows)
collect (nth j (nth i matrix)) into my-list
return my-list)
collect my-list)))
I'm trying to tell my Lisp that OK, create a list in the inner
loop by collecting "(nth j (nth i matrix))"s and then
pass it to the outer loop which will collect those lists in order
to create a lists of lists (and return the result when exiting).
But then again I'm not done with it because I still
don't get the correct result:
CL-USER> (matrix-transpose m1)
(NIL NIL NIL NIL)
It looks like the outer loop is collecting 4 items,
but somehow it receives NIL from the inner loop.
How can I make that inner loop pass the constructed
list (the transposed row) to the outer loop?
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
> (defun matrix-transpose (matrix)
> (let ((number-of-rows (length matrix))
> (number-of-columns (length (car matrix)))
> (my-list '()))
> (loop for j from 0 to (1- number-of-columns)
> do (loop for i from 0 to (1- number-of-rows)
> collect (nth j (nth i matrix)) into my-list
> return my-list)
> collect my-list)))
>
You are nearly there, but have quite a bit of unneeded code. The key thing is
that loop will return what it is collecting, so your function could be written
as:
(defun matrix-transpose (matrix)
(loop for j below (length (car matrix)) collecting
(loop for i below (length matrix)
collecting (nth j (nth i matrix)))))
Note that the 'below' keyword does the bounds you were looking for.
There remains a complexity question. What is the big-O of your approach,
and can you improve on it?
-s
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87acg39hc1.fsf@ileriseviye.org>
>>>>> "SA" == Simon Alexander <··@spam.net> writes:
SA> Emre Sevinc <·····@bilgi.edu.tr> writes:
>> (defun matrix-transpose (matrix) (let ((number-of-rows (length
>> matrix)) (number-of-columns (length (car matrix))) (my-list
>> '())) (loop for j from 0 to (1- number-of-columns) do (loop for
>> i from 0 to (1- number-of-rows) collect (nth j (nth i matrix))
>> into my-list return my-list) collect my-list)))
>>
SA> You are nearly there, but have quite a bit of unneeded code.
SA> The key thing is that loop will return what it is collecting,
SA> so your function could be written as:
SA> (defun matrix-transpose (matrix) (loop for j below (length
SA> (car matrix)) collecting (loop for i below (length matrix)
SA> collecting (nth j (nth i matrix)))))
Thanks for drawing attention to "below" keyword.
SA> There remains a complexity question. What is the big-O of
SA> your approach, and can you improve on it?
Hmm, well, I'm not very good with the "complexity" calculations
however a quick check shows me that for my m1 which is 3x4
took 12 iterations, so I say that an MxN matrix will
be matrix-transposed in MN iterations. But as far as I
can remember I need to provide something like O(N^2)
to talk about the complexity of the algorithm. I don't know
how I can map that M and N into a single N to give an big-O
complexity value.
I wondered and did a comparison between Norvig's approach
and the LOOP approach
(defparameter m2
(loop for i below 500 collecting
(loop for j below 500 collect j)))
CL-USER> (time (matrix-transpose-norvig m2))
Evaluation took:
0.032 seconds of real time
0.022997 seconds of user run time
0.007999 seconds of system run time
0 page faults and
4,008,264 bytes consed.
CL-USER> (time (matrix-transpose-loop m2))
Evaluation took:
0.497 seconds of real time
0.483927 seconds of user run time
0.004 seconds of system run time
0 page faults and
2,007,040 bytes consed.
Now, on the surface it seems that LOOPing is more space efficient
while Norvig's code is much faster.
I'm a little bit confused...
PS: This Supercite in Emacs seems to break the formatting of
cited Lisp code! :(
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Hmm, well, I'm not very good with the "complexity" calculations
> however a quick check shows me that for my m1 which is 3x4
> took 12 iterations, so I say that an MxN matrix will
> be matrix-transposed in MN iterations. But as far as I
> can remember I need to provide something like O(N^2)
> to talk about the complexity of the algorithm. I don't know
> how I can map that M and N into a single N to give an big-O
> complexity value.
Well, there is no need to get to worried about the formal description. From a
practical point of view, the problem is the line
collecting (nth j (nth i matrix))
because nth has to walk the lists every time you call it. So, for example the
final call of this line touches every element in the matrix, the previous call
all but one, etc. It should be clear, though, that what you really want to do is
walk the columns once, and collect up rows as you go.
To expand on your experiment, what we are interested in is how the cost scales
with the size of the input
(defparameter m2 (loop repeat 100 collecting (loop repeat 100 collecting (random 100))))
(defparameter m3 (loop repeat 1000 collecting (loop repeat 100 collecting (random 100))))
(defparameter m4 (loop repeat 1000 collecting (loop repeat 1000 collecting (random 100))))
CL-USER> (prog1 nil (time (matrix-transpose-emre m2)))
Evaluation took:
0.003 seconds of real time
0.003 seconds of user run time
0.0 seconds of system run time
0 page faults and
81,920 bytes consed.
NIL
CL-USER> (prog1 nil (time (matrix-transpose-emre m3)))
Evaluation took:
0.118 seconds of real time
0.116982 seconds of user run time
0.001 seconds of system run time
0 page faults and
798,720 bytes consed.
NIL
CL-USER> (prog1 nil (time (matrix-transpose-emre m4)))
Evaluation took:
7.745 seconds of real time
7.351883 seconds of user run time
0.047993 seconds of system run time
0 page faults and
8,017,376 bytes consed.
NIL
Here is norvigs code
CL-USER> (prog1 nil (time (matrix-transpose-norvig m2)))
Evaluation took:
0.001 seconds of real time
0.001 seconds of user run time
0.0 seconds of system run time
0 page faults and
163,792 bytes consed.
NIL
CL-USER> (prog1 nil (time (matrix-transpose-norvig m3)))
Evaluation took:
0.007 seconds of real time
0.003 seconds of user run time
0.002999 seconds of system run time
0 page faults and
1,612,040 bytes consed.
NIL
CL-USER> (prog1 nil (time (matrix-transpose-norvig m4)))
Evaluation took:
0.112 seconds of real time
0.079988 seconds of user run time
0.027996 seconds of system run time
0 page faults and
16,019,840 bytes consed.
NIL
Finally, here is a loop based implementation where i avoid re-walking the
columns
CL-USER> (prog1 nil (time (matrix-transpose m2)))
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 page faults and
81,920 bytes consed.
NIL
CL-USER> (prog1 nil (time (matrix-transpose m3)))
Evaluation took:
0.003 seconds of real time
0.002999 seconds of user run time
0.0 seconds of system run time
0 page faults and
802,816 bytes consed.
NIL
CL-USER> (prog1 nil (time (matrix-transpose m4)))
Evaluation took:
0.032 seconds of real time
0.017998 seconds of user run time
0.013998 seconds of system run time
0 page faults and
8,024,064 bytes consed.
NIL
These numbers are only from a single run, so caveats apply.
I'll post the implementation if you'd like, but for now leave you to play with
it :)
s.
From: Thomas A. Russ
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <ymipsoxpnq7.fsf@sevak.isi.edu>
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Hmm, well, I'm not very good with the "complexity" calculations
> however a quick check shows me that for my m1 which is 3x4
> took 12 iterations, so I say that an MxN matrix will
> be matrix-transposed in MN iterations. But as far as I
> can remember I need to provide something like O(N^2)
> to talk about the complexity of the algorithm. I don't know
> how I can map that M and N into a single N to give an big-O
> complexity value.
Well, complexity measures can have more than one parameters, so one way
of stating this is O(M*N). If you want to have only a single
parameter, then you can do one of two things:
(1) Assume that the matrix dimensions are roughly comparable, in
other words, assume that M is almost equal to N and then you can
state O (M*N) as O(N^2).
(2) Define N' = max(M,N) and then have O(N'^2).
In effect, as far as big-O notation goes, any runtime that is like M*N
is effectively the same as N*N for purposes of complexity analysis.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Arthur Lemmens
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <op.s0ed2aa5wpmq96@news.xs4all.nl>
Emre Sevinc wrote:
> I'm still struggling with LOOP:
>
> (defun matrix-transpose (matrix)
> (let ((number-of-rows (length matrix))
> (number-of-columns (length (car matrix)))
> (my-list '()))
> (loop for j from 0 to (1- number-of-columns)
> do (loop for i from 0 to (1- number-of-rows)
> collect (nth j (nth i matrix)) into my-list
> return my-list)
> collect my-list)))
You're making things worse now ;-)
Your previous version of the inner loop was doing fine. The form:
(loop for i from 0 to (1- number-of-rows)
collect (nth j (nth i matrix)))
collects the elements a column into a list. AND IT RETURNS THAT
LIST.
So your inner loop returns a list each time it's called.
Now: how do you, ahem, collect those lists in the outer loop?
> How can I make that inner loop pass the constructed
> list (the transposed row) to the outer loop?
The inner loop already passes it to the outer loop. But the outer
loop shouldn't, ahem, do with the result what it does now.
(Let me know when you get bored with the hinting game.)
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87irur9ijd.fsf@ileriseviye.org>
>>>>> "AL" == Arthur Lemmens <········@xs4all.nl> writes:
AL> Emre Sevinc wrote:
>> I'm still struggling with LOOP:
>>
>> (defun matrix-transpose (matrix) (let ((number-of-rows (length
>> matrix)) (number-of-columns (length (car matrix))) (my-list
>> '())) (loop for j from 0 to (1- number-of-columns) do (loop for
>> i from 0 to (1- number-of-rows) collect (nth j (nth i matrix))
>> into my-list return my-list) collect my-list)))
AL> You're making things worse now ;-)
AL> Your previous version of the inner loop was doing fine. The
AL> form:
AL> (loop for i from 0 to (1- number-of-rows) collect (nth j
AL> (nth i matrix)))
AL> collects the elements a column into a list. AND IT RETURNS
AL> THAT LIST.
AL> So your inner loop returns a list each time it's called. Now:
AL> how do you, ahem, collect those lists in the outer loop?
Hmm, "collecting" what is returned...
(defun matrix-transpose (matrix)
(let ((number-of-rows (length matrix))
(number-of-columns (length (car matrix))))
(loop for j from 0 to (1- number-of-columns)
collecting (loop for i from 0 to (1- number-of-rows)
collect (nth j (nth i matrix))))))
Now it looks like it is working as expected. But I still
feel my mind a little "twisted" :)
Now, on to performance evaluations...
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Arthur Lemmens
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <op.s0ej1ik4wpmq96@news.xs4all.nl>
Emre Sevinc <·····@bilgi.edu.tr> wrote:
> AL> So your inner loop returns a list each time it's called. Now:
> AL> how do you, ahem, collect those lists in the outer loop?
>
> Hmm, "collecting" what is returned...
>
> (defun matrix-transpose (matrix)
> (let ((number-of-rows (length matrix))
> (number-of-columns (length (car matrix))))
> (loop for j from 0 to (1- number-of-columns)
> collecting (loop for i from 0 to (1- number-of-rows)
> collect (nth j (nth i matrix))))))
Right!
> Now it looks like it is working as expected. But I still
> feel my mind a little "twisted" :)
You haven't seen our metaobject protocol yet ;-)
> Now, on to performance evaluations...
The problem is that NTH isn't an O(1) operation. You could try
to write your own version of NTH. Then you'll probably see why
the performance of your code is far from optimal.
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <873blv9e0m.fsf@ileriseviye.org>
>>>>> "AL" == Arthur Lemmens <········@xs4all.nl> writes:
AL> Emre Sevinc <·····@bilgi.edu.tr> wrote: So your inner loop
AL> returns a list each time it's called. Now: how do you, ahem,
AL> collect those lists in the outer loop?
>> Hmm, "collecting" what is returned...
>> Now it looks like it is working as expected. But I still feel
>> my mind a little "twisted" :)
AL> You haven't seen our metaobject protocol yet ;-)
Well, actually I did :)
http://bc.tech.coop/blog/050919.html
I've read AMOP book as well as Paepcke's articles about it.
Of course that doesn't mean I have used MOP
and am not confused about it, too ;-)
>> Now, on to performance evaluations...
AL> The problem is that NTH isn't an O(1) operation. You could
AL> try to write your own version of NTH. Then you'll probably
AL> see why the performance of your code is far from optimal.
Aha! I'd never blame NTH guilty for it. Should I write my own
list accessor or use some other data structure such as vector
and use vectors to build matrices? I must check it out. Thanks
for drawing my attention to NTH.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
>>>>>> "AL" == Arthur Lemmens <········@xs4all.nl> writes:
> >> Now, on to performance evaluations...
>
> AL> The problem is that NTH isn't an O(1) operation. You could
> AL> try to write your own version of NTH. Then you'll probably
> AL> see why the performance of your code is far from optimal.
>
> Aha! I'd never blame NTH guilty for it. Should I write my own
> list accessor or use some other data structure such as vector
> and use vectors to build matrices? I must check it out. Thanks
> for drawing my attention to NTH.
>
As also noted in my previous post, nth is the problem. On above note though,
what drove you to using lists-of-lists for matrices, since lists lack O(1)
access? Did it occur to you to use 2-d arrays?
-s
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87psoz7y6z.fsf@ileriseviye.org>
>>>>> "SA" == Simon Alexander <··@spam.net> writes:
SA> Emre Sevinc <·····@bilgi.edu.tr> writes:
>>>>>>> "AL" == Arthur Lemmens <········@xs4all.nl> writes:
>> >> Now, on to performance evaluations...
>>
AL> The problem is that NTH isn't an O(1) operation. You could
AL> try to write your own version of NTH. Then you'll probably
AL> see why the performance of your code is far from optimal.
>> Aha! I'd never blame NTH guilty for it. Should I write my own
>> list accessor or use some other data structure such as vector
>> and use vectors to build matrices? I must check it out. Thanks
>> for drawing my attention to NTH.
>>
SA> As also noted in my previous post, nth is the problem. On
SA> above note though, what drove you to using lists-of-lists for
SA> matrices, since lists lack O(1) access? Did it occur to you
SA> to use 2-d arrays?
Nothing drove me there. I mean I was not in the process of creating
some matrix manipulation lib. but just reading Norvig and concentrated
on that apply mapcar list pattern.
When I was warned about NTH's complexity I thought about vectors, arrays,
etc. (if I were to start writing some matrix manipulation function).
BTW, given the timing you've provided in your previous post, does
your implementation use vectors or arrays for representing matrices?
Is that the reason you had much faster results?
Happy hacking,
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
>>>>>> "SA" == Simon Alexander <··@spam.net> writes:
> Nothing drove me there. I mean I was not in the process of creating
> some matrix manipulation lib. but just reading Norvig and concentrated
> on that apply mapcar list pattern.
>
> When I was warned about NTH's complexity I thought about vectors, arrays,
> etc. (if I were to start writing some matrix manipulation function).
>
> BTW, given the timing you've provided in your previous post, does
> your implementation use vectors or arrays for representing matrices?
> Is that the reason you had much faster results?
>
No, not at all. In general, using list-of-lists for a matrix is problematic,
because there is no O(1) access (consider how you would get at the i,jth
element). However, in some operations this doesn't matter. All I did was
arrange to only walk over the lists once: in other words when I reach an element
in the matrix, I put it in the right place in the transpose and then forget
about it.
My actual implementation was the following:
(defun matrix-transpose (matrix)
(loop with rows = (loop for x in (car matrix)
for q = (cons nil nil)
collecting (setf (car q) q))
for col in matrix
do (loop for element in col
for row in rows
do (setf (car row) (setf (rest (car row)) (cons element nil))))
finally (return (mapcar #'cdr rows))))
which is perhaps a little cryptic due to the use of dequeues' for the rows.
This was only done to build the rows in place. This is again an issue of the
list data structure, as push must add to the beginning of the lists. Without
changing the over all complexity, I could have just
had a final pass to reverse the rows. I find "do" forms easier to follow for
this sort of list munging, so something like this would also work
(defun matrix-transpose (matrix)
(let ((rows (loop for x in (car matrix) collecting `(,x))))
(dolist (col (cdr matrix) rows)
(do ((element col (cdr element))
(row rows (cdr row)))
((null element))
(push (car element) (car row))))
;;;at this point it the rows are all in reverse order, because of push!
(do ((row rows (cdr row)))
((null row) rows)
(setf (car row) (nreverse (car row))))))
warning, above isn't tested.
In general, of course, we can't avoid the access problems with a list based data
structure.
A straighforward array-based one would look something like
(defun matrix-transpose-array (matrix)
(loop with res = (make-array (reverse (array-dimensions matrix)))
for i below (array-dimension matrix 0)
do (loop for j below (array-dimension matrix 1)
do (setf (aref res j i) (aref matrix i j)))
finally (return res)))
so, for example:
(defparameter mat1 (make-array `(1000 1000) :element-type 'double-float :initial-element 0.0d0))
CL-USER> (time (matrix-transpose-array mat1))
Evaluation took:
0.36 seconds of real time
0.279957 seconds of user run time
0.076988 seconds of system run time
0 page faults and
20,013,376 bytes consed.
#<(SIMPLE-ARRAY T (1000 1000)) {B7FF73F}>
Of course this can be made a lot quicker for particular specialized matrices
(and lisp implementations). The code gets uglier, but quite a bit quicker:
(deftype index () `(integer 0 #.(1- #.array-total-size-limit)))
(defun matrix-transpose-array (matrix)
(declare (type (simple-array double-float (* *)) matrix)
(optimize speed))
(loop with res of-type (simple-array double-float (* *))
= (make-array (reverse (array-dimensions matrix)) :element-type 'double-float)
for i of-type index below (array-dimension matrix 0)
do (loop for j of-type index below (array-dimension matrix 1)
do (setf (aref res j i) (aref matrix i j)))
finally (return res)))
CL-USER> (time (matrix-transpose-array mat1))
Evaluation took:
0.033 seconds of real time
0.022997 seconds of user run time
0.009999 seconds of system run time
0 page faults and
8,000,008 bytes consed.
#<(SIMPLE-ARRAY DOUBLE-FLOAT (1000 1000)) {B3DBAF7}>
Simon Alexander wrote:
> My actual implementation was the following:
>
> (defun matrix-transpose (matrix)
> (loop with rows = (loop for x in (car matrix)
> for q = (cons nil nil)
> collecting (setf (car q) q))
> for col in matrix
> do (loop for element in col
> for row in rows
> do (setf (car row) (setf (rest (car row)) (cons element nil))))
> finally (return (mapcar #'cdr rows))))
>
> which is perhaps a little cryptic due to the use of dequeues' for the rows.
> This was only done to build the rows in place. This is again an issue of the
> list data structure, as push must add to the beginning of the lists. Without
> changing the over all complexity, I could have just
> had a final pass to reverse the rows. I find "do" forms easier to follow for
> this sort of list munging, so something like this would also work
>
> (defun matrix-transpose (matrix)
> (let ((rows (loop for x in (car matrix) collecting `(,x))))
> (dolist (col (cdr matrix) rows)
> (do ((element col (cdr element))
> (row rows (cdr row)))
> ((null element))
> (push (car element) (car row))))
> ;;;at this point it the rows are all in reverse order, because of push!
> (do ((row rows (cdr row)))
> ((null row) rows)
> (setf (car row) (nreverse (car row))))))
>
> warning, above isn't tested.
Hmm, maybe something like this might be a bit easier to follow:
(defun matrix-transpose (matrix)
"Turn a matrix on its side."
(loop with matrix-copy = matrix
while (first matrix-copy)
collect (loop for row in matrix-copy
collect (first row) into firsts
collect (rest row) into rests
finally (setf matrix-copy rests)
finally (return firsts))))
Tayssir
--
"All human beings, whatever their position in society, are suffering
from this process of deterioration. Unknowingly prisoners of their own
egotism, they feel insecure, lonely, and deprived of the naive, simple,
and unsophisticated enjoyment of life."
-- Albert Einstein, 1949
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Nothing drove me there. I mean I was not in the process of creating
> some matrix manipulation lib. but just reading Norvig and concentrated
> on that apply mapcar list pattern.
>
> When I was warned about NTH's complexity I thought about vectors, arrays,
> etc. (if I were to start writing some matrix manipulation function).
>
> BTW, given the timing you've provided in your previous post, does
> your implementation use vectors or arrays for representing matrices?
> Is that the reason you had much faster results?
There are a lot of matrix representations, and choosing the best
really depends on the type of matrix and the type of operations you
want to do.
For small matrices (like 3x3), it doesn't matter much if you use list
of lists or if you use arrays.
Going thru one or two pointers, or multiplying an index would be about as fast.
The list of list will need in general twice as much memory as the 2D array.
If you have bigger matrices, then 2D arrays will be faster and will
spare more memory.
But then if you have big matrices, you often have empty matrices
(matrices with a lot of zeros). Then it can be worthwhile to revert
to a list based representation, where you keep in lists only the
elements that are present (may be ranges, may be cells with their
coordinates for really sparse matrices).
--
__Pascal Bourguignon__ http://www.informatimago.com/
The rule for today:
Touch my tail, I shred your hand.
New rule tomorrow.
From: Arthur Lemmens
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <op.s0enj7g8wpmq96@news.xs4all.nl>
Emre Sevinc <·····@bilgi.edu.tr> wrote:
> AL> The problem is that NTH isn't an O(1) operation. You could
> AL> try to write your own version of NTH. Then you'll probably
> AL> see why the performance of your code is far from optimal.
>
> Aha! I'd never blame NTH guilty for it. Should I write my own
> list accessor
Writing your own list accessor (as a separate function) wouldn't help.
The problem with the current code is that the (NTH I (NTH J MATRIX))
part needs to walk through the matrix again and again, each time starting
from 0.
A better implementation (assuming you use lists to represent matrices)
would try to keep track of the relevant part of the matrix while looping.
Basically it would 'cache' the result of at least one of the NTH operations.
> or use some other data structure such as vector and use vectors to
> build matrices?
That depends on the kind of matrix and the kind of computations you want
to do with them. But yes, unless you're doing specialized matrix
computations a 2-dimensional array feels like a more natural representation
for matrices.
"Arthur Lemmens" <········@xs4all.nl> writes:
> Bulent Murtezaoglu <··@acm.org> wrote:
>
>>>>>>> "ES" == Emre Sevinc <·····@bilgi.edu.tr> writes:
>>
>> ES> As I'm going through Norvig's PAIP, in Ch. 17 (where he
>> ES> describes "A Line-Labeling program using the Waltz algorithm")
>> ES> I came across a matrix-transpose function:
>
> [snip]
>
>> Anyway, folks, in addition to what the others explained I also pointed out
>> that this is _not_ guaranteed to work and might unnecessarily bump into
>> the call-arguments-limit. With all due respect to Norvig, I don't
>> consider this code elegant. Any more opinions?
>
> I agree. So a nice exercise for Emre would be to write a version that
> works regardless of call-arguments-limit. I suppose it wouldn't be a
> one-liner anymore ;-)
FSVO one-liner:
(let ((matrix '((1 2 3 4) (5 6 7 8) (9 a b c) (d e f g))))
(reduce (lambda (m c) (mapcar (lambda (l e) (append l (list e))) m c)) matrix :initial-value (make-list (length matrix) :initial-element '())))
((1 5 9 D) (2 6 A E) (3 7 B F) (4 8 C G))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87ek5f9ify.fsf@ileriseviye.org>
>>>>> "PB" == Pascal Bourguignon <····@mouse-potato.com> writes:
PB> "Arthur Lemmens" <········@xs4all.nl> writes:
>> Bulent Murtezaoglu <··@acm.org> wrote:
>>>>>>>> "ES" == Emre Sevinc <·····@bilgi.edu.tr> writes:
>>>
ES> As I'm going through Norvig's PAIP, in Ch. 17 (where he
ES> describes "A Line-Labeling program using the Waltz algorithm")
ES> I came across a matrix-transpose function:
>>> Anyway, folks, in addition to what the others explained I also
>>> pointed out that this is _not_ guaranteed to work and might
>>> unnecessarily bump into the call-arguments-limit. With all
>>> due respect to Norvig, I don't consider this code elegant.
>>> Any more opinions?
>> I agree. So a nice exercise for Emre would be to write a
>> version that works regardless of call-arguments-limit. I
>> suppose it wouldn't be a one-liner anymore ;-)
PB> FSVO one-liner:
PB> (let ((matrix '((1 2 3 4) (5 6 7 8) (9 a b c) (d e f g))))
PB> (reduce (lambda (m c) (mapcar (lambda (l e) (append l (list
PB> e))) m c)) matrix :initial-value (make-list (length matrix)
PB> :initial-element '()))) ((1 5 9 D) (2 6 A E) (3 7 B F) (4 8 C
PB> G))
And they say Norvig's code was a little bit confusing, huh? :)
(I'm going to implant a Lisp parser into my brain ;-))
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc <·····@bilgi.edu.tr> writes:
> And they say Norvig's code was a little bit confusing, huh? :)
> (I'm going to implant a Lisp parser into my brain ;-))
You can indent it correctly to better understand it:
(reduce (lambda (m c) (mapcar (lambda (l e) (append l (list e))) m c))
matrix
:initial-value (make-list (length matrix) :initial-element '()))
The initial value is merely a list of nil of same length as the matrix
Actually, if the matrix is not square, it should be (length (first matrix)).
[31]> (make-list (length matrix) :initial-element '())
(NIL NIL NIL NIL)
REDUCE calls (lambda (m c) ...) with c bound to each element of the
matrix list in turn, and with m bound first to the initial-value, and
then to the previous result of (lambda (m c) ...)
Adding some PRINTs may help to understand how it works:
[34]> (reduce (lambda (m c) (terpri)
(print `(m = ,m))
(print `(c = ,c))
(mapcar (lambda (l e) (print `(l = ,l))
(print `(e = ,e))
(append l (list e))) m c))
matrix
:initial-value (make-list (length matrix) :initial-element '()))
(M = (NIL NIL NIL NIL))
(C = (1 2 3 4))
(L = NIL)
(E = 1)
(L = NIL)
(E = 2)
(L = NIL)
(E = 3)
(L = NIL)
(E = 4)
(M = ((1) (2) (3) (4)))
(C = (5 6 7 8))
(L = (1))
(E = 5)
(L = (2))
(E = 6)
(L = (3))
(E = 7)
(L = (4))
(E = 8)
(M = ((1 5) (2 6) (3 7) (4 8)))
(C = (9 A B C))
(L = (1 5))
(E = 9)
(L = (2 6))
(E = A)
(L = (3 7))
(E = B)
(L = (4 8))
(E = C)
(M = ((1 5 9) (2 6 A) (3 7 B) (4 8 C)))
(C = (D E F G))
(L = (1 5 9))
(E = D)
(L = (2 6 A))
(E = E)
(L = (3 7 B))
(E = F)
(L = (4 8 C))
(E = G)
((1 5 9 D) (2 6 A E) (3 7 B F) (4 8 C G))
[35]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
I need a new toy.
Tail of black dog keeps good time.
Pounce! Good dog! Good dog!
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87y83n7yu2.fsf@ileriseviye.org>
>>>>> "PB" == Pascal Bourguignon <····@mouse-potato.com> writes:
PB> Emre Sevinc <·····@bilgi.edu.tr> writes:
>> And they say Norvig's code was a little bit confusing, huh? :)
>> (I'm going to implant a Lisp parser into my brain ;-))
PB> You can indent it correctly to better understand it:
PB> (reduce (lambda (m c) (mapcar (lambda (l e) (append l (list
PB> e))) m c)) matrix :initial-value (make-list (length matrix)
PB> :initial-element '()))
PB> The initial value is merely a list of nil of same length as
PB> the matrix Actually, if the matrix is not square, it should be
PB> (length (first matrix)).
PB> [31]> (make-list (length matrix) :initial-element '()) (NIL
PB> NIL NIL NIL)
PB> REDUCE calls (lambda (m c) ...) with c bound to each element
PB> of the matrix list in turn, and with m bound first to the
PB> initial-value, and then to the previous result of (lambda (m
PB> c) ...)
PB> Adding some PRINTs may help to understand how it works:
Thank you very much for detailed explanations.
By the way I also timed this "reduce"ing with that m2 which
is a 500x500 matrix:
CL-USER> (time (reduce (lambda (m c)
(mapcar (lambda (l e) (append l (list e))) m c))
m2 :initial-value (make-list (length m2) :initial-element '())))
Evaluation took:
4.452 seconds of real time
3.2915 seconds of user run time
1.002848 seconds of system run time
7 page faults and
507,007,168 bytes consed.
The interesting part for me was the page faults. I don't know
why they happen. Because of huge number of cons'ing?
On the other hand, seeing this and reading previous posts
it really feels like lists are not for this job but it is
good to be able to look at it from many different perspectives.
Actually all this stuff begin by my curiosity about what exactly
Norvig code meant but I came to the point that unless I go along
with very very small matrices I must stay away from lists.
Another lesson that shows me the interactive and incremental
style of development in Common Lisp such as starting with lists
as general purpose data structure and then after having a working
function, thinking about changing the structure for having
better performance but only after having understood the basics
of algorithm and knowing what's going on behind.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Edi Weitz
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <ud5ky545n.fsf@agharta.de>
On Thu, 17 Nov 2005 15:35:23 +0200, Bulent Murtezaoglu <··@acm.org> wrote:
> Anyway, folks, in addition to what the others explained I also
> pointed out that this is _not_ guaranteed to work and might
> unnecessarily bump into the call-arguments-limit. With all due
> respect to Norvig, I don't consider this code elegant. Any more
> opinions?
I'm coming in a bit late here but I just wanted to mention that SLIME
originally used Norvig's function and now uses this nice code from
Helmut Eller
(defun transpose-lists (lists)
(cond ((null lists) '())
((some #'null lists) '())
(t (cons (mapcar #'car lists)
(transpose-lists (mapcar #'cdr lists))))))
exactly for the reasons your mention.
See also my own premature optimization here:
<http://common-lisp.net/pipermail/slime-devel/2005-August/003840.html>
It's a lot uglier but slightly faster for large input... :)
My apologies if this was already posted further down in the thread -
I'm too tired to read all the postings I missed this week at once.
Cheers,
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
From: Stefan Nobis
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <873blvpble.fsf@snobis.de>
Emre Sevinc <·····@bilgi.edu.tr> writes:
> (defun matrix-transpose (matrix)
> "Turn a matrix on its side."
> (if matrix (apply #'mapcar #'list matrix)))
> Why? Because, when I look at CLHS and think like that:
> (apply #'+ '(1 2 3)) ----> (+ 1 2 3)
The point here is the transformation '(1 2 3) --> 1 2 3
So if matrix is a list of lists, this line
> (apply #'mapcar #'list matrix)
means not the same as this
> (mapcar #'list m1)
because m1 is still a list of lists. Look at this:
CL-USER> (mapcar #'list '(1 2) '(3 4))
((1 3) (2 4))
apply helps in decomposing the list of lists.
--
Stefan.
Emre Sevinc wrote:
> As I'm going through Norvig's PAIP, in Ch. 17 (where he
> describes "A Line-Labeling program using the Waltz algorithm")
> I came across a matrix-transpose function:
>
> (defun matrix-transpose (matrix)
> "Turn a matrix on its side."
> (if matrix (apply #'mapcar #'list matrix)))
>
> and it works fine:
I do not think so.
The LISP-using version of PAIP (1st Ed.) was published in 1991. At
that time, CLtL2 (1990) was the definitive reference on Common
Lisp. This says (as far as I understand it) that the maximum number of
arguments that mapcar can take here is given by CALL-ARGUMENTS-LIMIT,
which need not be larger than 50. For CLISP, this indeed is 4096 right
now. So, if we use this in such a situation:
(let* ((row (coerce (make-array 10) 'list))
(matrix (coerce (make-array 4000 :initial-element row) 'list)))
(apply #'mapcar #'list matrix))
everything will be fine with CLISP, but if you substitute 4000 by 5000,
this will go boom.
Admittedly, it's tricky, and certainly especially attractive for someone
with such a high affinity for superbrief constructions as Peter Norvig
(I'd say he's an early Perl Golfer who does not use Perl), but I
strongly recommend not using such unsafe constructions in potentially
important code - maybe even better not at all.
--
Thomas Fischbacher
"Dr. Thomas Fischbacher"
<··@spamtrap-delete-this.cip.physik.uni-muenchen.de> writes:
> The LISP-using version of PAIP (1st Ed.) was published in 1991. At that
> time, CLtL2 (1990) was the definitive reference on Common Lisp. This says
> (as far as I understand it) that the maximum number of arguments that
> mapcar can take here is given by CALL-ARGUMENTS-LIMIT, which need not be
> larger than 50. For CLISP, this indeed is 4096 right now. So, if we use
> this in such a situation:
>
> (let* ((row (coerce (make-array 10) 'list))
> (matrix (coerce (make-array 4000 :initial-element row) 'list)))
> (apply #'mapcar #'list matrix))
>
> everything will be fine with CLISP, but if you substitute 4000 by 5000,
> this will go boom.
>
> Admittedly, it's tricky, and certainly especially attractive for someone
> with such a high affinity for superbrief constructions as Peter Norvig
> (I'd say he's an early Perl Golfer who does not use Perl), but I strongly
> recommend not using such unsafe constructions in potentially important
> code - maybe even better not at all.
Hmm. I see it differently and think that this kind of coding is perfectly
OK for small matrices. If one needs to handle large matrices, other data
structures are to be preferred anyhow because of performance reasons.
Generally, I don't like this raising of CALL-ARGUMENTS-LIMIT against using
APPLY. _If_ this issue was really standing in my way (i.e. I really want
it and there is no way around it by using an even more appropriate operator
like REDUCE), I would ask the implementors if this limit could not be
increased. If this query would not succed, I would look for another
implementation.
Nicolas.
Nicolas Neuss wrote:
>>(I'd say he's an early Perl Golfer who does not use Perl), but I strongly
>>recommend not using such unsafe constructions in potentially important
>>code - maybe even better not at all.
>
>
> Hmm. I see it differently and think that this kind of coding is perfectly
> OK for small matrices. If one needs to handle large matrices, other data
> structures are to be preferred anyhow because of performance reasons.
One problem is that you want to be able to do proper stringent reasoning
over the behaviour of code. This gets insanely difficult with a larger
code base if there are all kinds of hidden gotchas and limitations
floating around, and I would even go so far that this kind of
dont-care-about-unusual-cases sloppiness is just the reason for the
majority of Microsoft's security woes.
Anyway, I think such style is perfectly okay for interactively written
one-shot throwaway code, but one for sure should not lure people who
still are learning into such dark alleys by putting this into a textbook.
> Generally, I don't like this raising of CALL-ARGUMENTS-LIMIT against using
> APPLY.
Well, that's the CL standard, unfortunately. I agree with you that
points like this do not make much sense philosophy-wise: LISP is rather
do-the-right-thing than worse-is-better, and CALL-ARGUMENTS-LIMIT
clearly is along the worse-is-better line of reasoning.
Anyway: the concept of having variable-argument functions with an
insanely large number of arguments is kind of exotic - as far as I know,
there is no other system - programming language or not - where this is
supported really well, and considered reasonably good style (except
maybe perl4 - look, even the shell might have problems executing a
simple "ls *" in a directory with lots of entries). So, if there is no
noticeable real benefit from this, and programmers usually do not think
in such ways, why use such a style?
> _If_ this issue was really standing in my way (i.e. I really want
> it and there is no way around it by using an even more appropriate operator
> like REDUCE), I would ask the implementors if this limit could not be
> increased. If this query would not succed, I would look for another
> implementation.
There may be other, and far better, reasons to stick with the particular
system you'd chosen.
Actually, if this were otherwise, very few people would use, say,
Objective Caml. On 32-bit systems, strings are limited to 16M entries,
and this limit comes from some quite deep design decisions that just
cannot be changed short of re-implementing the whole compiler (and in
particular GC) in a considerably less efficient way. For arrays, it's
even worse there: world ends at 4M entries:
# let a = Array.make 4000000 0 in Array.length a;;
- : int = 4000000
# let a = Array.make 5000000 0 in Array.length a;;
Exception: Invalid_argument "Array.make".
#
--
Dr. Thomas Fischbacher
From: Lars Brinkhoff
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <854q6as38u.fsf@junk.nocrew.org>
Lars Brinkhoff wrote:
>>(let* ((row (coerce (make-array 10) 'list))
>> (matrix (coerce (make-array 4000 :initial-element row) 'list)))
>
>
> Suggest make-list.
Thanks. Curiously, I really did not know about it, as I never was in a
situation where I could have made good use of that one before. (Yes,
that's a poor excuse for not looking it up when one should expect it to
exist.)
Anyway, I still have difficulties coming up with a real world example
(short of demonstrating that a certain list-based approach is not a good
idea) where this would be useful. Suggestions, anyone?
--
Dr. Thomas Fischbacher
Dr. Thomas Fischbacher wrote:
> Emre Sevinc wrote:
>
> > As I'm going through Norvig's PAIP, in Ch. 17 (where he
> > describes "A Line-Labeling program using the Waltz algorithm")
> > I came across a matrix-transpose function:
> >
> > (defun matrix-transpose (matrix)
> > "Turn a matrix on its side."
> > (if matrix (apply #'mapcar #'list matrix)))
> >
> > and it works fine:
>
> I do not think so.
>
> The LISP-using version of PAIP (1st Ed.) was published in 1991. At
> that time, CLtL2 (1990) was the definitive reference on Common
> Lisp. This says (as far as I understand it) that the maximum number of
> arguments that mapcar can take here is given by CALL-ARGUMENTS-LIMIT,
> which need not be larger than 50. For CLISP, this indeed is 4096 right
> now. So, if we use this in such a situation:
>
> (let* ((row (coerce (make-array 10) 'list))
> (matrix (coerce (make-array 4000 :initial-element row) 'list)))
> (apply #'mapcar #'list matrix))
>
> everything will be fine with CLISP, but if you substitute 4000 by 5000,
> this will go boom.
>
> Admittedly, it's tricky, and certainly especially attractive for someone
> with such a high affinity for superbrief constructions as Peter Norvig
> (I'd say he's an early Perl Golfer who does not use Perl), but I
> strongly recommend not using such unsafe constructions in potentially
> important code - maybe even better not at all.
I will say that it's a crappy docstring: "Turn a matrix on its side."
After I coded the LOOP version earlier in the thread, I came back to it
later, very sleepy, and thought, "Hey, this doesn't turn a matrix onto
its side!" and posted a modification -- but the original version was
more correct.
That is, the original did transpose a matrix, but didn't "turn it onto
its side," in some geometrical 90 degree rotation that my sleepy head
wondered about.
Tayssir
From: Thomas A. Russ
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <ymioe4hpnk4.fsf@sevak.isi.edu>
"Dr. Thomas Fischbacher" <··@spamtrap-delete-this.cip.physik.uni-muenchen.de> writes:
> (let* ((row (coerce (make-array 10) 'list))
> (matrix (coerce (make-array 4000 :initial-element row) 'list)))
> (apply #'mapcar #'list matrix))
Minor nit:
Instead of (coerce (make-array 10) 'list)
one could directly use (make-list 10)
MAKE-LIST also accepts the :initial-element keyword.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Emre Sevinc
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <87oe4g6s7c.fsf@ileriseviye.org>
>>>>> "ES" == Emre Sevinc <·····@bilgi.edu.tr> writes:
ES> As I'm going through Norvig's PAIP, in Ch. 17 (where he
ES> describes "A Line-Labeling program using the Waltz algorithm")
ES> I came across a matrix-transpose function:
ES> (defun matrix-transpose (matrix) "Turn a matrix on its side."
ES> (if matrix (apply #'mapcar #'list matrix)))
ES> and it works fine:
ES> (defparameter m1 '((1 0 0 0) (1 0 0 0) (1 0 0 0)))
CL-USER> (matrix-transpose m1)
ES> ((1 1 1) (0 0 0) (0 0 0) (0 0 0))
After the arguments about CALL-ARGUMENTS-LIMIT I checked
my SBCL:
CL-USER> (documentation 'call-arguments-limit 'variable)
"The exclusive upper bound on the number of arguments which may be passed
to a function, including &REST args."
CL-USER> call-arguments-limit
536870911
CL-USER> (format nil "~r" call-arguments-limit)
"five hundred thirty-six million eight hundred seventy thousand nine hundred eleven"
CL-USER>
At least, theoretically, SBCL seems to handle matrices containing more than
a few thousand elements (using Norvig's code), right?
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Brian Downing
Subject: Re: Norvig's use of APPPLY for MATRIX-TRANSPOSE puzzled me!
Date:
Message-ID: <ITRff.344995$084.34427@attbi_s22>
In article <··············@ileriseviye.org>,
Emre Sevinc <·····@bilgi.edu.tr> wrote:
> After the arguments about CALL-ARGUMENTS-LIMIT I checked
> my SBCL:
>
> CL-USER> call-arguments-limit
> 536870911
>
> At least, theoretically, SBCL seems to handle matrices containing more than
> a few thousand elements (using Norvig's code), right?
Since implementations are allowed to let a &REST argument share
structure with the last argument to APPLY
(http://www.lisp.org/HyperSpec/Body/sec_3-4-1-3.html), it's possible
that for some theoretical implementation CALL-ARGUMENTS-LIMIT might not
come into play at all for this example.
I.E., it could evaluate something like this:
(defun %list (lists)
lists)
(defun %mapcar (function lists)
(loop for cur = lists then (mapcar #'cdr cur)
while (every #'identity cur)
collect (funcall function (mapcar #'car cur))))
(defun transpose (lists)
(%mapcar #'%list lists))
Even with the calls to CL:MAPCAR there are no function calls with
unbounded numbers of arguments, no matter the lists passed to TRANSPOSE.
Of course, you can't count on this of course...
-bcd
--
*** Brian Downing <bdowning at lavos dot net>