[[354803]]

 在我們的觀念當中，數(shù)組成員訪問的時間復雜度是O(1)，每個成員都可以一次定位，因此訪問時間應該是一樣的。

那如果我說，現(xiàn)在有一個一千萬元素的數(shù)組，那么訪問第一個元素與訪問最后一樣元素的時間是一樣的嗎?這個時候你會不會有所猶豫呢?

實際動手驗證

實踐是檢驗真理的唯一手段。空想沒用，我們動手實際測試一下。我們實現(xiàn)如下所示的代碼，在該代碼中我們創(chuàng)建一個全局的數(shù)組，數(shù)組的大小是一千萬個元素。然后分別對第一個元素和最后一個元素賦值，并在賦值前后記錄時間。

#define BUF_SIZE 10000000 //一千萬個元素 
 
int test_array[BUF_SIZE] = {}; 
 
int main( int argc, char* argv[] ) 
 
{ 
 
long time1; 
 
long time2; 
 
time1 = get_time(); //獲取時間，單位是納秒 
 
test_array[0] = 1; //訪問第一個元素 
 
time2 = get_time(); 
 
printf("access first item time: %ld\n", time2-time1); 
 
time1 = get_time(); 
 
test_array[BUF_SIZE-1] = 1; //訪問最后一個元素 
 
time2 = get_time(); 
 
printf("access last item time: %ld\n", time2- time1); 
 
return(0); 
 
} 

 完成代碼后，我們編譯運行一下。為了得到穩(wěn)定可靠的結(jié)果，我們多運行幾次。得到的結(jié)果如下所示。

從測試結(jié)果可以看出，訪問最后一個元素的性能明顯要比訪問第一個元素慢得多，有幾十倍的性能差異!

原因分析

要想搞清楚上述問題的原因，需要更加深入的理解計算機的原理，包括可執(zhí)行程序的內(nèi)存布局、操作系統(tǒng)進程的原理以及硬件層面的一些知識。接下來我們將逐步介紹相關(guān)內(nèi)容，抽絲剝繭，搞清楚為什么有如此明顯的性能差異。

我們知道用戶態(tài)的程序都是運行在虛擬空間的，每個程序都有自己4GB的虛擬空間。這個虛擬空間又稱為虛擬內(nèi)存。程序的虛擬內(nèi)存并不是即刻分配的，而是按需分配。也就是說，只有在用戶訪問該部分內(nèi)存的數(shù)據(jù)的時候，操作系統(tǒng)才會分配對應的物理內(nèi)存，然后將數(shù)據(jù)加載到內(nèi)存中。顯然，這種從硬盤再讀取數(shù)據(jù)的速度肯定要比直接訪問內(nèi)存慢的多。

 

現(xiàn)代的CPU為了提高系統(tǒng)采用了多級緩存和流水線技術(shù)。CPU會根據(jù)程序的指令運行情況將部分數(shù)據(jù)或者指令預加載到緩存當中，這樣接下來就可以直接從從緩存讀取數(shù)據(jù)了。

 

根據(jù)存儲性能金字塔的數(shù)據(jù)，從緩存讀取數(shù)據(jù)的性能是從內(nèi)存讀取性能的10倍以上。因此，如果代碼沒有規(guī)律，CPU無法預取數(shù)據(jù)和指令，那么程序的運行效率肯定會很低。

扯了這么遠，讓我們回到題目本身。由于這里數(shù)組比較大，因此當訪問第一個元素的時候，第一千萬個元素肯定是沒有被預讀的，之后訪問該數(shù)據(jù)大概率會發(fā)生缺頁中斷。所以，訪問第一個元素和最后一個元素在性能上是有差異的。

進一步的驗證

有了上面的分析，我們可以再做進一步的驗證。比如我們可以連續(xù)兩次訪問最后一個元素，看看兩者的區(qū)別。

int main( int argc, char* argv[] ) 
 
{ 
 
long time1; 
 
long time2; 
 
time1 = get_time(); 
 
test_array[0] = 1; 
 
time2 = get_time(); 
 
printf("access first item time: %ld\n", time2-time1); 
 
time1 = get_time(); 
 
test_array[BUF_SIZE-1] = 1; // 第一次訪問最后一個元素 
 
time2 = get_time(); 
 
printf("access last item time: %ld\n", time2- time1); 
 
time1 = get_time(); 
 
test_array[BUF_SIZE-1] = 1; // 第二次訪問最后一個元素 
 
time2 = get_time(); 
 
printf("access last item time: %ld\n", time2- time1); 
 
return(0); 
 
} 

 修改完代碼之后，執(zhí)行該程序。同樣，我們多次執(zhí)行該程序，確保結(jié)果穩(wěn)定。通過下面執(zhí)行結(jié)果可以看到，在第二次執(zhí)行是其時間與訪問第一個元素相當，已經(jīng)沒有那么明顯的差異了。

通過上面的學習，大家是不是覺得深入學習計算機原理層面的重要性了。關(guān)于更多計算機深層次的內(nèi)容，我們后面會繼續(xù)分享給大家。