いくつかのオブジェクトのフィールドによって、オブジェクトの巨大なメモリ内配列で高速検索を実行するタスクがあります。いくつかの条件を満たすオブジェクトのサブセットを選択する必要があります。
基準は、浮動小数点値またはそのような値の範囲として指定できます（例2.5..10）。
問題は、検索対象のfloatプロパティが完全に均一に分散されていないことです。10-20たとえば、値の範囲を持つオブジェクトがいくつか含まれ、値を持つオブジェクトがさらに100万個、値を持つオブジェクトがさらに100万個含まれる可能性が0-1あります100-150。
では、これらのオブジェクトを効果的に検索するためのインデックスを作成することは、どのように可能でしょうか。コードサンプルは大歓迎です。
インメモリ配列が順序付けられている場合、バイナリ検索が私の最初の試みになります。ウィキペディアのエントリにもサンプルコードがあります。
範囲の要件については、範囲ツリーを試すことができます。
ルックアップのみを実行している場合は、単一のソートとそれに続く複数のバイナリ検索が適しています。
究極のルックアップ速度などが必要な場合は、完璧なハッシュアルゴリズムを試すこともできます。
ルックアップ以上のものが必要な場合は、treapsと赤黒木をチェックしてください。前者は平均して高速ですが、後者は動作時間の変動が少ないまともなパフォーマーです。
値の分布がインデックスの作成と何の関係があるのかわかりません（正確な重複を除いて）。データはメモリに収まるため、すべてのフィールドを元の位置で抽出して並べ替え、@MattiLyraで提案されているようにバイナリ検索を使用します。
私たちは何かが欠けていますか？