Subject: matrix transpose (was Re: mini / maxi functions)
From: Dieter Kaiser
Date: Sun, 27 Jun 2010 21:35:15 +0200
Am Sonntag, den 27.06.2010, 06:57 -0500 schrieb Barton Willis:
> For a n x n matrix, the running time for transpose is O(n^3). Here is a proposed O(n^2) replacement:
>
> ;; Transpose a list of lists ll and return a list of lists. Example:
> ;; ((1 2) (3 4)) --> ((1 3) (2 4)).
>
> (defun transpose (ll)
> (let ((acc nil))
> (while (car ll)
> (push (mapcar #'car ll) acc)
> (setq ll (mapcar #'cdr ll)))
> (nreverse acc)))
>
> To transpose the 800 x 800 matrix (i,j) --> i - j:
>
> current transpose: 26.21 seconds
> proposed transpose: 0.80 seconds.
>
> Matrix multiplication also uses transpose.
>
> Comments?
I have no further comment. If this routine is faster and works like the
original version I do not see any reason not to commit the new version.
Dieter Kaiser