Rosetta Code

Matrix transposition: Difference between revisions

Page Discussion

Matrix transposition (view source)

Revision as of 22:13, 29 August 2011

1,008 bytes removed ,  12 years ago
→‎{{header|C}}
m (→‎{{header|Ruby}}: Remove phantom category 'matrix.rb'.)
Line 230:
return 0;
}</lang>
 
{{improve|C|Unnecessarily complicated, probably lost all benefit from the algorithm. Can use cleaner coding (and malloc(item_size) does not violate O(1))}}
Transpose a matrix of size w x h in place with only O(1) space and without moving any element more than once. See the [[wp:In-place_matrix_transposition|Wikipedia article]] for more information.▼
Playing more to C's strengths, the following implementation transposes a matrix of any type and dimensions
<lang c>#include <stdio.h>
▲in place with only O(1) space. See the [[wp:In-place_matrix_transposition|Wikipedia article]] for more information.
 
<lang c>void *transpose_matrix(void *matrix, int rows, int cols, size_t item_size)
void transpose(double *m, int w, int h)
{
int start, next, i;
#define ALIGNMENT 16 /* power of 2 >= minimum array boundary alignment; maybe unnecessary but machine dependent */
double tmp;
 
for (start = 1; start < w * h - 2; start++) {
next = start;
do { next = (next % h) * w + next / h; } while (next > start);
if (next < start) continue;
 
tmp = m[next = start];
do {
i = (next % h) * w + next / h;
m[next] = (i == start) ? tmp : m[i];
next = i;
} while (next > start);
}
}
 
void show_matrix(double *m, int w, int h)
{
int i, j;
for (i = 0; i < h; i++) {
for (j = 0; j < w; j++)
printf("%2g ", m[i * w + j]);
putchar('\n');
}
}
 
int main(void)
{
int i;
double m[15];
for (i = 0; i < 15; i++) m[i] = i + 1;
 
puts("before transpose:");
show_matrix(m, 3, 5);
 
transpose(m, 3, 5);
 
puts("\nafter transpose:");
show_matrix(m, 5, 3);
 
return matrix0;▼
char *cursor;
}</lang>output<lang>before transpose:
char carry[ALIGNMENT];
1 2 3 {▼
size_t block_size, remaining_size;
4 5 6 }▼
int nadir, lag, orbit, ents;
7 8 9 {▼
10 11 12
13 14 15
 
after transpose:
if (rows == 1 || cols == 1)
1 4 return7 10 13 matrix;
2 ents5 = rows8 *11 14 cols;
3 6 9 12 15 </lang>
cursor = (char *) matrix;
remaining_size = item_size;
while ((block_size = ALIGNMENT < remaining_size ? ALIGNMENT : remaining_size))
{
nadir = 1; /* first and last entries are always fixed points so aren't visited */
while (nadir + 1 < ents)
{
memcpy(carry, &cursor[(lag = nadir) * item_size], block_size);
while ((orbit = lag / rows + cols * (lag % rows)) > nadir) /* follow a complete cycle */
▲ {
memcpy(&cursor[lag * item_size], &cursor[orbit * item_size], block_size);
lag = orbit;
▲ }
memcpy(&cursor[lag * item_size], carry, block_size);
orbit = nadir++;
while (orbit < nadir && nadir + 1 < ents) /* find the next unvisited index by an exhaustive search */
▲ {
orbit = nadir;
while ((orbit = orbit / rows + cols * (orbit % rows)) > nadir);
if (orbit < nadir) nadir++;
}
}
cursor += block_size;
remaining_size -= block_size;
}
▲ return matrix;
}</lang>
No extra storage allocation is required by the caller. Here are
usage examples for an array of doubles and an array of complex numbers.
<lang c>a = (double *) transpose_matrix((void *) a, n, m, sizeof(double));
b = (complex *) transpose_matrix((void *) b, n, m, sizeof(complex));</lang>
After execution, the memory maps of a and b will be those of m by n arrays instead
of n by m.
 
=={{header|C++}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/56874"