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

パイプラインに正しいブランチと正しいシーケンスをロードします

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 ++プログラムでソートされていない配列よりもソートされた配列を処理する方が速いのはなぜですか？

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

  2. ソートされた配列を実装するC++プログラム

    並べ替えられた配列は、各要素が数値、アルファベット順などの順序で並べ替えられた配列です。バブルの並べ替え、挿入の並べ替え、選択の並べ替え、マージの並べ替え、クイック並べ替えなど、数値の配列を並べ替えるアルゴリズムは多数あります。ヒープソートなど。選択ソートを使用した配列のソートの詳細については、以下を参照してください。 選択ソートは、ソートされた配列を生成するソート方法です。これは、配列内の最小の要素を繰り返し見つけて、ソートされていない部分の先頭にある要素と交換することによって行われます。 選択ソートを使用してソートされた配列を実装するプログラムは次のとおりです。 例 #include&