3

行列乗算を行う別の方法を検討しています。行列を 2 次元配列として格納する代わりに、次のようなベクトルを使用しています。

vector<pair<pair<int,int >,int > >

私の行列を保存します。my ペア (pair) 内のペアにはインデックス (i,j) が格納され、もう一方の int には指定された (i,j) ペアの値が格納されます。この方法でスパース配列を実装すると、運が良いかもしれないと思いました。

問題は、この行列をそれ自体で乗算しようとするときです。

これが 2 次元配列の実装である場合、次のように行列を乗算します。

   for(i=0; i<row1; i++)
    {
        for(j=0; j<col1; j++)
        {
          C[i][j] = 0;
         for(k=0; k<col2; k++) 
           C[i][j] += A[i][j] * A[j][k];
      }
    }

「ペアのペア」のベクトルを使用して同じ結果を達成する方法を誰かが指摘できますか?

ありがとう

4

1 に答える 1

1

これまでのところ、1 つの値を 1 つの場所に格納できます。行列にいくつかの非ゼロ エントリを格納する場合は、より大きな構造体でより多くのペアのペアが必要になります。

map<pair<int, int>, int>次の論理的なステップになります。の並べ替え順序firstでは座標がより重要になるため、行を反復処理できるようになりました。map

列を反復するには、その優先順位を逆にします。

typedef pair<int, int> mx_coord;
struct reverse_compare {
    bool operator() (mx_coord const &l, mx_coord const &r) const
        { return l.second < r.second? true :
                 r.second < l.second? false : l.first < r.first; }
};

typedef map< mx_coord, int > matrix;
typedef map< mx_coord, int, reverse_compare > matrix_transpose;

A を B で乗算するには、B を転置し、A と B を反復処理して、重要度の低い座標が一致する要素を乗算します。

B を移調するには:

matrix_transpose b_t( b.begin(), b.end() ); // complexity: n log n
于 2010-04-06T04:32:54.667 に答える