transpose of a matrix
in [Lisp]
|
Prev: Algebra Rizing
Next: GNU Emacs and Xemacs Schism
From: Raymond Toy on 29 Jun 2010 20:47 On 6/29/10 7:38 PM, Raffael Cavallaro wrote: > 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? Perhaps we should put this all back into perspective. The original question concerned maxima, which represents matrices as lists of lists. You may think this stupid, but consider that maxima is a SYMBOLIC math system, so large symbolic matrices quickly become unusable and the cost of matrix operations is probably swamped with the work needed to simplify the terms resulting from the matrix operation. Ray
From: Raffael Cavallaro on 29 Jun 2010 21:51 On 2010-06-29 20:47:55 -0400, Raymond Toy said: > Perhaps we should put this all back into perspective. The original > question concerned maxima, which represents matrices as lists of lists. > > You may think this stupid, No, I don't; I think crowing about the speed of a particular operation on such an otherwise sub-optimal representation is silly. > but consider that maxima is a SYMBOLIC math > system, so large symbolic matrices quickly become unusable and the cost > of matrix operations is probably swamped with the work needed to > simplify the terms resulting from the matrix operation. As you say, this representation was chosen in maxima for ease of symbolic manipulation, not for raw speed, so, optimizing matrix transpose is fairly pointless here. warmest regards, Ralph -- Raffael Cavallaro
From: pero on 30 Jun 2010 05:59 On 30 jun, 01:38, Raffael Cavallaro <raffaelcavall...(a)pas.despam.s.il.vous.plait.mac.com> wrote: > 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 Sorry Raffael, but you lose: 0.40 > 0.28, also your transpose-rc is only for array of fixnum, and this is a severe restriction. (defun transpose-rc (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 CL-USER> (defparameter l1 (make-array (list 1000 1000) :element-type 'fixnum :initial-element 0)) CL-USER> (progn (time (transpose-rc l1)) 'done) Evaluation took: 0.040 seconds of real time 0.040000 seconds of total run time (0.040000 user, 0.000000 system) 100.00% CPU 92,120,462 processor cycles 0 bytes consed DONE Well, I think my hidden motivation for this post was about football, as I am not a big fan of football but here is Spain there is a football fever. I think I have got an "Optimization Fever" (tm). Anyway, I am glad I have beaten every attempt done by Lispers to improve the time of this operation in sbcl.
From: Raymond Toy on 30 Jun 2010 09:31 On 6/29/10 9:51 PM, Raffael Cavallaro wrote: > On 2010-06-29 20:47:55 -0400, Raymond Toy said: > >> Perhaps we should put this all back into perspective. The original >> question concerned maxima, which represents matrices as lists of lists. >> >> You may think this stupid, > > No, I don't; I think crowing about the speed of a particular operation > on such an otherwise sub-optimal representation is silly. > >> but consider that maxima is a SYMBOLIC math >> system, so large symbolic matrices quickly become unusable and the cost >> of matrix operations is probably swamped with the work needed to >> simplify the terms resulting from the matrix operation. > > As you say, this representation was chosen in maxima for ease of > symbolic manipulation, not for raw speed, so, optimizing matrix > transpose is fairly pointless here. But aren't we all guilty of premature optimization sometimes? :-) Sometimes it's just fun to do. Ray
From: Raffael Cavallaro on 30 Jun 2010 18:44
On 2010-06-30 02:59:43 -0700, pero said: > Anyway, I am glad I have beaten every attempt done by Lispers to > improve the time of this operation in sbcl. Again, no one cares because you've microoptimized one operation on a matrix - transpose - at the expense of random access which is the primary reason arrays exist. To repeat, the random access for list of list matrices of the size you test is 2 orders of magnitude - 100 times slower! In the implementation I use, CCL, the in-place array transpose runs in the exact same time as your highly convoluted list of lists implementation. To summarize: * You've gained no speed advantage in transpose * Your code is much less clear * Your random access times, the whole reason arrays exist in the first place, are slower by 100 times The only thing you've triumphed over here is common sense. At least Spain actually beat Portugal. warmest regards, Ralph -- Raffael Cavallaro |