3

stl の bitset または boost の dynamic_bitset<> を使用して、マップ (行列行 x 列) をビットで表しています (好きなものを使用できます)。その行列の部分行列をより小さいサイズで取得する必要があります(たとえば、 a(2,2) a(2,3) a(3,2) a(3,3) にはサイズ 2 があります)。マトリックスをビットで表し、反復なしで startindex と length からサブマトリックスを取得するための効率的な構造はありますか?

4

1 に答える 1

3

マトリックスとサブマトリックス間でデータを効率的に共有できます。秘訣は、クラス内の 3 つの変数を追跡することです。

  • 行ストライド
  • 始める
  • データ

は、使用が終了したら基礎となるデータを破棄できるようdataに、同様の構造である必要があります。によって参照されるデータへのポインタとなり、次の行に到達するまでの移動距離を示します。shared_ptrstartdatarow_stride

あなたが追跡したいかもしれない追加のものは次のとおりです

  • 列のストライド (これにより、他の興味深いビューをマトリックスに取り込み、転置を効率的にサポートできます)。
  • 行と列の長さ - これらは、デバッグや、ループを作成したい場合に便利で、乗算を簡単に行うことができます。

これが非ビットベースのアプローチでどのように見えるかを次に示します (多くのことを省略しましたが、要点を理解していただければ幸いです)。

template<typename T>
struct MatrixData
{
   T * data;
   explicit MatrixData( size_t N ) { new T[N]; }
   ~MatrixData() { delete [] data; }
private:
    MatrixData( const MatrixData & );
    MatrixData& operator=( const MatrixData & );
};

template<typename T>
class Matrix
{
    Matrix(size_t nni, size_t nnj) :
      data( new MatrixData( nni*nnj ) ),
      ni(nni),
      nj(nnj),
      row_stride(ni),
      col_stride(1)
    {
    }

    T operator()( size_t i, size_t j)
    {
       assert( i < ni );
       assert( j < nj );
       return start + i * col_stride + j * row_stride;
    }

    Matrix submatrix( size_t i_start, size_t j_start, size_t new_ni, size_t new_nj )
    {
       assert( i_start + new_ni < ni );
       assert( j_start + new_nj < nj );

       Matrix retval(*this);
       retval.start += i_start * col_stride + j_start * row_stride;
       retval.ni = new_ni;
       retval.nj = new_nj;
       return retval;
    }

    Matrix transpose()
    {
       Matrix retval(*this);
       std::swap(retval.ni,retval.nj);
       std::swap(retval.row_stride,retval.col_stride);
    }

  private:
    shared_ptr<MatrixData> data;
    T* start;
    size_t ni;
    size_t nj;
    size_t row_stride;
    size_t col_stride;

};

ビット ベースのバージョンでこれを機能させるにMatrixDataは、ボット ベースの構造の 1 つを保持するように を変更startし、構造へのインデックスに変更しoperator()、データに正しくアクセスするように変更する必要があります。

于 2012-06-27T08:11:36.107 に答える