ソートされた巨大なダイレクトバッファをJavaで効率的に検索するにはどうすればよいですか？

Question

私はすでにソートされている整数（つまり1,1,3,3,3,3,7,7、...）を保持する直接バッファを持っています。ほとんどの値は複数回発生します。私が検索する価値の最初の位置を見つけたい。

1. バッファに直接作用する検索機能はありますか Javaに組み込まれていますか？ （何も見つかりませんでした）
2. もしそうでなければ、そのような機能を提供するまともなライブラリがありますか？そうでない場合

3. 、実装のために推薦するものを検索アルゴリズム、ことを考える：

   • 私は通常私のバッファに数百万のエントリを持つことになります
   • 速度は、それが返さなければなりません
   • 非常に重要です検索された番号が最初に出現する
   • 後で元のデータが必要になるため、データを変更しないでください。

EDIT：Arrays.binarySearch()を示唆全てのポスターのおかげで、しかしが、私の知る限り、直接バッファは、一般的に補助配列を持っていません。そのため、私はバッファで直接動作する実装を探していました。

また、各値は1000回まで発生する可能性があるため、着陸点を見つけた後の線形探索はそれほど効率的ではないかもしれません。 dasblinkenlightのコンパレータ提案はうまくいくかもしれません。

Answer 1

最善のアプローチは、バッファにBinary Searchの独自の実装をコーディングすることです。このアプローチは、ビューの作成、大規模な配列のコピーなどに伴う潜在的なパフォーマンスのヒットを慎重に避け、同時にコンパクトなままです。

リンクのコードサンプルは右端の点を返します。一番左の点を取得するには>をnums[guess] > check行の>=に置き換える必要があります。これにより、潜在的に高価な後方線形検索が不要になります。Comparatorを使用すると、intをIntegerオブジェクトにラップする必要があります。

Answer 2

私はバッファの組み込み機能についてはわかりません（Arrays.binarySearch(...)はバッファを配列に変換する必要があります）が、バッファはすでにソートされているためバイナリ検索が便利かもしれません。値を見つけたら、以前の値をチェックしてそのシーケンスの開始点を得ることができます。バイト配列は、配列の使用をintに変換できる場合

Answer 3

使用Binary search algorithm

ByteBuffer buffer = createByteBuffer(); 
IntBuffer intBuffer = buffer.asIntBuffer(); 

：

int [] array = intBuffer.array(); 
int index = java.util.Arrays.binarySearch(array,7); 

Answer 4

おそらく、自分のバイナリ検索を書く必要があります：チェックされた値と検索された値が等しい場合は、常に左に移動します。

xの代わりに効果的にx-εを検索します。アルゴリズムは常にlogn（またはlogn + 1）ステップを踏みますが、これは常に「失敗」しますが、x-εより大きい最初の要素のインデックスが与えられます。あなたがする必要があるのは、その要素がxであるかどうかを確認することだけです。そうであれば、一致するものを見つけました。そうでない場合は、バッファにxがありません。