在 C++ 中，二维数组的整体操作是否比行为类似于二维数组的一维数组慢？

Question

我只是想问一下在处理二维数组时，在性能和效率方面哪个更好实现，以及可能的代码复杂性，因为我们需要为我们的小组项目制作一个矩阵库。

我有下面的代码（我认为这可能不是一个很好的例子，而且我的 ram 也有限，这就是原因）

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

int main(){

    auto start = high_resolution_clock::now();
    auto arr2d = new unsigned long long int[10000ul][10000ul];

    int cnt = 1;
    for(unsigned long long int i=0; i<10000ul; ++i){
        for(unsigned long long int j=0; j<10000ul; ++j){
            arr2d[i][j] = cnt;
            cnt++;
        }
    }
    auto stop = high_resolution_clock::now();   
    auto duration = duration_cast<microseconds>(stop-start);
    cout<<duration.count()<<endl;

    auto start1 = high_resolution_clock::now();
    auto arr1d = new unsigned long long int[100000000ull];

    int cnt1 = 1;
    for(unsigned long long int i=0; i<10000ul; ++i){
        for(unsigned long long int j=0; j<10000ul; ++j){
            arr1d[(i*10000ul)+j] = cnt1;
            cnt1++;
        }
    }
    auto stop1 = high_resolution_clock::now();  

    auto duration1 = duration_cast<microseconds>(stop1-start1);
    cout<<duration1.count()<<endl;

    return 0;
}

这表明性能并没有太大的差异？

谁能给我们建议并解释我们应该走哪条路线？

Answer 1

在您的特定情况下，您的两个 for 循环实际上都是按顺序访问内存，即使在二维数组的情况下（由于二维数组的内存布局），所以没有真正的区别.要查看不同的执行速度，请尝试以下模式：

for(unsigned long long int i=0; i<10000ull; ++i){
    for(unsigned long long int j=0; j<10000ull; ++j){
        arr2d[j][i] = 1-1*3+3/4;  // note i and j are switched.
    }
}

当您顺序访问内存时，CPU 足够聪明，可以将内存内容预取到 CPU 的 L1 和 L2 缓存中。但在修改后的版本中，对内存的访问不是顺序的——每次都向前跳转 10000*8 个字节，CPU 将无法预取那么远，因此代码将运行较慢。

在您的代码中要注意的另一件事是，表达式 1-1*3+3/4 实际上将由编译器预先计算，因为它仅包含常量，因此您的代码将变成仅一系列赋值。

Answer 2

这两种方法的性能预计是相同的。

二维数组，如unsigned long long int[10000ul][10000ul]，占用一个连续的内存块，与元素数量相同的一维数组，如unsigned long long int[100000000ull]。这里没有区别。

着眼于访问数组中的元素，让我们假设 sizeof(unsigned long long) 是 8 来简化表示法。当您访问 arr2d[i][j] 时，编译器会将 (i*10000ul + j)*8 添加到 arr2d 的起始地址以找到该元素。当您访问 arr1d[(i*10000ul)+j] 时，编译器将 ((i*10000ul)+j)*8 添加到 arr1d 的起始地址以找到该元素。这里没有区别。

这两种方法的底层实现没有区别，所以你应该使用更方便的。 但是， 在利用此答案之前，请确保您使用的是二维数组（如 T [M][N]），而不是指向数组的指针数组（如 T* [M] ).使用一个的符号通常与另一个的符号没有区别，但指针数组使用更多内存并且不保证所有内容都是连续的。这是否会显着影响代码的性能取决于执行了哪些操作。（虽然问题确实显示了一个真正的二维数组，但未来的读者可能会从这个警告中受益。）

说到方便，您可能会发现 std::vector 比自己管理内存更方便。但是，如果您选择使用矢量，您可能希望坚持使用 1D 方法。 std::vector< std::vector<unsigned long long int>> 中的嵌套向量类似于指针数组，因此您失去了单个连续内存块的好处。

在 C++ 中，二维数组的整体操作是否比行为类似于二维数组的一维数组慢？

In C++, is a 2D array slower in overall operations than a 1D array that behaves like a 2D array?

c++

arrays

matrix

2d