c++ - 高速文字列検索？

Question

文字列のベクトルがあり、ベクトルの各要素が5000語の特定のリストに存在するかどうかを確認する必要があります。2つのネストされたループのありふれた方法に加えて、C ++でこれを行うより速い方法はありますか？

Answer 1

文字列のリストをstd::setに入れる必要があります。これは、検索用に最適化されたデータ構造です。特定の要素がセットに含まれているかどうかを確認することは、すべてのエントリを繰り返すよりもはるかに高速な操作です。

すでにC++11を使用している場合は、ハッシュテーブルとして実装されているため、ルックアップがさらに高速なstd::unordered_setを使用することもできます。

これが学校/大学向けである場合：これらのデータ構造がどのように高速化されるかを説明する準備をしてください。あなたのインストラクターがあなたがそれらを使用した理由を説明するようにあなたに頼んだとき、「インターネット上の何人かの人が私に言った」はあなたにクラスブックのステッカーを獲得する可能性は低いです。

Answer 2

単語のリストをstd::unordered_setに入れることができます。次に、ベクトル内の各要素について、それがO（1）のunordered_setにあるかどうかをテストする必要があります。O（n）の複雑さが予想されます（コメントを見て、なぜそれだけが予想されるのかを確認してください）。

Answer 3

ベクトルを並べ替えると、1つの「ループ」（辞書も並べ替えられていると見なされます）でこれを解決できます。つまり、O（n）は並べ替えのコストを考慮していません。

Answer 4

つまり、文字列のベクトルがあり、各文字列には1つ以上の単語があり、辞書であるベクトルがあり、文字列のベクトルのどの単語も辞書にあるかどうかを判断する必要がありますか？文字列のベクトルは、各単語を確認する必要があるため、煩わしいものです。まず、新しいベクトルを作成し、各文字列を単語に分割し、各単語を新しいベクトルにプッシュします。次に、新しいベクトルを並べ替え、std::uniqueアルゴリズムを実行して重複を排除します。次に、辞書を並べ替えます。次に、両方の範囲を実行std::set_intersectionして結果を書き込みます。