タイトルが示すように、大きな定数配列 N に存在する M の要素を見つけようとしています。ほとんどの場合、M の要素は N に存在しないため、M に対して行われる検索の大部分は無駄です。時間。
M の本格的な検索を行う前にチェックするインデックスを作成する方法を探しています。私のようなプロジェクトは、M のすべての要素の最初の数バイトからビット配列を作成し、私が理解していることから、高速に検索するためのビット レベルの並列処理。これがどのように機能するのか完全にはわかりません。
では、不必要に M を検索する可能性を減らすために、どのようなトリックを使用できますか?
これはほとんど言語に依存しない質問ですが、できるだけ完全にするために、私は C++ を使用しています。
まさにこの場合に使用されるブルーム フィルターを考えているかもしれません。それらは偽陽性を与える可能性があり、その場合は実際のテーブルを検索する必要がありますが、ほとんどの場合、アイテムが保存されていない場合は最初からわかります.
通常、ハッシュ テーブルはストレージに最適なオプションです。ただし、キー スペースがターゲットの数よりもはるかに大きい場合は、かなりの数のハッシュ衝突が発生し、そこに格納されているターゲットが実際に探しているキーであるかどうかを確認する必要があります。キーの比較にコストがかかる場合は、すぐに要因になる可能性があります。
N の値をキーとしてハッシュテーブルを作成できます。
次に、hash[M[i]] にアクセスしようとします。値が返された場合、それは存在します。つまり、O(1) (衝突を無視します)。
N は静的であるため、N の完全ハッシュ関数を作成することを検討できます。これにより、検索がO(1) 時間保証されます。
アルゴリズムに関する CLR ブックには、これに関する章があり、上記の wiki ページには、役に立つと思われるリンクがあります。ただし、複雑すぎる可能性があり、有用な実装を見つけるのに苦労する可能性があります。. 実装についてはGperfを参照してください。
ただし、予想される O(1) で一般的に利用可能なハッシュ テーブルをいつでも使用できます。
そこにあることを知って取得したい追加情報を保存していると思いますか？それらをどのように保管していますか？
その場合、インデックスとしても機能するB ツリーが役立つ場合があります (業界標準のデータベースは通常、それらのバリアントを使用します) 。したがって、検索し、それが見つかった場合は、そのデータ/ポインターを取得します。これらの実装は Web で多数見つかります。