6

現在のプロジェクトでは、いくつかのことにスパースベクトルを使用する必要があります。ただ、私はプロジェクトを担当していないので、外部の図書館は使えません。STLとOpenCVしか利用できません。

私はいくつかのstackoverflowの回答済みの質問を調べましたが、それらは特定のアプローチ、限られた数のアプローチの比較（2）、およびスパースベクトルを具体的に扱う場合の外部ライブラリのいずれかに焦点を当てています。スパース行列を実装するための優れたアイデアもいくつかあります。

私が欲しいのは、具体的にはスパースベクトルです（インデックスは常に1次元になり、データはこの質問には関係ありません）。それ自体ではプロジェクトではないものを実装したいのですが、デモンストレーション以上の目的（たとえば、まともな速度を達成し、メモリのオーバーヘッドをあまり多くしたくない）に使用でき、うまくいけば再実行できます。後で使用します。私が検討したオプションは次のとおりです。

  • SparseMatのOpenCV実装を私のニーズに適合させる
  • を使用しstd::mapて値を格納します（または、ゼロ要素にインデックスを付ける場合にデフォルト値を返す非常に単純なラッパーを作成します）
  • 要素std::vector< std::pair < int , data_type > >にインデックスとデータを格納できる場所を使用するstd::pair

これらのソリューションのいずれかが、スパースベクトルとしての汎用使用に適していますか？私はすべてへのすべてのアプローチに浮き沈みがあることを知っていますが、どのアプローチを選択するかについての議論された提案は非常にありがたいです。また、私が考えていないアプローチを推奨することは、誰かが彼がより良い提案をしていると思うなら、大歓迎です。

私の特定の場合の使用法は次のとおりです。

  • ベクトルは、作成後に変更されない可能性があります（現時点では、これは必要ありませんが、100％表示されないことを保証することはできません）
  • 最も一般的な操作は、そのような2つのベクトルの内積であると予想されます（つまり、多かれ少なかれ線形の順次方法で要素にアクセスします）
  • 私が今予測できる唯一のルックアップは、（多分）特定の要素がゼロ要素であるかどうかを天気をチェックすることです
  • 約500の非ゼロ要素が予想されます
  • つまり、ほとんどの場合、スパースベクトルは、各座標を個別に調べる必要なしに、ベクトル（多次元ポイント）の数学的概念として使用されます。

それでも、元の質問で書いたように、汎用のスパースベクトルの実装について提案したいと思います。

4

2 に答える 2

6

私はstd::mapあなたに最高の結果を与えると信じています。SpareseMat、わかりませんが、あなたが言及した他の2つの方法の中で、std::map挿入と削除O(log(n))だけでなく、ルックアップも提供します。O(log(n))ただし、すべてのvectorデータを検索する必要があります（したがって、O(n)ルックアップがあります）。O(1)挿入はありますが、取り外しO(n)があります。私の推測では、ルックアップがたくさんあるので、おそらくstd::mapあなたにとってより良いでしょう。

アプリケーションによってvectorは、構造の最初の作成時にメソッドを使用し、使用を開始したらメソッドを変換してmap、両方の長所を活用することをお勧めします（ただし、多くの場合、これは当てはまりません。たとえば、繰り返しインデックスがあります）。

それに加えhashて、あなたにすべてを与えるはずO(1)ですが、実際にはそうではないかもしれませんが、のルックアップはO(log(n))あなたが望むことができる最高のものです。二分探索が可能なベクトル、または比較によるデータの検索に基づく他の方法を思い付くかもしれませんが、最終的にはそれらはすべてそうなるO(log(n))ので、簡単に実行できるものを使用する方がよいでしょうstd::map。

更新：質問の更新に基づいて、ベクトルは作成後に変更されない可能性が高く、最も一般的な操作は内積であると予想されることを示しています。次のことをお勧めします。

まず、自分で提案したようにペアのベクトルを使用します。作成中に、単純にパフォーマンスpush_backを得ることができO(1)ます。1その後、ベクトルを並べ替えることができます。ドット積は非常に単純です2：

int dot = 0;
unsigned int index_v1 = 0, index_v2 = 0;
while (index_v1 < v1.size() && index_v2 < v2.size())
    if (v1[index_v1].first == v2[index_v2].first)
        dot += v1[index_v1++].second * v2[index_v2++].second;
    else if (v1[index_v1].first < v2[index_v2].first)
        ++index_v1;
    else
        ++index_v2;

特定の要素がゼロ要素であるかどうかを確認することは、単純な二分探索であり、要素が見つかるかどうかを確認します（O(log(n))パフォーマンス）。

この構造をポイントとして使用するという事実を考えると、ベクトルのままにしておく方がよいと思います。後で外積または他の幾何学的操作を実行したい場合があります。

時々ベクトルに何かを挿入する必要があるかもしれないという事実に関して、あなたはそれをその場に挿入しなければならないでしょう（それでベクトルはソートされたままです）。パフォーマンスはそうなるでしょうがO(n)、それは頻繁には起こらないので、それは問題ではないはずです。

1これらのベクトルが何百万もある場合を除いて、実際には目立った違いはO(1)ありません。O(log(n))n ~= 500

2間違いなく、amapを使用し、その上でイテレータを使用して、インデックス順にドット積を実行することもできます。の次のノードに到達できるスレッドツリーstd::mapを使用した場合、パフォーマンスは同じになります。O(1)

于 2012-05-29T10:12:22.850 に答える
3

接吻

std::map<size_t, YourData>最も単純なソリューションから始めます。つまり、特定のスパースベクトル構造にラップします。

template <typename V>
class SparseVector {
public:

private:
    std::map<size_t, V> specificValues;
    V defaultValue;
};

これmapにより、すべてのユースケース（検索/挿入/更新）で優れたデフォルトパフォーマンスが得られます。カスタムクラスを使用すると、別の実装に変更する必要がある場合でも、クライアントソースを変更する必要がなく、再コンパイルするだけで済みます。

于 2012-05-29T10:20:35.910 に答える