C++ 性能小测 1 二维数组的遍历效率
遍历二维数组时,常规思路是使用一个嵌套循环。一方面,由于 CPU 使用了分支预测技术,因此通常将循环次数最多循环的放在最内层。另一方面,由于二维数组是按行存储的,因此遍历二维数组时,一般将列循环放在内层。但当数组的行数rowSize
大于数组的列数columnSize
时,这两条规律无法同时得到满足。下面通过一个小测试来判断这个时候哪种方式效率更高。
#include <iostream>
#include <ctime>
using namespace std;
const int rowSize = 50000;
const int columnSize = 2000;
const int testCount = 100;
int main()
{
//生成大型二维数组
int** arr = new int * [rowSize];
for (int i = 0; i < rowSize; i++)
{
arr[i] = new int[columnSize];
for (int j = 0; j < columnSize; j++)
{
arr[i][j] = rand() % 5;
}
}
//声明工具变量
double meanTime = 0;
long double sum = 0;
clock_t start, end, time;
//将列循环放在内层,进行多次测试
time = 0;
for (int k = 0; k < testCount; ++k)
{
sum = 0;
start = clock();
for (int i = 0; i < rowSize; ++i)
{
for (int j = 0; j < columnSize; ++j)
{
sum += arr[i][j];
}
}
end = clock();
sum = sum / (rowSize * columnSize);
time += end - start;
}
meanTime = (double) time / testCount / CLOCKS_PER_SEC;
cout << "列循环放在内层平均耗时" << meanTime << "秒,平均值为" << sum << endl;
//将列循环放在外层,进行多次测试
time = 0;
for (int k = 0; k < testCount; ++k)
{
sum = 0;
start = clock();
for (int j = 0; j < columnSize; ++j)
{
for (int i = 0; i < rowSize; ++i)
{
sum += arr[i][j];
}
}
end = clock();
sum = sum / (rowSize * columnSize);
time += end - start;
}
meanTime = (double) time / testCount / CLOCKS_PER_SEC;
cout << "列循环放在外层平均耗时" << meanTime << "秒,平均值为" << sum << endl;
//释放大型二维数组内存
for (int i = 0; i < rowSize; i++)
delete[] arr[i];
delete[] arr;
system("pause");
return 0;
}
测试输出如下:
列循环放在内层平均耗时0.42657秒,平均值为1.99975
列循环放在外层平均耗时1.35246秒,平均值为1.99975
请按任意键继续. . .
由此可得:使用嵌套循环遍历二维数组时,将列循环放在内层运行效率更高,即使所遍历的二维数组行数远大于列数。
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/tech/pnotes/282752.html