transpose of a matrix
in [Lisp]
|
Prev: Algebra Rizing
Next: GNU Emacs and Xemacs Schism
From: pero on 29 Jun 2010 08:23 Hello, recently I saw this code on the maxima list for computing the transpose of a matrix, can you do it better (less computing time)? How this speed compares to C? B. Willis version: (defun transpose-wb (ll) (let ((acc nil)) (loop while (car ll) do (push (mapcar #'car ll) acc) (setq ll (mapcar #'cdr ll))) (nreverse acc))) --------------------------------------------------- My version. This version is destructive and avoid consing. (defvar l1 nil) (defvar l2 nil) (defun transpose-pg(m) (let (m1) (setq m1 (loop for x on (car m) collect x)) (transposeaux m) m1)) (defun transposeaux(ll) (let (next) (loop for l1 in ll for l2 in (cdr ll) do (loop for ai = l1 then next for bi on l2 do (setf next (cdr ai)) (rplacd ai bi)) finally (loop for bi = l2 then next while (cdr bi) do (setf next (cdr bi) (cdr bi) nil))) ll)) (defun a-matrix(i j) "construct a rectangular matrix" (loop repeat i collect (loop repeat j collect (random 20)))) (defun transpose-wb (ll) (let ((acc nil)) (loop while (car ll) do (push (mapcar #'car ll) acc) (setq ll (mapcar #'cdr ll))) (nreverse acc))) Now a benchmark: CL-USER> (progn (setq l2 (copy-tree (setq l1 (a-matrix 1000 1000)))) nil) NIL CL-USER> (time (progn (transpose-wb l1) 'done)) Evaluation took: 0.184 seconds of real time 0.190000 seconds of total run time (0.130000 user, 0.060000 system) [ Run times consist of 0.140 seconds GC time, and 0.050 seconds non- GC time. ] 103.26% CPU 431,324,341 processor cycles 32,046,400 bytes consed DONE CL-USER> (time (progn (transpose-pg l2) 'done)) Evaluation took: 0.028 seconds of real time 0.030000 seconds of total run time (0.020000 user, 0.010000 system) 107.14% CPU 67,007,521 processor cycles 16,384 bytes consed --------------------------
From: joswig on 29 Jun 2010 08:46 On 29 Jun., 14:23, pero <perogarridogo...(a)yahoo.es> wrote: a style remark: > (defvar l1 nil) > (defvar l2 nil) L1 and L2 are now defined to be SPECIAL (dynamic variables). .... > (defun transposeaux(ll) > (let (next) > (loop for l1 in ll > for l2 in (cdr ll) do Here L1 and L2 are local variables introduced by LOOP. Unfortunately both are also SPECIAL variables, because of the DEFVAR above. Because of that there is a convention to write SPECIAL variables as *l1* and *l2*. That way your local variables can be named l1 and l2 and will not be special. Often one may not see a difference. Sometimes it introduces hard to find bugs and it even may have performance implications in some cases...
From: Marc Mientki on 29 Jun 2010 09:10 Am 29.06.2010 14:23, schrieb pero: > Hello, recently I saw this code on the maxima list for computing the > transpose of a matrix, > can you do it better (less computing time)? How this speed compares > to C? > > B. Willis version: > > (defun transpose-wb (ll) > (let ((acc nil)) > (loop while (car ll) do > (push (mapcar #'car ll) acc) > (setq ll (mapcar #'cdr ll))) > (nreverse acc))) And how about this version? (defun transpose-m (matrix) (apply 'mapcar 'list matrix)) regards Marc
From: Norbert_Paul on 29 Jun 2010 09:22 pero wrote: > Hello, recently I saw this code on the maxima list for computing the > transpose of a matrix, > can you do it better (less computing time)? How this speed compares > to C? > > B. Willis version: > > (defun transpose-wb (ll) > (let ((acc nil)) > (loop while (car ll) do > (push (mapcar #'car ll) acc) > (setq ll (mapcar #'cdr ll))) > (nreverse acc))) I'd avoid (mapcar #'cdr ll) and use map-into: Something like: .... (let ((acc nil) (ll (copy-list ll))) ; conses only once .... (setf ll (map-into ll #'cdr ll)) ; re-use conses. .... gc now recycles only n conses, not (roughly) n^2 (not tested) Norbert
From: Pascal J. Bourguignon on 29 Jun 2010 10:30
pero <perogarridogomez(a)yahoo.es> writes: > Hello, recently I saw this code on the maxima list for computing the > transpose of a matrix, > can you do it better (less computing time)? How this speed compares > to C? 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): (defun transpose-matrix (matrix) (lambda (i j &rest args) (apply matrix j i args))) ;; That is, with the right representation. (defun make-matrix (r c) (let ((storage (make-array (list r c)))) (lambda (i j &optional (new-value nil setp)) (if setp (setf (aref storage i j) new-value) (aref storage i j))))) (let ((m (make-matrix 2 2))) (funcall m 0 0 3) (funcall m 0 1 2) (funcall m 1 0 -2) (funcall m 1 1 3) (flet ((print-matrix (m) (loop for i from 0 to 1 do (terpri) (loop for j from 0 to 1 do (prin1 (funcall m i j)) (princ " "))) (terpri))) (print-matrix m) (print-matrix (transpose-matrix m)))) 3 2 -2 3 3 -2 2 3 -- __Pascal Bourguignon__ http://www.informatimago.com/ |