最速の方法<RのJava

Question

でint型のL、Rのための

Javaでint l,rための条件

l + 1 < r 

をチェックする最速の方法は何ですか？

lとrは一定ではなく、私はl <= rを知っています。この比較は、バイナリ検索の実装においてループwhileの停止条件です。私は別のテスト（大きな配列を検索する）とそれを使用するコードの両方で、私のコードをベンチマークしています。

私が探しているのは、現状よりも速いビット操作のようなものです。しかし、私は知らない。

Answer 1

私はこれがおそらく速いと思います。これは非常に単純なバイトコードに還元され、JIT（ジャストインタイムコンパイラ）はおそらくこれを非常に簡単なネイティブ実装に減らすでしょう。

（無関係：面白いところでJavaの使用が多いことが起こらない「クオンツdevの」を参照すること）

Answer 2

マイクロ最適化のこの種は、ほとんど常に悪い考えです。そのような小さなビットのパフォーマンスは、ホットスポットコンパイラがコードを最適化する方法と、周囲のコードと関係がある微妙なキャッシュ効果に完全に依存します。

Answer 3

これらのすべての人は何を言った。コンパイラはそれをあなたのために最適化しようとしています。あなたに見えて、正しく読んで行くように書いてください。

Answer 4

まあ基本的な比較どちらかでなければなりません：

、Lに1を追加rからrの

または

減算1に結果を比較し、L

に結果を比較し、現代のすべてハードウェアはどちらの操作（同じネイティブ・データ型の加減算も、副作用を完了させるためのサイクルとパイプラインの副作用の点で同じパフォーマンスを持ちます）で同じ未処理のパフォーマンスを持ちます。コンパイル時定数が知られているLまたはRの

いずれかならば、これは、任意の効果を有するであろう

唯一の方法です。例えば。

l + 1 < 5 
5 + 1 < r 

この場合、乏しい最適化コンパイラは、すべてののJavaコンパイラは、第二のケースは6 < r

他であることを見つけるために必要とされるl < 4

しかしに最初に変換することができ実現しないかもしれませんlとrのデータ型が異なる場合です。

の動作：

1. 浮動小数点加算/減算INT
   節
2. 積分加算/減算に、比較次いで二重との比較は、異なっていてもよいです。

このアプリケーションの重大な問題である可能性は、これらのいずれかのサイクルコストが、決定に関連する分岐予測ミスのパイプラインヒットと比較して小さいため、無視できると言えます。

また、適切なJITは、実行されたマイクロ最適化を上回る周囲のコードに関連して、あらゆる種類の最適化を行うことができます。

Answer 5

あなたの最善の策は、コードではなくJVMを調整することです。これがあなたのボトルネックだとすれば、

引数が-server -XX:+AggressiveOptsのjvmを起動してみてください。

Answer 6

変数lr1は常に(l - r + 1)になります。 lを増減するたびに、lr1と同じ操作を行います。 rについても同様です。

あなたのテストは(lr1 < 0)になり、lr1を修正する手順は必要以上に頻繁に実行されません。

私はちょっとばかげて微妙な最適化をしています。ほとんどの場合、これはペニーワイズ、ポンドフリッシュです。あなたが文字列を比較しているように、それは完全にそのテストを沼にします。

追加：バイナリ検索を行っているので、私はJon Bentleyのクールなバイナリ検索の展開について言及します。まず、1024のような2のべき乗までパッドテーブルAを、そして、あなたはこのような何か書く：

i = 0; 
if (X >= A[i+512]) i += 512; 
if (X >= A[i+256]) i += 256; 
    . . . 
if (X >= A[i+ 1]) i += 1; 

をし、最終的に(X == A[i])かどうかを調べます。あなたが唯一の終了後.equals（）を確認してか、あなたがパッドにそれをしたくない場合は、if文はwhileループの外であなたの平等のテストを動かすことについてどのように
if (i+512 < N && X >= A[i+512]) i += 512;

Answer 7

ようなものにしましょう。 btw私はl + 1かどうかをテストするためにどんなビットツイリングの方法も見つけられませんでした。<配列の長さが特定のサイズよりも小さいことがわかっている場合、インデックスに別のデータ型を使用するとどうなりますか？ char/short/byte？