爲什麼這兩個多維數組的實現之間會有這麼大的執行時間差？

多維數組需要大量的時間來訪問數組。爲了提高緩存和訪問速度，建議將索引從小到大，即聲明rmq數組，如rmq[11][11][1002][1002]而不是rmq[1002][1002][11][11]。

我試了一個代碼來測試相同的。在代碼1：

int pre_compute[18][100001]; //global variable 

int main(){ 
    /*some precomputations on pre_compute array 
    of the order of size of the array*/ 

    /*Run 10^8 queries on pre_compute array, 
    O(1) per query.*/ 
}

代碼2：

int pre_compute[100001][18]; //global variable 

int main(){ 
    /*exact same precomputations on pre_compute array as done in Code 1 
    of the order of size of the array*/ 

    /*Run 10^8 queries on pre_compute array, 
    O(1) per query.*/ 
}

這兩個碼相同，除了陣列的分佈相同。這兩個代碼仍然有很大的執行時間差異。第一個代碼在我的電腦上的平均值爲0.40 secs，而其他代碼的平均值爲1.42 secs。

什麼可能是數組的兩個實現之間執行時間差這麼大的可能原因？

來源

2016-06-21 Sahil Arora

這可能有所幫助：http://stackoverflow.com/questions/16699247/what-is-cache-friendly-code，http://stackoverflow.com/questions/9936132/why-does-the-order -of-the-loops-affect-performance-when-iterating-over-a-2d-arrail – vu1p3n0x

@ vu1p3n0x後者是非常正確的問題，並且描述了在不方便省略的代碼中發生的事情實際使用聲明的數組。不錯的工作。 – WhozCraig

請問下次提供[MCVE]，或者如果您不同意重複回答您的問題，請在此提問。 –

這正是行 - 主和列 - 主要有序矩陣之間的差異。

的差異上Wikipedia解釋：

在行優先順序，所述陣列的行的連續元素是在存儲器中連續;按列主要順序，列的連續元素是連續的。

C和C++是行優先的，因此它們可以利用緩存由於空間局部性的行。這解釋了加速的急劇增加。從技術上講，如果要節省大量時間，最好將多維數組表示爲一維數組。 :)

來源

2016-06-21 16:20:35 erip

由於Fortran是Column Major訂單，移植Fortran-> C而不處理問題會導致性能問題。 – EvilTeach

@EvilTeach是的 - 絕對的噩夢。 – erip

將多維數組表示爲1d數組並不會真正改變任何內容，或者如果您的訪問模式爲主行，則不會節省時間。如果您將訪問模式從主專欄更改爲主專欄，或者您使用專欄專欄訪問，並使用帶索引計算的1d表示來實現專欄主存儲訂單，則可能會提高性能。 –

爲什麼這兩個多維數組的實現之間會有這麼大的執行時間差？

回答

相關問題