我正在研究 wiki 文章中描述的方法的实现，用于方矩阵的就地缓存不经意转置。
https://en.wikipedia.org/wiki/In-place_matrix_transposition
该算法基本上递归地将矩阵分成四份，然后转置沿对角线的象限并交换其上方和下方的象限。实际的转置/交换仅在矩阵大小为 2*2 或更小时发生，否则将再次拆分。
我把它分成了三个函数:
这将启动给定大小 N 的过程:
void SmartTranspose(int A[row][col]) {
Transpose(A, 0, 0, N, N);
}
然后:
void Transpose(int A[row][col], int x, int y, int w, int h) {
int Temp;
if ((w - x) * (h - y) <= 4){
for (int row1 = x ; row1 < w -1 ; row1++)
for (int col1 = y + 1 ; col1 < h ; col1++) {
Temp = A[row1][col1];
printf("transp: %d %d\n", A[row1][col1], A[col1] [row1]);
A[row1][col1] = A[col1][row1];
A[col1][row1] = Temp;
}
}
else {
int halfh = h / 2;
int halfw = w / 2;
Transpose(A, x, y, halfw , halfh);
Transpose(A, x + halfw, y + halfh, w , h);
TransposeSwap(A, x + halfw, y, w, halfh, x, y + halfh, halfw , h);
}
}
最后:
void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1) {
int Temp; int row2 = x1; int col2 = y1;
if ((w - x) * (h - y) <= 4 && (w1 - x1) * (h1 - y1) <= 4) {
for(row1 = x; row1 < w; row1++)
for(col1 = y; col1 < h; col1++)
{
Temp = A[row1][col1] ;
A[row1][col1] = A[col1][row1];
A[col1][row1] = Temp;
}
}
else {
printf("RECURSE");
int halfh = h / 2;
int halfw = w / 2;
int halfh1 = h1 / 2;
int halfw1 = w1 / 2;
TransposeSwap(A, x, y, halfw, halfh, x1, y1, halfw1, halfh1);
TransposeSwap(A, x + halfw, y, w, h - halfh, x1, y1 + halfh1, halfw1, h1);
TransposeSwap(A, x , y + halfh, halfw, h, x1 + halfw1, y1, w1, halfh1);
TransposeSwap(A, x + halfw, y + halfh, w, h, x1 + halfw1, y1 + halfh1, w1, h1);
}
}
然而，这不起作用，我正在努力寻找我的逻辑哪里出了问题。
编辑:输出示例
Original matrix:
1948037971 40713922 986050715 74181839 943010147 1060710730
18590233 268906808 1966315840 1325423973 398061279 2047858287
513589654 1727398080 2016821685 277200601 1611383116 2000671901
228038281 1863845528 106517081 1934721636 745170263 1736525254
224427632 687572994 1249224754 1497415191 537022734 1443375385
1054092341 337577057 1484089307 2040143056 411758897 279615807
Transposed matrix:
1948037971 18590233 513589654 74181839 943010147 1060710730
40713922 268906808 1727398080 1325423973 398061279 2047858287
986050715 1966315840 2016821685 277200601 1611383116 2000671901
228038281 1863845528 106517081 1934721636 745170263 1736525254
224427632 687572994 1249224754 1497415191 537022734 1443375385
1054092341 337577057 1484089307 2040143056 411758897 279615807
正确的输出应该是一个转置矩阵。
编辑:主要函数和声明:
int row = 40000 , col = 40000;
static int A[40000][40000];
static int N[100] = {0};
void SmartTranspose(int A[row][col]);
void Transpose(int A[row][col], int x, int y, int w, int h);
void InitializeMatrix(int X[row][col]);
void PrintMatrix(int X[row][col]);
double pow(double x, double y);
int matrix = 0;
void TransposeSwap(int A[row][col], int x, int y, int w, int h,int x1, int y1, int w1, int h1);
int main(){
srand(time(NULL));
double sizes = 0;
int count = 0;
for(sizes = 20; sizes < 30; sizes++)
{
N[count] = floor(pow(2, (sizes/9)));
printf("N %d\n", N[count]);
count++; }
for (matrix = 0; matrix <= count -1 ; matrix++){
InitializeMatrix(A);
printf("N %d\n",N[matrix]);
printf("\nOriginal matrix: \n");
SmartTranspose(A);
printf("E\n");
printf("\nTransposed matrix: \n");
PrintMatrix(A);
}
return 0;
}
完整代码的链接:https://jpst.it/QaBq
最佳答案
这是我尝试演示一种有效算法的尝试。由于矩阵是正方形的，我去掉了一些函数参数。此外，我还留下了一些调试代码来显示算法在每个递归级别的进度。
它可以转置任何对角线在主对角线上的子矩阵。我在 100x100 阵列的 0,0 角使用 9x9 矩阵进行了测试。
#include <stdio.h>
int dbglvl;
void TransposeSwap(int dim, int A[dim][dim], int rs, int cs, int re, int ce) {
int Temp;
for (Temp = 0; Temp < dbglvl; Temp++) {
putchar('>');
}
printf("TransposeSwap(dim=%d, rs=%d, cs=%d, re=%d, ce=%d)\n", dim, rs, cs, re, ce);
if (re - rs <= 2 && ce - cs <= 2) {
for (int r = rs; r < re; r++)
for (int c = cs; c < ce; c++)
{
printf("transp %d %d: %d %d\n", r, c, A[r][c], A[c][r]);
Temp = A[r][c] ;
A[r][c] = A[c][r];
A[c][r] = Temp;
}
}
else {
int rm = (rs + re) / 2;
int cm = (cs + ce) / 2;
dbglvl++;
TransposeSwap(dim, A, rs, cs, rm, cm);
TransposeSwap(dim, A, rm, cs, re, cm);
TransposeSwap(dim, A, rs, cm, rm, ce);
TransposeSwap(dim, A, rm, cm, re, ce);
dbglvl--;
}
for (Temp = 0; Temp < dbglvl; Temp++) {
putchar('<');
}
printf("TransposeSwap\n");
}
void Transpose(int dim, int A[dim][dim], int s, int e) {
int Temp;
for (Temp = 0; Temp < dbglvl; Temp++) {
putchar('>');
}
printf("Transpose(dim=%d, s=%d, e=%d)\n", dim, s, e);
if (e - s <= 2) {
for (int r = s; r < e - 1 ; r++)
for (int c = s + 1 ; c < e ; c++) {
printf("transp %d %d: %d %d\n", r, c, A[r][c], A[c][r]);
Temp = A[r][c];
A[r][c] = A[c][r];
A[c][r] = Temp;
}
}
else {
int m = (s + e) / 2;
dbglvl++;
Transpose(dim, A, s, m);
Transpose(dim, A, m, e);
TransposeSwap(dim, A, m, s, e, m);
dbglvl--;
}
for (Temp = 0; Temp < dbglvl; Temp++) {
putchar('<');
}
printf("Transpose\n");
}
void Dump(int dim, int A[dim][dim], int rs, int cs, int re, int ce) {
int r, c;
for (r = rs; r < re; r++) {
for (c = cs; c < ce; c++) {
printf("%d ", A[r][c]);
}
putchar('\n');
}
}
#define N 100
int test[N][N] = {
{ 11, 12, 13, 14, 15, 16, 17, 18, 19 },
{ 21, 22, 23, 24, 25, 26, 27, 28, 29 },
{ 31, 32, 33, 34, 35, 36, 37, 38, 39 },
{ 41, 42, 43, 44, 45, 46, 47, 48, 49 },
{ 51, 52, 53, 54, 55, 56, 57, 58, 59 },
{ 61, 62, 63, 64, 65, 66, 67, 68, 69 },
{ 71, 72, 73, 74, 75, 76, 77, 78, 79 },
{ 81, 82, 83, 84, 85, 86, 87, 88, 89 },
{ 91, 92, 93, 94, 95, 96, 97, 98, 99 },
};
int main(void) {
puts("Original:");
Dump(N, test, 0, 0, 9, 9);
putchar('\n');
dbglvl = 1;
Transpose(N, test, 0, 9);
putchar('\n');
puts("Transposed:");
Dump(N, test, 0, 0, 9, 9);
return 0;
}
关于c - 分而治之矩阵的就地转置，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41041369/