2

一般的な文字列を格納して検索できる必要があります。文字列の内容についてはよくわかりません.2/3より少し多いのは人間の言葉で、残りはUUIDまたは数字/文字の組み合わせに近いものです. 特定のグループ化は一定であることを知っています（つまり、人間の言葉が含まれている場合はすべて人間の言葉になり、UUID が含まれている場合はすべてのコンテンツが UUID になります）。

最高の平均検索率を得るために、このデータをマップまたはハッシュマップのどちらに配置するかを決定する必要があります。入力形式についてほとんど知らない場合、文字列の適切で効率的なハッシュを作成できるとは思わないため、O(log n) ランタイムでマップすると言う傾向があります。どちらが良いかについての考えはありますか？

編集：重要な側面を1つ忘れていました。文字列の長さがわからないので、長い文字列ではメモリ使用量が大きくなりすぎるのではないかと心配しています。ハッシュ方式を使用した場合、X 文字の後にハッシュが文字単位でハッシュされないような処理を行って、メモリの消費量が膨大になるのを回避します。

私が本当に欲しいのは、バケットの（ログN）検索を提供できるように、順序付けられた方法でソートされた「バケット」に複数の値を保持するハッシュマップの実装です。しかし、それはstardrd C++には存在しないと思いますし、ゼロから書く価値はありません。

pps。データはほぼ静的です。たまにリストに追加する必要がありますが、それはまれであり、書き込み時間が遅いことを喜んで受け入れます。私は検索時間だけを気にします。

4

4 に答える 4

4

おすすめを1つにするのは難しいです。これは、いくつかのトレードオフ (反復のタイプ、メモリとルックアップ) に依存します。全体を通して、C++11 コンパイラ (または同等の Boost または TR1 ライブラリ) を使用できると想定しています。

挿入/検索時間が最も重要である場合、私は間違いなく(std::unordered_setリファレンスを参照) をstd::hash<std::string>(リファレンスを参照) とともに使用します。挿入と検索の両方がO(1)平均 (償却定数) です。もしも

順序付けられていないハッシュ コンテナーでは、並べ替えられた順序で反復を実行できないことに注意してください。したがって、並べ替えられた反復が必要な場合は、順序付けられたコンテナーを使用できますstd::set<std::string>が、支払う代償はO(log N)ルックアップ/挿入です。

メモリの制約は分析がより困難です。まず、順序付けられたコンテナーは、順序付けられた反復を可能にするツリー構造を維持するために、要素あたり約3 ワードのオーバーヘッドstd::setを必要とします。ただし、順序付けされていないハッシュ コンテナーには、ハッシュ コンテナーが全負荷ファクターで非常に不十分に動作するため、予備の容量があります。std::map

#include <iostream>
#include <functional>
#include <string>
#include <unordered_set> // or <set> for ordered lookup

int main()
{
    // or std::set<std::string> for ordered lookup
    std::unordered_set<std::string> dictionary; 

    std::string str = "Meet the new boss...";
    dictionary.insert(str);
    auto it = dictionary.find(str);

    std::cout << *it << '\n';
}

Ideoneに出力します。Valueと一緒に保存したい場合は、同じハッシュ関数で, またはをstd::string使用できます。std::unordered_map<std::string, Value>std::map<std::string, Value>

結論: 上記のトレードオフに応じて、アプリケーションに最適なものを測定するのが最善です。

于 2012-08-14T18:04:02.993 に答える
3

std::set、std::map、std::unordered_set、および std::unordered_map とは別に、Triesを調べて、それらがより適しているかどうかを確認することも検討します。

http://en.wikipedia.org/wiki/Trie

于 2012-08-14T18:07:59.110 に答える
0

ベンチマークをご覧になることをお勧めします: http://www.dotnetperls.com/sorteddictionary 衝突にもかかわらず、実際のアプリケーションに表示されます Dictionary は SortedDictionary よりも優れています。

于 2012-08-14T18:16:26.967 に答える