どうして?どうして?Javaはソート後の配列を処理するのがソートされていないより速いですか?考えたことある?

まず「いいね」をクリックして、自分に少し考える時間を与えて、微信は「沈黙王二」を検索して、この顔があるのに才能に頼っているふりをしているプログラマーに注目します.本文GitHub github.com/itwangerはすでに収録されていて、中には私が心を込めてあなたのために準備した第一線の大工場の面接問題もあります.
今日の日曜日、大事なことがないので、早く目が覚めました.しばらく渡辺淳一の本を読んでいて、心がだんだん落ち着いてきた.気分が悪いとき、本は最高の薬のようだ.気持ちが落ち着いたら、もっと意味のあることをしなければなりません.技術サイトをぶらぶらして、勉強しなければなりません.
Stack Overflowは私が一番好きなサイトで、Chromeブラウザの最初のブックマークです.中には多くの経典の問題があり、その中のいくつかの答えは、私の心に深く分析されています.例えば、「なぜソートされた配列をソートされていない配列よりも速く処理するのか」ということです.
間違いなく、直感的な印象では、ソート後の配列はソートされていないよりも速く、理由も必要なく、「夏にアイスクリームを食べるのは爽やかで、冬にダウンジャケットを着るのは暖かい」と知っているようなものです.
しかし、「知っているから知っている」という態度で、なぜなのかを明らかにする必要があります.
Javaコードを見てみましょう.

/**
 * @author     ，        
 */
public class SortArrayFasterDemo {
    public static void main(String[] args) {
        //     
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c             data[c] = rnd.nextInt() % 256;
        }

        // !!!    ，       
        Arrays.sort(data);

        //   
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i 100000; ++i)
        {
            //   
            for (int c = 0; c             {
                if (data[c] >= 128) {
                    sum += data[c];
                }
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

このコードはとても簡単です.説明します.
指定した長さ(32768)の配列を宣言します.Random乱数オブジェクトを宣言します.シードは0です.rnd.nextInt() % 256は、0から256の絶対値、0を含む、256を含まない、負の数である可能性のある余剰数を生成します.余剰数を使用して配列を埋めます. Arrays.sort()を使用してソートします.
forループネストにより配列累積後の結果を計算し,System.nanoTime()により前後の時間差をナノ秒レベルに正確に計算した.
私の本機の環境はMac OSで、メモリは16 GBで、CPU Intel Core i 7、IDEはIntelliJ IDEAを使って、並べ替えた後と並べ替えていない後の結果は以下の通りです:
並べ替え後:2.81163398未並べ替え:9.41434346
時間差はやはり明らかですよね?ソートされていないとき、結果を待っているときは、いつ終わるのか心配になります.终わらないでしょう?
読者の皆さんはトーチの光を游んだことがありますか?非常に古典的な単機ゲームで、すべてのシーンに地図があり、地図には多くの分岐がありますが、次の関門に通じる分岐は1つしかありません.ブラシがない前に、地図はぼやけていて、プレイヤーはどの分岐が正しいか分かりません.
もし幸運にも正しい分岐点を走ったら、すぐに次の関門に着くことができます.そうでなければ、戻って、正しい分岐点を探すには、より多くの時間がかかりますが、同時により多くの経験と人気を得ることができます.
トーチの光を游んだ古いプレイヤーとして、ほとんどの地図を何度も磨いたことがあります.ブラシの回数が多くなり、地図の差が少なくて私の頭に刻まれました.最初は地図がぼやけていても、経験と直感で最も正しい分支を見つけることができて、折り返し走る时間を節約することができます.
読者の皆さんは、上のコードにifブランチであるif (data[c] >= 128)があることに注意してください.つまり、配列の値が128以上であれば、それを累積します.そうしないとスキップします.
このコードのブランチはトーチの光の中の地図のブランチのようなもので、プロセッサが私のように事前に判断できれば、累積の操作はずっと速くなりますよね?
プロセッサの内部構造は分かりませんが、それは私の脳と似ているはずです.if分岐に遭遇したときも止まる必要があります.いったい続けるかどうか当ててみてください.毎回当ててみると、明らかに折り返して走る必要はありません.時間を無駄にします.
これが伝説の分岐予測です!
地図上のルートを正確に予測するには、何度も図をブラシする必要があります.プロセッサは判断の精度を高めるためにソートする必要があります.
コンピュータはここ数年発展して、すでに非常に聡明になって、条件に対する予測は通常90%以上の命中率に達することができます.しかし、ブランチが予測不可能であれば、プロセッサもどうしようもないのではないでしょうか.
ソート後にかかる時間が少なく、ソートされていない時間が多く、元凶はif文にあります.

if (data[c] >= 128) {
    sum += data[c];
}

配列内の値は均一に分布している(-255から255の間)、どのように均一に分布しているかについては、とにかくRandomクラスが責任を負います.
説明を簡単にするために、負の数の部分をしばらく無視して、0から255まで話します.
ソートされたデータを見てみましょう.

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT

Nは128未満でif条件でフィルタリングされる.Tはsumに累積する値である.
並べ替えられていないデータを見てみましょう.

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   

全く予測できない.
比較すると、ソート後のデータは分岐予測に遭遇したときに50%のデータを簡単にフィルタリングできることがわかりますよね?法則に従うことができる.
並べ替えたくないとか、時間を節約したいとか言ったら、仕方がありませんか.
もしあなたが直接私に聞いたら、私はきっと仕方がなくて、両手を広げて、仕方がない顔をしています.しかし、Stack Overflowは神の視点で答えを出した.
次のようにします.

if (data[c] >= 128) {
    sum += data[c];
}

次のように変更します.

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

ビット演算によりif分岐を除去した(完全に同等ではない)が,計算後のsum結果は同じであることをテストした.

/**
 * @author     ，        
 */
public class SortArrayFasterDemo {
    public static void main(String[] args) {
        //     
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random();
        for (int c = 0; c             data[c] = rnd.nextInt() % 256;
        }

        //   
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i 100000; ++i)
        {
            //   
            for (int c = 0; c             {
                if (data[c] >= 128) {
                    sum += data[c];
                }
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);

        //   
        long start1 = System.nanoTime();
        long sum1 = 0;

        for (int i = 0; i 100000; ++i)
        {
            //   
            for (int c = 0; c             {
                int t = (data[c] - 128) >> 31;
                sum1 += ~t & data[c];
            }
        }

        System.out.println((System.nanoTime() - start1) / 1000000000.0);
        System.out.println("sum1 = " + sum1);
    }
}

出力結果は次のとおりです.

8.734795196
sum = 156871800000
1.596423307
sum1 = 156871800000

配列が累積された結果は同じですが、時間的には非常に悪く、配列がソートされていない場合、分岐予測に時間がかかっていることを示しています.
最後に、大神級のプログラマーはさすが大神級のプログラマーで、ビット演算を知っているプログラマーはキックアスだと言わざるを得ない.
大学に通っている読者の友达は、「コンピュータオペレーティングシステムの原理」という最下層の本をもっと読むことをお勧めします.優秀なプログラマーになるのに役立ちます.结局大学の期间、学习の时间は十分で、社会の圧力は小さくて、心をやり遂げることができて、顽张ります!
私は沈黙の王二で、顔があるのに才能に頼っているふりをするプログラマーです.注目すれば学習効率が向上します.三連を忘れないでください.いいね、コレクション、伝言、私は選ばないで、オリーはあげます.
注:文章に何か問題があれば、容赦なく指摘してください.
もし文章があなたに少し役に立つと思ったら、微信が「沈黙王二」を検索するのを歓迎します.本論文ではGitHub github.com/itwangerが収録されていますので、starを歓迎します.