4

私はC ++を初めて使用し、行列を乗算するためにstrassenのアルゴリズムをプログラムしようとしています。アルゴリズムの一部では、行列を 4 つの部分に分割する必要があります。

4 5 6 7
6 7 8 9
1 2 3 4
2 3 5 6

分割:

4 5   6 7
6 7   8 9

1 2   3 4
2 3   5 6

(各部分は再帰的に再利用され、分割されます)。元のマトリックスからデータをループおよびコピーせずにマトリックスを分割したい (時間がかかるため)。私が読んでいる本では、マトリックスは「インデックス計算を使用して分割され、元のマトリックスの行インデックスの範囲と列インデックスの範囲によってサブマトリックスを識別します。これが何を意味するのかわかりません。

また、2D配列とベクトルのどちらを使用する必要があるかわかりませんか? 多くの人がベクトルを推奨しているのを見てきましたが、これまでのところすべてを2D配列で書いているので、2D配列で私が望むことが可能になることを願っています.

ps行列の次元は常に2の累乗であり、nxn（平方）であると想定できます。また、これに似た多くの質問を見てきましたが、実際に探している解決策はありません。

ありがとう

4

1 に答える 1

1

サブマトリックスをビューとして直接サポートするマトリックス クラスを作成できます。

template<typename T>
struct Matrix {
    int rows, cols, stride;
    std::vector<T> data; // Possibly empty for a view
    T *ptr;

    // A fresh matrix (owning its data)
    Matrix(int rows, int cols)
        : rows(rows), cols(cols), stride(cols),
          data(rows*cols),
          ptr(&data[0])
    {
    }

    // A view of a sub-matrix (pointing to the original data!)
    Matrix(Matrix& m, int row0, int col0, int rows, int cols)
        : rows(rows), cols(cols), stride(m.stride),
          ptr[&m(row0, col0)]
    {
    }

    T& operator()(int row, int col) {
        return ptr[row*stride + col];
    }

    ...
};

もちろん、ビューが所有するマトリックスよりも長く存続しないようにする必要があり、その操作が禁止されていない場合にビュー オブジェクトをコピーする意味に注意を払う必要があります。

ビューを所有するマトリックスに変換するような明示的な操作を追加すると便利な場合があります (コピー コンストラクターがそれを実行しない場合)。

于 2015-11-15T18:21:36.720 に答える