我一直在网络(和 stackoverflow)上搜索有关一维数组(或 vector )是否比对应的二维数组更快的意见。一般的结论似乎是一维是最快的。然而，我自己写了一个简短的测试程序，结果表明二维是最好的。任何人都可以在我的测试中找到错误，或者至少解释为什么我得到这个结果吗？

我用它来存储矩阵，因此需要对具有行和列的一维数组进行索引。

#include <iostream>
#include <chrono>
#include <vector>

uint64_t timestamp()
{
    namespace sc = std::chrono;
    static auto start = sc::high_resolution_clock::now();
    return sc::duration_cast<sc::duration<uint64_t, std::micro>>(sc::high_resolution_clock::now() - start).count();
}

int main(int argc, char** argv)
{
    if (argc < 3)
        return 0;
    size_t size = atoi(argv[1]);
    size_t repeat = atoi(argv[2]);

    int** d2 = (int**)malloc(size*sizeof(int*));
    for (size_t i = 0; i < size; ++i)
        d2[i] = (int*)malloc(size*sizeof(int));

    int* d1 = (int*)malloc(size*size*sizeof(int));

    std::vector<std::vector<int> > d2v(size);
    for (auto& i : d2v)
        i.resize(size);

    std::vector<int> d1v(size*size);

    uint64_t start, end;
    timestamp();

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d2[r][c] = 0;
                else
                    d2[r][c] = d2[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D array\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d2[r][c] = 0;
                else
                    d2[r][c] = d2[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D array C\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d1[r + c*size] = 0;
                else
                    d1[r + c*size] = d1[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D array\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d1[r + c*size] = 0;
                else
                    d1[r + c*size] = d1[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D array C\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d2v[r][c] = 0;
                else
                    d2v[r][c] = d2v[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D vector\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d2v[r][c] = 0;
                else
                    d2v[r][c] = d2v[r-1][c] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "2D vector C\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t r = 0; r < size; ++r)
        {
            for (size_t c = 0; c < size; ++c)
            {
                if (r == 0)
                    d1v[r + c*size] = 0;
                else
                    d1v[r + c*size] = d1v[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D vector\t" << size << "\t" << end - start << std::endl;

    start = timestamp();
    for (size_t n = 0; n < repeat; ++n)
    {
        for (size_t c = 0; c < size; ++c)
        {
            for (size_t r = 0; r < size; ++r)
            {
                if (r == 0)
                    d1v[r + c*size] = 0;
                else
                    d1v[r + c*size] = d1v[r-1 + c*size] + 1;
            }
        }
    }
    end = timestamp();
    std::cout << "1D vector C\t" << size << "\t" << end - start << std::endl;

    return 0;
}

我得到以下输出:

user@user-debian64:~/matrix$ ./build/test/index_test 1000 100
2D array    1000    79593
2D array C  1000    326695
1D array    1000    440695
1D array C  1000    262251
2D vector   1000    73648
2D vector C 1000    418287
1D vector   1000    371433
1D vector C 1000    269355
user@user-debian64:~/matrix$ ./build/test/index_test 10000 1
2D array    10000   149748
2D array C  10000   3507346
1D array    10000   2754570
1D array C  10000   257997
2D vector   10000   92041
2D vector C 10000   3791745
1D vector   10000   3384403
1D vector C 10000   266811

最佳答案

问题的根源是两种方案你的存储顺序不一样。

您的二维结构按行优先存储。通过首先取消对行的引用，您可以得到一个可以直接按列索引的缓冲区。相邻的列位于相邻的内存位置。

您的一维结构按列优先存储。相邻列是内存中分开的 size 元素。

尝试两种迭代顺序几乎涵盖了所有效果。但剩下的就是数据依赖。引用D(r-1,c)，行主和列主的访问模式完全不同。

果然，将 1D 索引更改为 d1[r*size + c] 和 d1[(r-1)*size + c] 会产生以下时序:

2D array    1000    78099
2D array C  1000    878527
1D array    1000    19661
1D array C  1000    729280
2D vector   1000    61641
2D vector C 1000    741249
1D vector   1000    18348
1D vector C 1000    726231

所以，还是得解释一下。我要使用“循环携带的依赖性”。当您以列优先顺序迭代列优先一维数组时(好主意)，每个元素都取决于上一次迭代中计算的元素。这意味着循环不能完全流水线化，因为结果必须完全计算并写回缓存，然后才能再次读取以计算下一个元素。在行优先中，依赖现在是很久以前计算的元素，这意味着循环可以展开和流水线化。

关于c++ - 使用二维或一维，哪个最快？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26974406/