2

私は C の初心者です。転置を使用して行列の乗算を実行するコードを作成しようとしていました。実行時間に関してコードを改善する方法はありますか?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <time.h>

int main()
{   

  int a[3][3] = {{1,0, 1}, {2, 2, 4},{1, 2, 3}};

        int b[3][3] ={ { 2, 3, 1}, { 6, 6, 2 }, { 9, 9, 0 } };
        int result[3][3];
        double tmp;
        int i,j,k;
        for (i=0; i<3; i++) //i = col
          {
            for (k=0; k<3; k++)
            {
              tmp = a[i][k];
              for (j=0; j<3; j++) //j = row
              {
                result[i][j] += tmp * b[k][j];
                printf("%d\t",result[i][j]);
              }
            }
          }
}
4

4 に答える 4

2

行列の乗算の実装は、複数の理由により間違っています。行列の乗算は、最初の行列のすべての行と2番目の行列のすべての列の内積を計算することによって実行されます。これは、実装では本質的に欠落しています。a [i] [k]を指す一時変数を使用しています。これは、最も内側のループ全体で変更されません。最初の行列の行インデックスと2番目の行列の列インデックス（または転置乗算の場合はその逆）は、実際の乗算ステップ中に更新する必要があります。また、結果は3番目の行列に段階的に追加されます。これは、ジャンク値の問題を回避するために、Cなどの言語ではすべての要素を0で初期化する必要があります。

于 2012-10-09T10:34:01.000 に答える
1

非常に直感的ではありませんが、試してみるべきことの 1 つは、ソース コードの最適化を解除し、明示的な を削除することtmpです。

for (i=0; i<3; i++)
    for (k=0; k<3; k++)
        for (j=0; j<3; j++) //j = row
        {
            result[i][j] += a[i][k] * b[k][j];
        }

これにより、コンパイラの手をいくらか解放し、共通の不変部分式を独自に見つけることができます。それらをループの外に移動し、おそらくより高速なパラダイム (スタックの場所ではなくレジスター) を使用して保存します。

ターゲット CPU によっては、速度の最適化が有効になっている賢明なコンパイラは、独立したレジスタを割り当てて内部ループを展開することで、CPU のパイプラインを並列処理できる場合があります。もちろん、これはすべて、(適切なコンパイラ オプションを使用して) コンパイラに最適化を指示するかどうかにかかっています。

于 2012-10-09T07:58:08.963 に答える