どのデータ構造を使用すればいいですか

Question

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

Answer 1

実際の問題に関する知識がなくても、高速なソリューションを提供することは困難です。特に、あなたのデータセットはどれくらいの大きさですか、実際のデータはどこに保存されていますか（コンテナや他の場所に保存されていますか？）。コンテナで実行する必要がある他の操作は何ですか？コンテナから要素を削除する必要がありますか？

他の質問の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（ログn）ルックアップを可能にします。セットのサイズに応じて（多くの要素がある場合）、線形検索よりも改善されますが、サイズが小さいと線形検索が改善されます。

また、データの多様性に応じて、線形検索に従うこともできますが、計算時間が短縮され、同時にセットをできるだけ均等に分割するいくつかの基準に応じて検索スペースを分割することもできます。たとえば、線形検索を使用できますが、単一のリストを保持する代わりに、キーの長さに基づいて異なるリストを保持します。

基準が実際に文字列の内容（文字ではなく文字）に基づいている場合は、トライの定義に近似しています。すでに実装されているライブラリを取得した場合や、必要な時間を費やしたい場合は、このタイプのルックアップの最速のコンテナの1つになります。これは、 "size"変数を要素を文字列の長さに置き換えます。

Answer 2

おそらく何らかの種類のハッシュテーブルですか？あなたのキーに良いハッシュアルゴリズムを使用すると、検索時間が大幅に短縮されます。あなたの挿入時間は少し遅くなりますが、うまくいけば、あなたのハッシュ関数が良い場合は大したことではありません。

Answer 3

std::vectorは、リンクされたリストよりも高速で、でも高速です。ほとんどの場合、メモリの割り当ては不要です。

Answer 4

あなたはあなたのタグの1つとして持っています...なぜTrieを使用しないのですか？挿入が迅速でなければならず、文字の重複によりメモリ使用量が低下し、検索が高速になります。