0

この問題に使用するのに最適なデータ構造を見つけようとしています。文字列であるキーを使用してキー値ストアを実装しています。値は頻繁に追加され、通常は1〜2回しか検索されません。最初はstd::map、しかし、キーの追加と赤黒木のリバランスのオーバーヘッドが値を検索する時間の減少を覆い隠していたため、パフォーマンスが最適ではないことがわかりました。現在、変更された単一のリンクリストを使用しています。ac文字列（const char *）、バイト単位の長さ、および格納されている値を含む構造体を使用します。キーを使用して値を検索する場合は、リストを繰り返し処理してキーのサイズを比較します。キーが一致する場合は、memcmpを使用して文字列が同一かどうかを確認します。それらが同一である場合、私は値を返します。この方法を使用すると、の約10倍のパフォーマンスを達成できstd::mapます。ただし、効率を約2倍にする必要があります。この問題に対して、誰かがより良いタイプのデータ構造を推奨できますか？

4

4 に答える 4

3

std::vectorpush_back()ほとんどの場合、メモリの割り当ては必要ないため、リンクリストよりも反復処理が高速であり、反復処理も高速である必要があります。

于 2011-02-10T18:35:20.647 に答える
3

実際の問題についての知識がなければ、迅速な解決策を見つけるのは困難です。特に、データセットの大きさ、実際のデータはどこに保存されていますか（コンテナーまたは他の場所に保存されていますか？）。コンテナに対して他にどのような操作を実行する必要がありますか？コンテナから要素を削除する必要がありますか？

他の質問の1つへのコメントとして、キーをコピーする必要があると述べていますstd::unordered_map...キーがすでに別の場所に保存されている場合は、マップを使用することをお勧めしますが、文字列のコピーは避けてください。キーとしてポインターを使用し、結果を逆参照して操作するためのカスタムコンパレータを使用します。

// Assuming that the data is stored in std::string somewhere else
struct custom_compare {
   bool operator()( std::string* lhs, std::string* rhs ) const {
      return lhs!=rhs && (lhs->size() < rhs->size() || lhs->compare( *rhs ) < 0);
   }
};
std::map< std::string*, data, custom_compare > mymap;

実際の文字列の代わりにポインタを格納することにより、これはコピーを取り除きます。カスタムコンパレータは基本的にリストに実装したものと同じくらい高速であり、ツリーは内容のバランスを取り、O（log n）ルックアップを可能にします。セットのサイズに応じて（要素が多い場合）、これは線形探索よりも改善されますが、サイズが小さい場合は線形探索の方が優れています。

また、データの多様性によっては、線形探索を実行することもできますが、計算が高速ないくつかの基準に応じて探索空間を分割し、同時にセットを可能な限り均等に分割します。たとえば、線形検索を使用できますが、単一のリストを保持する代わりに、キーの長さに基づいて異なるリストを保持します。

基準が実際に文字列の内容（サイズではなく文字）に基づいている場合は、トライの定義を概算しています。すでにライブラリを実装しているライブラリを入手した場合、またはそのために必要な時間を費やしても構わないと思っている場合、トライは「サイズ」変数を次の数から変換するため、このタイプのルックアップでおそらく最速のコンテナの1つになります。文字列の長さに対する要素。

于 2011-02-10T19:24:26.713 に答える
2

あなたはそれをあなたのタグの1つとして持っています...なぜTrieを使わないのですか？挿入は迅速である必要があり、文字の重複によりメモリ使用量が減少する可能性があり、ルックアップは高速です。

于 2011-02-10T18:39:12.527 に答える
0

おそらくある種のハッシュテーブル？キーに適切なハッシュアルゴリズムを使用すると、検索時間が大幅に短縮されます。挿入時間は少し遅くなりますが、ハッシュ関数が優れていればそれほど大きくないことを願っています。

于 2011-02-10T18:30:56.250 に答える