Java中為什么處理排序數(shù)組比未排序數(shù)組快-創(chuàng)新互聯(lián)

這篇文章主要介紹了Java中為什么處理排序數(shù)組比未排序數(shù)組快的相關(guān)知識，內(nèi)容詳細(xì)易懂，操作簡單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇Java中為什么處理排序數(shù)組比未排序數(shù)組快文章都會有所收獲，下面我們一起來看看吧。

和平網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、自適應(yīng)網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營維護(hù)。創(chuàng)新互聯(lián)從2013年創(chuàng)立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

首先來看一下問題，下面是很簡單的一段代碼，隨機(jī)生成一些數(shù)字，對其中大于 128 的元素求和，記錄并打印求和所用時(shí)間。

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

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

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

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

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

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

我的運(yùn)行結(jié)果：分別在對數(shù)組排序和不排序的前提下測試，在不排序時(shí)所用的時(shí)間比先排好序所用時(shí)間平均要多 10 ms。這不是巧合，而是必然的結(jié)果。

問題就出在那個(gè)if判斷上面，在舊文順序、條件、循環(huán)語句的底層解釋中其實(shí)已經(jīng)提到了造成這種結(jié)果的原因，只是舊文中沒有拿出具體的例子來說明。

為了把這個(gè)問題搞明白，需要先對流水線有一定的了解。計(jì)算機(jī)是指令流驅(qū)動的，執(zhí)行的是一個(gè)一個(gè)的指令，而執(zhí)行一條指令，又要經(jīng)過取指、譯碼、執(zhí)行、訪存、寫回、更新六個(gè)階段（不同的劃分方式所包含的階段不一樣）。

六個(gè)階段使用的硬件基本是不一樣的，如果一條指令執(zhí)行完再去執(zhí)行另一條指令，那么在這段時(shí)間里會有很多硬件處于空閑狀態(tài)，要使計(jì)算機(jī)的速度變快，那么就不能讓硬件停下來，所以有了流水線技術(shù)。

流水線技術(shù)通過將指令重疊來實(shí)現(xiàn)幾條指令并行處理，下圖表示的是三階段指令時(shí)序，即把一個(gè)指令分為三個(gè)階段。在第一條指令的 B 階段，A 階段相關(guān)的硬件是空閑的，于是可以將第二條指令的 A 階段提前操作。

很明顯，這種設(shè)計(jì)大幅提高了指令運(yùn)行的效率，聰明的你可能發(fā)現(xiàn)問題了，要是不知道下一條指令是什么怎么辦，那提前的階段也就白干了，那樣流水線不就失效了？沒錯(cuò)，這就是導(dǎo)致開篇問題的原因。

讓流水線出問題的情況有三種：1、數(shù)據(jù)相關(guān)，后一條指令需要用到前一條指令的運(yùn)算結(jié)果；2、控制相關(guān)，比如無條件跳轉(zhuǎn)，跳轉(zhuǎn)的地址需要在譯碼階段才能知道，所以跳轉(zhuǎn)之后已經(jīng)被取出的指令流水就需要清空；3、結(jié)構(gòu)相關(guān)，由于一些指令需要的時(shí)鐘周期長（比如浮點(diǎn)運(yùn)算等），長時(shí)間占用硬件，導(dǎo)致之后的指令無法進(jìn)入譯碼等階段，即它們在爭用同一套硬件。

代碼中的if (data[c] >= 128)翻譯成機(jī)器語言就是跳轉(zhuǎn)指令，處理器事先并不知道要跳轉(zhuǎn)到哪個(gè)分支，那難道就等知道了才開始下一條指令的取指工作嗎？處理器選擇了假裝知道會跳轉(zhuǎn)到哪個(gè)分支（不是謙虛，是真的假裝知道），如果猜中了是運(yùn)氣好，而沒有猜中那就浪費(fèi)一點(diǎn)時(shí)間重新來干。

沒有排序的數(shù)組，元素是隨機(jī)排列的，每次data[c] >= 128的結(jié)果也是隨機(jī)的，前面的經(jīng)驗(yàn)就不可參考，所以下一次執(zhí)行到這里理論上還是會有 50% 的可能會猜錯(cuò)，猜錯(cuò)了肯定就需要花時(shí)間來修改犯下的錯(cuò)誤，自然就會浪費(fèi)更多的時(shí)間。

對于排好序的數(shù)組，開始幾次也需要靠猜，但是猜著猜著發(fā)現(xiàn)有規(guī)律啊，每次都是往同一個(gè)分支跳轉(zhuǎn)，所以以后基本上每次都能猜中，當(dāng)遍歷到與 128 分界的地方，才會出現(xiàn)猜不中的情況，但是猜幾次之后，發(fā)現(xiàn)這又有規(guī)律啊，每次都是朝著另外一個(gè)相同分支走的。

雖然都會猜錯(cuò)，但是在排好序的情況下猜錯(cuò)的幾率遠(yuǎn)遠(yuǎn)小于未排序時(shí)的幾率，最終呈現(xiàn)的結(jié)果就是處理排序數(shù)組比未排序數(shù)組快，其原因就是流水線發(fā)生了大量的控制相關(guān)現(xiàn)象，下面通俗一點(diǎn)，加深一下理解。

遠(yuǎn)在他方心儀多年的姑娘突然告訴你，其實(shí)她也喜歡你，激動的你三天三夜睡不著覺，決定開車前往她的城市，要和她待在一起，但是要去的路上有很多很多岔路，你只能使用的某某地圖導(dǎo)航，作為老司機(jī)并且懷著立馬要見到愛人心情的你，開車超快，什么樣罰單都不在乎了。

地圖定位已經(jīng)跟不上你的速度了，為了盡快到達(dá)，遇到岔路你都是隨機(jī)選一條路前進(jìn)，遺憾的是，自己的選擇不一定對（我們假設(shè)高速可以回退），走錯(cuò)路了就要重新回到分岔點(diǎn)，這就對應(yīng)著未排序的情況。

現(xiàn)在岔路是有規(guī)律的，告訴你開始一直朝著一邊走，到某個(gè)地點(diǎn)后會一直朝著另一邊走，你只需要花點(diǎn)時(shí)間去探索一下開始朝左邊還是右邊，到了中間哪個(gè)地點(diǎn)會改變方向就可以了，相比之下就能節(jié)省不少時(shí)間了，盡快見到自己的愛人，這對應(yīng)著排好序的情況。

關(guān)于“Java中為什么處理排序數(shù)組比未排序數(shù)組快”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“Java中為什么處理排序數(shù)組比未排序數(shù)組快”知識都有一定的了解，大家如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道。

分享標(biāo)題：Java中為什么處理排序數(shù)組比未排序數(shù)組快-創(chuàng)新互聯(lián)
標(biāo)題路徑：http://muchs.cn/article36/deehsg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計(jì)公司、自適應(yīng)網(wǎng)站、網(wǎng)站內(nèi)鏈、微信公眾號、企業(yè)建站、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)