C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C ++プログラムでソートされていない配列よりもソートされた配列を処理する方が速いのはなぜですか？

C ++では、分岐予測のため、ソートされていない配列よりもソートされた配列を処理する方が高速です。コンピュータアーキテクチャでは、分岐予測は、プログラムの命令フローで条件付き分岐（ジャンプ）が実行される可能性が高いかどうかを判断します。

例を見てみましょう：

if(arr[i] > 50) {
   Do some operation B
} else {
   Do some operation A
}

このコードを100個の要素に対して、並べ替えられていない順序と並べ替えられた順序で実行すると、次のようなことが起こります。

ソートされた配列の場合：

1,2,3,4,5,……50,51………100
A,A,A,A,A A,B B
It will load the correct branch in pipeline and correct sequence A,A,A, A,A,A,A,A A,B B

ソートされていないアレイの場合：

5,51,6,90,4,49,60…
A,B,A,B,A,A,A,B

ここでは、分岐予測は重要な役割を果たしません。 AとBの間の正しい動作を予測することは非常に困難です。


  1. C++で配列のビットノイズをチェックするプログラム

    N個の整数の配列arr[N]が与えられた場合、タスクは、与えられた配列がバイトニックであるかどうかをチェックすることです。指定されたアレイがバイトニックである場合は、「はい、バイトニックアレイです」と出力します。そうでない場合は、「いいえ、バイトニックアレイではありません」と出力します。 Bitonicアレイとは、アレイが最初に厳密に昇順で、次に厳密に降順である場合です。 この配列のように、arr [] ={1、2、3、4、2、-1、-5}はバイトニック配列です。これは、4までは厳密に昇順であり、4以降は厳密に降順であるためです。 入力 arr[] = {1, 3, 5, 4,

  2. C ++でソートされていない配列よりもソートされた配列を処理する方が速いのはなぜですか？

    C ++では、分岐予測のため、ソートされていない配列よりもソートされた配列を処理する方が高速です。コンピュータアーキテクチャでは、分岐予測は、プログラムの命令フローで条件付き分岐（ジャンプ）が実行される可能性が高いかどうかを判断します。 例を見てみましょう- if(arr[i] > 50) {    Do some operation B } else {    Do some operation A } このコードを100個の要素に対してソートされていない順序とソートされた順序で実行すると、以下のことが起こります- ソートされた配列の場合- 1