4

メンバーを使用して小さな疎行列クラスを作成しました。

std::map<int,std::map<int,double> > sm;

以下のメソッドは、反復子を介して不可能な場合に、マトリックスの要素にアクセスするために使用する関数です。

double matrix::operator()(int r,int c) const
{
    std::map<int,std::map<int,double> >::const_iterator i = sm.find(r);
    if(i==sm.end()) { return 0.0; }
    std::map<int,double>::const_iterator j = i->second.find(c);
    if(j==i->second.end()) { return 0.0; }
    return j->second;
}

それでも、この関数は非常に頻繁に呼び出される必要があります。この機能を改善する方法を誰かが考えていますか? ありがとうございます。

4

2 に答える 2

6

ライブラリを使用せずに独自のコードを作成する場合は、この変更によりパフォーマンスが大幅に向上する可能性があります。

std::map<std::pair<int,int>, double> sm;

さらに増やすには、ハッシュされたコンテナに移動します。

std::unordered_map<std::pair<int,int>, double> sm;

（tr1、boost、またはC ++ 0xを使用）

編集：最初のケースでは、次のように繰り返すことができますrow：

for(auto& cell : make_pair(
    sm.lower_bound(make_pair(row, 0)), sm.lower_bound(make_pair(row+1, 0))))
{ ... }

Boost.MultiIndexを使用すれば、適切なファンクターを使用してequal_rangeを1回呼び出すだけで上記を実行できると思います。

すべてにわたって：

for(auto& cell : sm)
{ ... }

列を反復処理するには、すべてのセルを個別に検索する必要があります。データ構造もこの操作を提供しないことに注意してください。

于 2010-10-01T19:22:48.013 に答える
1

あなたはおそらくこれを嫌うでしょうが、次の (表示目的で小さい) 行列の行の場合:

1 0 0 5 9 0 0 0

マトリックス内のその位置にゼロ以外またはゼロがあったかどうかを反映するために、各ビットが設定またはクリアされたビット配列（この場合は8ビット）を持つことができます。

次に、ゼロ以外の数値を次のようにまとめて通常の配列に格納します。

{ 1, 5, 9 }

およびバイナリフラグ

0x98 // バイナリ 1001 1000

行列の行を反復するには、ビット操作を使用してビット配列をループします。

while (! /* not at the end of the bit array */ ) {
    f = get_next_from_bit_array();  // This is just bitwise shift and bitwise & 
    if (!f) {
       val = 0;
    } else {
       val = compressed_row[i];
       i++;
    }
    do_action(val);
}

ここにある私のコードはデモンストレーション用であり、あまり C++ ではありませんが、アイデアが得られることを願っています。

ビット配列を使用すると、メモリのはるかに小さな領域でスパース行を調べることができます。これは、メモリ アクセスが少なくなり、キャッシュの局所性が向上することを意味します。

使用しているマトリックスが非常にまばらな場合は、これを他の次元にも拡張できます (行のまばらな配列を持つ) が、行全体が空になる可能性はおそらく低いです。

于 2010-10-01T20:14:20.883 に答える