2

以下の配列は、小さなサイズ (5000 未満) の重複 (一意の正の整数を含む) なしで並べ替えられ、交差 (以下を参照) は何十億回も呼び出されるため、マイクロ最適化は重要です。この記事Cでは、言語で以下のコードを高速化する方法をうまく説明しています。

int i = 0, j = 0, c = 0, la = a.length, lb = b.length;
intersection = new int[Math.min(la, lb)];
while (i < la && j < lb) {
    if (a[i] < b[j]) i++;
    else if (a[i] > b[j]) j++;
    else {
        intersection[c] = a[i];
        i++; j++; c++;
    }
}
int[] intersectionZip = new int[c];
System.arraycopy(intersection, 0, intersectionZip, 0, c);

Java では、これらの低レベルの命令を呼び出すことは不可能だと思います。しかし、彼らは「ブランチレス実装を使用してこのアプローチを改善することが可能です」と述べています。どうやってそれをするでしょうか？を使用していswitchますか？それともa[i] < b[j]、整数オペランドでの二項演算との置換a[i] > b[j]またはa[i] == b[i]比較でしょうか?

二分探索アプローチ (複雑さを伴うO(la log(lb))) は、よりも でlaはないため、当てはまりません。ステートメントを変更する方法が興味深い。<<lbif

4

2 に答える 2

1

その Java コードのパフォーマンスを改善するためにできることはあまりないと思います。ただし、C バージョンと同じことを行っていないことに注意してください。C バージョンは、呼び出し元によって事前に割り当てられた配列に交差を配置しています。Java バージョンは、配列自体を割り当てます...そして、それが終了すると、より小さい配列に再割り当てしてコピーします。

Java のバージョンを変更して、入力配列に対して 2 つのパスを作成することができると思います。最初のパスでは、入力配列が必要な大きさを計算します...しかし、それが役立つか妨げになるかは、入力によって異なります。

他にも最適化できる特別なケースがあるかもしれません。たとえば、一方の配列に長い数字があり、もう一方の配列にはその範囲に何もない場合、「楽観的に」一度に複数の数字をスキップしようとすることができるかもしれません。つまり、増加iするかj、よりも大きな数で増加します1。

しかし、彼らは「ブランチレス実装を使用してこのアプローチを改善することが可能です」と述べています。どうやってそれをするでしょうか？スイッチを使用していますか？

Java スイッチ ... または条件式ではありません。どちらもネイティブ コードに変換するときに分岐が含まれるためです。

彼は次のようなことを指していると思います: ゼロ、負、正を 0、1、2 にマップするブランチレス コード

FWIW Javaでこの種のことをしようとするのは悪い考えです。問題は、このようなトリッキーなコード シーケンスのパフォーマンスが、プラットフォームごとに異なるハードウェア アーキテクチャ、命令セット、クロック カウントなどの詳細に依存することです。Java JIT コンパイラーのオプティマイザーは、コードを最適化するのに非常に優れた仕事をすることができます...しかし、トリッキーなシーケンスを含めると:

  1. それらがネイティブ コードにどのように変換されるかは、まったく明白でも予測可能でもありません。
  2. このトリッキーさが、JIT コンパイラーが実行できる有用な最適化を実際に阻害していることに気付くかもしれません。

そうは言っても、Javaの将来のリリースにスーパーオプティマイザーが含まれる可能性はあります...上記のリンクされたQ&Aで言及されているものに沿って...ブランチレスシーケンスを自動的に生成できるようになります。ただし、超最適化の実行には非常にコストがかかることに注意してください。

于 2013-05-09T11:53:29.257 に答える
0

多分? :演算子を使用して：

  (a[i] < b[j]) ? i++ : ((a[i] > b[j]) ? j++ : ....
于 2013-05-09T11:46:56.217 に答える