4

テンプレート化されたsparse_vectorクラスを実装しています。これはベクトルのようなものですが、デフォルトの構築値とは異なる要素のみを格納します。

したがって、sparse_vectorは、値がT（）ではないすべてのインデックスの遅延ソートされたインデックスと値のペアを格納します。

私は、数値ライブラリ内の既存のスパースベクトルに基づいて実装を行っていますが、非数値型Tも処理します。見てみましboost::numeric::ublas::coordinate_vectorたeigen::SparseVector。

両方のストア：

size_t* indices_;  // a dynamic array
T* values_;  // a dynamic array 
int size_;
int capacity_;

単純に使ってみませんか

vector<pair<size_t, T>> data_;

私の主な質問は、両方のシステムの長所と短所は何ですか、そしてどちらが最終的に優れているかです。

ペアのベクトルは、size_とcapacity_を管理し、付随するイテレータクラスを単純化します。また、2つではなく1つのメモリブロックがあるため、再割り当ての半分が発生し、参照の局所性が向上する可能性があります。

他のソリューションでは、検索中にキャッシュラインがインデックスデータのみでいっぱいになるため、検索が速くなる可能性があります。Tが8バイトタイプの場合、アライメントの利点もいくつかありますか？

ペアのベクトルがより良い解決策であるように私には思えますが、両方のコンテナーがもう一方の解決策を選択しました。なんで？

4

2 に答える 2

2

別のリストにインデックスがあると、検索が速くなります。ご提案のとおり、特にTが大きい場合は、キャッシュをより効果的に使用できます。

独自に実装したい場合は、std::map（またはstd::unordered_map）を使用してみませんか？キーは大きくなりますが、実装時間はゼロに近くなります。

于 2010-05-11T06:28:57.210 に答える
1

事実上、彼らは（いわば）車輪の再発明をしたようです。

私は個人的にあなたの必要性のために2つのライブラリを検討します：

  • Loki、for -> （あなたがやりたいことです）Loki::AssocVector上に実装されたマップのインターフェースvector
  • Boost.Iterator、そのiterator_adaptorクラス。Compositionによる新しいコンテナの実装が非常に簡単になります。

備考として、これはDefaultConstructibleであるT()ため、とは異なる値よりももう少し一般的なものにしたいと思うかもしれません。Tをとるコンストラクターを提供できますT const&。汎用コンテナーを作成するときは、必要な要件を可能な限り減らすようにしてください（パフォーマンスを低下させない限り）。

また、ストレージにforを使用するというアイデアは、vector少数の値には非常に適していますが、基になるコンテナーをクラシックに変更するmapかunordered_map、値の数が増える場合は、変更することをお勧めします。プロファイリング/タイミングの価値があるかもしれません。stackSTLは、実装を少し難しくする可能性がありますが、のようなコンテナアダプタでこの機能を提供することに注意してください。

楽しむ。

于 2010-05-11T07:00:10.447 に答える