为什么这两个多维数组的实现之间会有这么大的执行时间差？

多维数组需要大量的时间来访问数组。为了提高缓存和访问速度，建议将索引从小到大，即声明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表示来实现专栏主存储订单，则可能会提高性能。 –

为什么这两个多维数组的实现之间会有这么大的执行时间差？

回答

相关问题