こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

転置行列アルゴリズム

こんにちは。プログラミングを学んでいる学生です。
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;
}

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

投稿日時 - 2008-01-20 23:39:51

QNo.3698544

すぐに回答ほしいです

質問者が選んだベストアンサー

 
 "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];
}

投稿日時 - 2008-01-21 03:25:09

お礼

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

投稿日時 - 2008-01-26 21:06:56

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(4)

ANo.3

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

投稿日時 - 2008-01-21 02:41:38

お礼

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

投稿日時 - 2008-01-26 21:04:08

ANo.2

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

投稿日時 - 2008-01-21 01:18:24

ANo.1

#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;
}

投稿日時 - 2008-01-21 01:06:36

あなたにオススメの質問