転置行列アルゴリズム

質問

こんにちは。プログラミングを学んでいる学生です。
N*Nのint型の配列を転置するCプログラムでなるべく性能の良いものを書け、という課題が出て、それと同時にシンプルな(性能が悪いと思われる)サンプルが配布されてました。
ですが、それを超えるようなアルゴリズムがどうしても思いつきません。
何かアドバイスいただけたらうれしいです。

配布メソッド:
#define N 64 //Nは64,128,512,...,2048をはかる
typedef int matrix_t[N][N];
void naive_rotate(matrix_t src, matrix_t dst){
　　int i,j;
　　for(i=0;i<N;i++)
　　 for(j=0;j<N;j++)
　　　　　 dst[N-1-j][i]=src[i][j];
return;
}

メソッドの７行目をdst[j][i]にしたらあまり変化ありませんでした。
また、i==Jのときcontinueするようにしたら、逆に遅くなってしまいました。

回答No.4

yaemon_2006 · ベストアンサー

"ANo.1"訂正。
void func(int a[][N], int b[][N], int n)
{
int i, j;

for(i = 0; i < n / 2; i ++){
for(j = i; j < n - i - 1; j ++){
b[i][j] = a[j][n - i - 1];
b[j + 1][i] = a[i][n - j - 2];
b[n - i - 1][j + 1] = a[j + 1][i];
b[j][n - i - 1] = a[n - i - 1][n - j - 1];
}
}
if(n % 2) b[n / 2][n / 2] = a[n / 2][n / 2];
}

お礼

一気に半分やってしまうということですね。
なるほど！　思いつきませんでした...
勉強が足りないですね。
ありがとうございます。やってみます。

回答No.3

wave_sc

dstを使わずにsrcだけで処理するのはどうでしょうか。
src[i][j]とsrc[j][i]の値を入れ替えるようにすれば計算量は減るはずです。

お礼

引数を一つ消す代わりに、中で数値を保存する配列を作る、
ということでしょうか。
ありがとうございます。やってみます。

回答No.2

yaemon_2006

ごめん。"ANo.1"は、間違い。

回答No.1

yaemon_2006

#include <stdio.h>

#define N 10

void init(int a[][N], int n)
{
int i, j;

for(i = 0; i < n; i ++){
for(j = 0; j < n; j ++) a[i][j] = n * i + j;
}
}

void func(int a[][N], int b[][N], int n)
{
int i, j;

for(i = 0; i < n / 2; i ++){
for(j = i; j < n - i; j ++){
b[i][j] = a[j][n - i - 1];
b[j][i] = a[i][n - j - 1];
b[n - i - 1][j] = a[j][i];
b[j][n - i - 1] = a[n - j - 1][n - i - 1];
}
}
}

void print(int a[][N], int n)
{
int i, j;

for(i = 0; i < n; i ++){
for(j = 0; j < n; j ++) printf("%3d ", a[i][j]);
putchar('\n');
}
putchar('\n');
}

int main(void)
{
int a[N][N], b[N][N];

init(a, N);
print(a, N);
func(a, b, N);
print(b, N);
return 0;
}