transpose of a matrix
in [Lisp]
|
Prev: Algebra Rizing
Next: GNU Emacs and Xemacs Schism
From: Thomas M. Hermann on 29 Jun 2010 11:42 On Jun 29, 9:30 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > You are talking of matrices, not of list of lists, therefore I will > boldly ignore the code you've pasted and show you how to transpose a > matrix in O(1): I, too, will boldly ignore the original code and paste something that may or may not be apropos. I needed something to do while I was waiting on my utility company to verify my email address. (defun transpose-matrix (matrix) "Transpose the matrix represented by a 2D array." (if (= 2 (array-rank matrix)) (destructuring-bind (numrows numcols) (array-dimensions matrix) (let ((new-matrix (make-array (list numcols numrows) :element-type (array-element-type matrix)))) (dotimes (i0 numrows new-matrix) (dotimes (i1 numcols) (setf (aref new-matrix i1 i0) (aref matrix i0 i1)))))) (error "The matrix is not a 2D array."))) Hope that helps or at least confuses, ~ Tom
From: pero on 29 Jun 2010 16:05 On 29 jun, 17:42, "Thomas M. Hermann" <tmh.pub...(a)gmail.com> wrote: > On Jun 29, 9:30 am, p...(a)informatimago.com (Pascal J. Bourguignon) > wrote: > > > You are talking of matrices, not of list of lists, therefore I will > > boldly ignore the code you've pasted and show you how to transpose a > > matrix in O(1): > > I, too, will boldly ignore the original code and paste something that > may or may not be apropos. I needed something to do while I was > waiting on my utility company to verify my email address. > > (defun transpose-matrix (matrix) > "Transpose the matrix represented by a 2D array." > (if (= 2 (array-rank matrix)) > (destructuring-bind (numrows numcols) > (array-dimensions matrix) > (let ((new-matrix (make-array (list numcols numrows) > :element-type > (array-element-type matrix)))) > (dotimes (i0 numrows new-matrix) > (dotimes (i1 numcols) > (setf (aref new-matrix i1 i0) (aref matrix i0 i1)))))) > (error "The matrix is not a 2D array."))) > > Hope that helps or at least confuses, > > ~ Tom You boldly lose: 0.050 > 0.028, better continue waiting for email. CL-USER> (progn (setq m1 (make-array (list 1000 1000))) nil) NIL CL-USER> (progn (time (transpose-matrix m1)) nil) Evaluation took: 0.050 seconds of real time 0.050000 seconds of total run time (0.050000 user, 0.000000 system) 100.00% CPU 117,341,497 processor cycles 8,000,016 bytes consed NIL
From: Raffael Cavallaro on 29 Jun 2010 16:33 On 2010-06-29 16:05:47 -0400, pero said: > You boldly lose: 0.050 > 0.028, better continue waiting for email. You've boldly missed the point of the previous posts entirely. Common Lisp has an array data type. Anyone interested in speed, especially with larger matrices, is going to use arrays, not lists for matrix code since array element access is O(1) and list element access is O(n). Their code operates on this array data type; yours does not. In addition, as Rainer pointed out, your code uses special variable names as locals! Faulty code is still faulty, even if fast on toy examples. Specifically, your array representation (i.e., a list) will show poor performance for anything that requires random access (as opposed to merely sequential access) of array elements: ? (let* ((list-matrix (loop for i below 10000 collect i))) (time (loop repeat 10000 for index = (random 10000) always (= (nth index list-matrix) index)))) (LOOP REPEAT 10000 FOR INDEX = (RANDOM 10000) ALWAYS (= (NTH INDEX LIST-MATRIX) INDEX)) took 301 milliseconds (0.301 seconds) to run with 2 available CPU cores. During that period, 304 milliseconds (0.304 seconds) were spent in user mode 0 milliseconds (0.000 seconds) were spent in system mode T ? (let* ((real-matrix (make-array 10000 :element-type 'fixnum))) (loop for i below 10000 do (setf (aref real-matrix i) i)) (time (loop repeat 10000 for index = (random 10000) always (= (aref real-matrix index) index)))) (LOOP REPEAT 10000 FOR INDEX = (RANDOM 10000) ALWAYS (= (AREF REAL-MATRIX INDEX) INDEX)) took 0 milliseconds (0.000 seconds) to run with 2 available CPU cores. During that period, 0 milliseconds (0.000 seconds) were spent in user mode 1 milliseconds (0.001 seconds) were spent in system mode T warmest regards, Ralph -- Raffael Cavallaro
From: pero on 29 Jun 2010 17:17 On 29 jun, 22:33, Raffael Cavallaro <raffaelcavall...(a)pas.despam.s.il.vous.plait.mac.com> wrote: > On 2010-06-29 16:05:47 -0400, pero said: > > > You boldly lose: 0.050 > 0.028, better continue waiting for email. > > You've boldly missed the point of the previous posts entirely. > > Common Lisp has an array data type. Anyone interested in speed, > especially with larger matrices, is going to use arrays, not lists for > matrix code since array element access is O(1) and list element access > is O(n). Their code operates on this array data type; yours does not. > In addition, as Rainer pointed out, your code uses special variable > names as locals! > > Faulty code is still faulty, even if fast on toy examples. > Specifically, your array representation (i.e., a list) will show poor > performance for anything that requires random access (as opposed to > merely sequential access) of array elements: > > ? (let* ((list-matrix (loop for i below 10000 collect i))) > (time (loop repeat 10000 > for index = (random 10000) > always (= (nth index list-matrix) index)))) > (LOOP REPEAT 10000 FOR INDEX = (RANDOM 10000) ALWAYS (= (NTH INDEX > LIST-MATRIX) INDEX)) took 301 milliseconds (0.301 seconds) to run > with 2 available CPU cores. > During that period, 304 milliseconds (0.304 seconds) were spent in user mode > 0 milliseconds (0.000 seconds) were spent in system mode > T > ? (let* ((real-matrix (make-array 10000 :element-type 'fixnum))) > (loop for i below 10000 do (setf (aref real-matrix i) i)) > (time (loop repeat 10000 > for index = (random 10000) > always (= (aref real-matrix index) index)))) > (LOOP REPEAT 10000 FOR INDEX = (RANDOM 10000) ALWAYS (= (AREF > REAL-MATRIX INDEX) INDEX)) took 0 milliseconds (0.000 seconds) to run > with 2 available CPU cores. > During that period, 0 milliseconds (0.000 seconds) were spent in user mode > 1 milliseconds (0.001 seconds) were spent in system mode > T > > warmest regards, > > Ralph > > -- > Raffael Cavallaro Well, now I ask: Can you find a way to calculate the transpose of a matrix (2d-array) that is faster than the algorithm I gave for calculating the transpose a list of lists that contains the same data? Do you really think that a person that can write this kind of code doesn't know the difference between a list and an array? really?
From: Raffael Cavallaro on 29 Jun 2010 19:38
On 2010-06-29 17:17:01 -0400, pero said: > Well, now I ask: Can you find a way to calculate the transpose of a > matrix (2d-array) that is faster than the algorithm I gave for > calculating the transpose a list of lists that contains the same data? A destructive matrix transpose which optimizes for array element type: (defun 2d-matrix-transpose! (matrix) (declare (type (array fixnum (* *)) matrix)) (let* ((dimensions (array-dimensions matrix)) (rows (first dimensions)) (cols (second dimensions))) (loop for i from 0 below rows do (loop for j from (1+ i) below cols do (rotatef (aref matrix j i) (aref matrix i j)))) matrix)) runs in the same time your tortured list of lists transpose does, while random access for your list of lists matrix is 2 orders of magnitude (100x) slower! If I'm using arrays for their intended O(1) random access, why would I possibly care how fast a list representation with its O(n) access can be transposed? > > Do you really think that a person that can write this kind of code > doesn't know the difference between a list and an array? really? I think that a person that would bother to write such code (i.e., representing large arrays as lists) might not have a good grasp of why people interested in performance don't use lists to represent arrays, yes. warmest regards, Ralph -- Raffael Cavallaro |