2

事項

対称行列を連続して格納する行列クラスがあります。これらの行列は (対角線でのミラーリングに関して) 軸対称であるという優れた特性を持っているため、ストレージを最適化して上三角行列または下三角行列にすることができます。

次のスキームは、上三角行列として格納された 6x6 対称行列の格納スキームを示しています。

r\c 0 1 2 3 4 5
   --------------------------------------
 0 | 0 | 1 | 2 | 3 | 4 | 5 |
   --------------------------------------
 1 | | | 6 | 7 | 8 | 9 | 10 |
   --------------------------------------
 2 | | | | | 11 | 12 | 13 | 14 |
   --------------------------------------
 3 | | | | | | | 15 | 16 | 17 |
   --------------------------------------
 4 | | | | | | | | | 18 | 19 |
   --------------------------------------
 5 | | | | | | | | | | | 20 |
   --------------------------------------

次に、その行列の行と列の反復子を設計したいと思います。実際の行と列を反復するのではなく、実質的に完全な対称行列の行と列を反復します。

例:

for (the_iterator i=matrix.row(2).begin(); i!=matrix.row(2).end(); ++i)
{
    cout << *i << " ";
}

これにより、要素の内容が出力されます

2 7 11 12 13 14

(上記のように、行列が 6x6 三角行列の場合)。

幸いなことに、対称行列の場合、行のシーケンスは列のシーケンスとi同じであるiため、必要なイテレータ タイプは 1 つだけです。

行列クラスは、行と列のインデックスに従って要素にアクセスするメソッドを提供します

reference operator() (size_type const r, size_type const c) { /*...*/ }

イテレータの設計方法について 2 つのアイデアが浮かびました。数学をある点から別の点に切り替える。

1. 行列参照によるイテレータの簡単な進め方

一方では、マトリックスへの参照、目的の行/列の番号、およびこの行/列の現在の要素を格納できます。

matrix_type & m;
size_type fixed;
size_type free;

これにより、operator()逆参照のためのマトリックス クラスの使用と、簡単なイテレータの進行が可能になります。

class the_iterator
  // ...
{
  // ...
  reference operator* () const _NOEXCEPT 
  { 
    return *m(fixed, free);
  }
  // ...
  this_type & operator++ (void) _NOEXCEPT
  { // increment then return
    ++free;
    return *this; 
  }
  // ...
};

これには明らかな欠点が 1 つあります。 を呼び出すたびにoperator()、行インデックスと列インデックスを使用して計算される基になるメモリ内の連続したインデックスが必要です。

2. 要素へのポインタによる簡単な逆参照

一方で、pイテレーターの進行を制御するためのポインター (matrix value_type 要素ポインター) といくつかの制御値を持つことも可能です。垂直部分 (2 -> 7 -> 11; 上記の例を参照) では、ポインターを 5+4 進める必要があり、水平部分 (11 -> 12 -> 13 -> 14) では、ポインターをpointer1 ずつ変更する必要があります。 +1+1。これは自明ではありませんが、それほど難しくもなく、反復なしで代数的に解くことができます。

*p逆参照/要素アクセスは、使用できるようになったため、どの計算にも関連付けられなくなりました。これが私が現在行っている方法です。

質問：

「計算作業」はどこで行う必要があり、どちらに進みますか (そしてその理由)?

私はどちらかを持つことができます

  • シンプルで高速な反復子の進行ですが、要素へのアクセスが必要です。
  • 高度化が要求されますが、要素へのアクセスはシンプルかつ高速です。

イテレータは (ループ内で) サイクルごとに 1 回だけ進む可能性が高いため、私は 2 番目の傾向がありますが、複数回逆参照される可能性があります。

4

1 に答える 1

0

本当に、あなたの例のようにデータを配置する必要がない限り、まず三角配列の基本的な特徴を利用してインデックス作成を高速化します。これにより、最初の選択がより適切になります。マトリックスへの参照、固定された行/列、および現在の空きインデックス値を保存し、パフォーマンスのために高速なインデックス作成に依存します。

単位三角行列のインデックスについて私が知っている最も単純なマッピングは次のとおりです。

int unitriangular_index(int row, int col)
{
    assert(row >= 0);
    assert(col >= row);

    int base = (col * (col + 1)) / 2;

    return (base + row);
}

そのように値を配置できる場合、行列のスライスへのアクセスは次のようになります。

int reflected_index(int row, int col)
{
    assert(row >= 0);
    assert(col >= 0);

    if (col < row)
    {
        return (unitriangular_index(col, row));
    }
    else
    {
        return (unitriangular_index(row, col));
    }
}
于 2013-06-27T14:13:33.553 に答える