一维数组还是二维数组，哪个更快？

Question

我需要表示一个二维场域 (坐标轴 x、y)，但我面临一个问题：我应该使用一维数组还是二维数组？

我可以想象，对于一维数组重新计算索引 (y + x*n) 可能比使用二维数组 (x, y) 更慢，但我能想象到一维数组可能在 CPU 缓存中..

我进行了一些谷歌搜索，但只找到了关于静态数组的页面（并指出一维数组和二维数组基本相同）。但我的数组必须是动态的。

那么，哪个更快，占用更少内存 (RAM)，动态一维数组还是动态二维数组？

1. 更快的是：
2. 更小的（RAM）是：

- graywolf

---

你的二维数组在内存中以一维数组的形式存储，因此无论何时调用 arr[x][y]，它都会在内部计算 (&arr[0][0])[x * dim + y]，所以不应该有任何区别。 - Alexandru Barbarosie

技术上讲是正确的，但 OP 可能指的是动态数组（即 T**），而不是真正的数组。因此，它不再是连续的。 - Konrad Rudolph

@KonradRudolph，那就不是一个二维数组了，对吗 :-) - juanchopanza

在通常的用法中，这绝对是一个二维数组。事实上，除非有人明确提到静态长度，否则我总是假设是动态数组，而且我几乎总是正确的。此外，原帖中明确提到他需要动态数组。 - Konrad Rudolph

一份简明的专家建议，适用于实际数值计算：http://www.fftw.org/doc/Dynamic-Arrays-in-C_002dThe-Wrong-Way.html#Dynamic-Arrays-in-C_002dThe-Wrong-Way。该文甚至提供了一种解决办法，使两种方式兼得。 - alfC

Answer 1

简而言之：你应该使用一维方法。

注意：当比较动态1D或2D存储模式的性能时，不能深入挖掘影响性能的细节，因为代码的性能取决于非常多的参数。如果可能，请进行分析。

1. 哪个更快？

对于密集矩阵，一维方法可能更快，因为它提供更好的内存局部性和更少的分配和释放开销。

2. 哪个更小？

动态1D消耗的内存比2D方法少。后者还需要更多的分配。

备注

我在下面列出了一个相当长的答案，并给出了几个原因，但我想先对你的假设进行一些评论。

我可以想象，重新计算1D数组的索引（y + x * n）可能比使用2D数组（x，y）更慢。

让我们比较这两个函数：

int get_2d (int **p, int r, int c) { return p[r][c]; }
int get_1d (int *p, int r, int c)  { return p[c + C*r]; }

对于那些函数，Visual Studio 2015 RC 生成的（非内联）汇编代码（启用了优化）如下：

?get_1d@@YAHPAHII@Z PROC
push    ebp
mov ebp, esp
mov eax, DWORD PTR _c$[ebp]
lea eax, DWORD PTR [eax+edx*4]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0

?get_2d@@YAHPAPAHII@Z PROC
push ebp
mov ebp, esp
mov ecx, DWORD PTR [ecx+edx*4]
mov eax, DWORD PTR _c$[ebp]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0

这里的区别是mov(2d)和lea(1d)。前者延迟为3个时钟周期，每个时钟周期最大吞吐量为2，而后者延迟为2个时钟周期，每个时钟周期最大吞吐量为3。（根据指令表- Agner Fog）由于差异很小，我认为从索引重新计算中产生的性能差异不会很大。我认为很难将此差异本身识别为任何程序中的瓶颈。

这就带我们来到下一个（更有趣的）问题：

...... 但我可以想象，1D可能在CPU缓存中......

没错，但2d也可能在CPU缓存中。请参见缺点：内存局部性，以了解为什么1d仍然更好。

长答案，或者说为什么动态二维数据存储（指针指针或向量向量）对于简单/小矩阵是“不好”的。

注意：这是关于动态数组/分配方案[malloc/new/vector等]的。静态二维数组是一块连续的内存块，因此不会受到我将在这里提出的缺点的影响。

问题

为了能够理解为什么动态数组或向量的动态数组很可能不是首选的数据存储模式，您需要了解此类结构的内存布局。

使用指针到指针语法的示例情况

int main (void)
{
    // allocate memory for 4x4 integers; quick & dirty
    int ** p = new int*[4];
    for (size_t i=0; i<4; ++i) p[i] = new int[4]; 

    // do some stuff here, using p[x][y] 

    // deallocate memory
    for (size_t i=0; i<4; ++i) delete[] p[i];
    delete[] p;
}

缺点

内存局部性

对于这个“矩阵”，你需要分配一个包含四个指针和四个整数块的内存。 所有的分配都没有关联， 因此可能会导致任意的内存位置。

下面的图像将让你了解内存的可能布局。

对于真实的二维情况：

• 紫色正方形是 p 本身占用的内存位置。
• 绿色正方形组成了由 p 指向的内存区域（4 x int*）。
• 4个连续蓝色正方形的每个 int* 所指向的区域是绿色区域所指向的区域之一

对于二维映射到一维情况：

• 绿色正方形是唯一必需的指针 int *
• 蓝色正方形组成了所有矩阵元素的内存区域（16 x int）。

这意味着（使用左侧布局）由于缓存等原因，性能可能比连续存储模式更差（如右侧所示）。

假设缓存行是“一次传输到缓存中的数据量”，并且想象一个程序按顺序访问整个矩阵的每个元素。

如果你有一个正确对齐的 4x4 矩阵，每个元素都是 32 位值，那么具有 64 字节缓存行（典型值）的处理器可以“一次性”读取所有数据（4*4*4 = 64 字节）。 如果开始处理时数据不在缓存中，你会遇到缓存未命中，数据将从主内存中提取。此次加载可以一次性获取整个矩阵，因为它是连续存储的（并且正确对齐）。 在处理该数据时，可能不会再发生缓存未命中。

在动态的“真正的二维”系统中，每行/列的位置都不相关，处理器需要逐个地加载每个内存位置。 即使只需要 64 字节，但是为了 4 个不相关的内存位置加载 4 个缓存行可能会实际传输 256 字节，并浪费 75% 的吞吐量带宽。 如果使用 2d 方案处理数据，你将再次（如果尚未缓存）在第一个元素上遇到缓存未命中。 但现在，仅有第一行/列会在第一次从主存储器的加载后在缓存中，因为所有其他行都位于内存中的其他位置，并且不相邻于第一行。 当你到达新的行/列时，又会出现缓存未命中，并且执行下一次从主内存的加载。

简而言之：使用一维方案时，二维模式有更高的缓存未命中几率，而数据局部性使得一维方案具有更好的性能潜力。

频繁的分配/释放：

需要尽多达N + 1（4 + 1 = 5）次分配（使用new、malloc、allocator::allocate或其他方法）才能创建所需的NxM（4×4）矩阵。同样数量的适当释放操作也必须应用。

因此，与单个分配方案相比，创建/复制这种矩阵的成本更高。

随着行数的增加，情况变得越来越糟。

内存消耗开销：

我将假设int为32位，指针为32位。（注意：系统依赖性。）

让我们记住：我们想要存储一个4×4的int矩阵，这意味着64字节。

对于一个用所述指针到指针方案存储的NxM矩阵，我们消耗了

- N*M*sizeof(int) [实际蓝色数据] + - N*sizeof(int*) [绿色指针] + - sizeof(int**) [紫色变量p]字节。

在本例中，这使得84字节，而使用std::vector>则会更糟。它将需要N * M * sizeof(int) + N * sizeof(vector) + sizeof(vector>)字节，即64字节的4 x 4 int的144字节。

此外，根据所使用的分配器，每个单独的分配可能会有另外16字节的内存开销。（一些“Infobytes”用于存储为了适当释放而分配的字节数。）

这意味着最坏的情况是：

N*(16+M*sizeof(int)) + 16+N*sizeof(int*) + sizeof(int**) = 4*(16+4*4) + 16+4*4 + 4 = 164字节！开销：156％。

随着矩阵大小的增长，开销的份额将减少，但仍将存在。

内存泄漏的风险。

一堆分配需要适当的异常处理，以避免内存泄漏，如果其中一个分配失败！您需要跟踪已分配的内存块，并在释放内存时不要忘记它们。

如果new耗尽内存且无法分配下一行（特别是在矩阵非常大时），则new会抛出std::bad_alloc异常。

例如：在上述的new/delete示例中，如果我们想要在bad_alloc异常情况下避免泄漏，则需要面对更多的代码。

  // allocate memory for 4x4 integers; quick & dirty
  size_t const N = 4;
  // we don't need try for this allocation
  // if it fails there is no leak
  int ** p = new int*[N];
  size_t allocs(0U);
  try 
  { // try block doing further allocations
    for (size_t i=0; i<N; ++i) 
    {
      p[i] = new int[4]; // allocate
      ++allocs; // advance counter if no exception occured
    }
  }
  catch (std::bad_alloc & be)
  { // if an exception occurs we need to free out memory
    for (size_t i=0; i<allocs; ++i) delete[] p[i]; // free all alloced p[i]s
    delete[] p; // free p
    throw; // rethrow bad_alloc
  }
  /*
     do some stuff here, using p[x][y] 
  */
  // deallocate memory accoding to the number of allocations
  for (size_t i=0; i<allocs; ++i) delete[] p[i];
  delete[] p;

摘要

在某些情况下，“真实的2D”内存布局是适用且有意义的（即如果每行的列数不是固定的），但是在最简单和常见的2D数据存储情况下，它们只会增加代码的复杂性并降低程序的性能和内存效率。

替代方案

您应该使用一个连续的内存块，并将行映射到该块上。

“C ++方式”可能是编写一个管理内存的类，同时考虑重要事项，如：

• 什么是三法则？
• 什么是资源获取初始化（RAII）？
• C++概念：容器（在cppreference.com上）

示例

为了提供这样一个类可能看起来像什么的想法，这里有一个具有一些基本特性的简单示例：

• 2D大小可构造
• 2D可调整大小
• operator(size_t, size_t)用于2D行主元素访问
• at(size_t, size_t)用于检查的2D行主元素访问
• 满足容器的概念要求

来源：

#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>

namespace matrices
{

  template<class T>
  class simple
  {
  public:
    // misc types
    using data_type  = std::vector<T>;
    using value_type = typename std::vector<T>::value_type;
    using size_type  = typename std::vector<T>::size_type;
    // ref
    using reference       = typename std::vector<T>::reference;
    using const_reference = typename std::vector<T>::const_reference;
    // iter
    using iterator       = typename std::vector<T>::iterator;
    using const_iterator = typename std::vector<T>::const_iterator;
    // reverse iter
    using reverse_iterator       = typename std::vector<T>::reverse_iterator;
    using const_reverse_iterator = typename std::vector<T>::const_reverse_iterator;

    // empty construction
    simple() = default;

    // default-insert rows*cols values
    simple(size_type rows, size_type cols)
      : m_rows(rows), m_cols(cols), m_data(rows*cols)
    {}

    // copy initialized matrix rows*cols
    simple(size_type rows, size_type cols, const_reference val)
      : m_rows(rows), m_cols(cols), m_data(rows*cols, val)
    {}

    // 1d-iterators

    iterator begin() { return m_data.begin(); }
    iterator end() { return m_data.end(); }
    const_iterator begin() const { return m_data.begin(); }
    const_iterator end() const { return m_data.end(); }
    const_iterator cbegin() const { return m_data.cbegin(); }
    const_iterator cend() const { return m_data.cend(); }
    reverse_iterator rbegin() { return m_data.rbegin(); }
    reverse_iterator rend() { return m_data.rend(); }
    const_reverse_iterator rbegin() const { return m_data.rbegin(); }
    const_reverse_iterator rend() const { return m_data.rend(); }
    const_reverse_iterator crbegin() const { return m_data.crbegin(); }
    const_reverse_iterator crend() const { return m_data.crend(); }

    // element access (row major indexation)
    reference operator() (size_type const row,
      size_type const column)
    {
      return m_data[m_cols*row + column];
    }
    const_reference operator() (size_type const row,
      size_type const column) const
    {
      return m_data[m_cols*row + column];
    }
    reference at() (size_type const row, size_type const column)
    {
      return m_data.at(m_cols*row + column);
    }
    const_reference at() (size_type const row, size_type const column) const
    {
      return m_data.at(m_cols*row + column);
    }

    // resizing
    void resize(size_type new_rows, size_type new_cols)
    {
      // new matrix new_rows times new_cols
      simple tmp(new_rows, new_cols);
      // select smaller row and col size
      auto mc = std::min(m_cols, new_cols);
      auto mr = std::min(m_rows, new_rows);
      for (size_type i(0U); i < mr; ++i)
      {
        // iterators to begin of rows
        auto row = begin() + i*m_cols;
        auto tmp_row = tmp.begin() + i*new_cols;
        // move mc elements to tmp
        std::move(row, row + mc, tmp_row);
      }
      // move assignment to this
      *this = std::move(tmp);
    }

    // size and capacity
    size_type size() const { return m_data.size(); }
    size_type max_size() const { return m_data.max_size(); }
    bool empty() const { return m_data.empty(); }
    // dimensionality
    size_type rows() const { return m_rows; }
    size_type cols() const { return m_cols; }
    // data swapping
    void swap(simple &rhs)
    {
      using std::swap;
      m_data.swap(rhs.m_data);
      swap(m_rows, rhs.m_rows);
      swap(m_cols, rhs.m_cols);
    }
  private:
    // content
    size_type m_rows{ 0u };
    size_type m_cols{ 0u };
    data_type m_data{};
  };
  template<class T>
  void swap(simple<T> & lhs, simple<T> & rhs)
  {
    lhs.swap(rhs);
  }
  template<class T>
  bool operator== (simple<T> const &a, simple<T> const &b)
  {
    if (a.rows() != b.rows() || a.cols() != b.cols())
    {
      return false;
    }
    return std::equal(a.begin(), a.end(), b.begin(), b.end());
  }
  template<class T>
  bool operator!= (simple<T> const &a, simple<T> const &b)
  {
    return !(a == b);
  }

}

需要注意以下几点：

• T需要满足所使用的std::vector成员函数的要求。
• operator()不会进行任何“超出范围”的检查。
• 无需自己管理数据。
• 不需要析构函数、拷贝构造函数或赋值运算符。

因此，您无需为每个应用程序处理正确的内存管理，只需为编写的类处理一次即可。

限制条件

可能存在动态“真实”二维结构更加有利的情况。例如：

• 矩阵非常大且稀疏（如果任何行根本不需要分配，而可以使用nullptr来处理），或者
• 行没有相同数量的列（即如果您根本没有矩阵，而是另一个二维结构）。

- Pixelchemist

---

这是一个很好的答案，但为什么你坚持在示例中使用（并讨论）原始指针？在现代C++中完全没有必要这样做。只需使用 std::vector 即可完成。 - Konrad Rudolph

我最近添加了一个关于常见布局std::vector及其在内存中的布局方式的答案。也许这与这个问题有关。c++ Vector, what happens whenever it expands/reallocate on stack? - Pixelchemist

@FrankH 这就是我所说的“_如果其中一个分配失败，那么一堆分配需要适当的异常处理来避免内存泄漏！_” @内存泄露的风险，但我认为我会进行审查以更进一步。 - Pixelchemist

这里不是有几个错别字吗：reference at() (size_type const row, size_type const column) { return m_data.at(m_cols*row + column); } at operator() (size_type const row, size_type const column) const { return m_data.at(m_cols*row + column); }？难道不应该改为 reference at(size_type const row, size_type const column) 和 const_reference at(size_type const row, size_type const column) const 吗？ - beesleep

@beesleep：是的...当你复制和粘贴operator()并半心半意地将其重命名为at时，就会发生这种情况;) - Pixelchemist

Answer 2

除非涉及静态数组，一维数组比较快。

这是一维数组（std::vector<T>）的内存布局：

+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+

对于动态二维数组（std::vector<std::vector<T>>），以下是相同的操作：

+---+---+---+
| * | * | * |
+-|-+-|-+-|-+
  |   |   V
  |   | +---+---+---+
  |   | |   |   |   |
  |   | +---+---+---+
  |   V
  | +---+---+---+
  | |   |   |   |
  | +---+---+---+
  V
+---+---+---+
|   |   |   |
+---+---+---+

显然，2D情况下会失去缓存局部性并使用更多内存。它还引入了额外的间接性（因此需要跟随额外的指针），但第一个数组有计算索引的开销，因此这些差异或多或少会平衡。

- Konrad Rudolph

---

好的回答。我也考虑了动态二维数组的缓存未命中问题。 - Alex

Answer 3

一维和二维静态数组

• 大小: 两者都需要相同数量的内存。

• 速度: 可以假设没有速度差异，因为这两个数组的内存应该是连续的（整个二维数组应该出现为内存中的一个块，而不是分布在内存中的多个块）。（但这可能取决于编译器。）

一维和二维动态数组

• 大小: 由于二维数组需要指向已分配的一维数组集的指针，所以二维数组将需要比一维数组多一点点的内存。（当我们谈论大数组时，这一点很小，但对于相对较小的数组来说，这一点相对来说可能还是比较大的。）

• 速度: 一维数组可能比二维数组快，因为二维数组的内存不连续，缓存未命中会成为一个问题。

---

使用可行且最合理的方案，如果遇到速度问题，则进行重构。

- user123

---

这并不会有速度差异。这实际上取决于编译器如何计算二维数组的偏移量。 - SigTerm

在速度方面，它也取决于你如何使用数组。计算随机访问元素的偏移量是相同的，但如果你想迭代所有元素，使用一维数组只需线性迭代，而不必使用嵌套循环或将多维坐标乘以内存偏移量。 - Boann

但是static std::vector<T>呢？它是静态的还是动态的？很抱歉，我没有区分它们的能力。 - mr5

动态“2D数组”是指指向其他数组的指针数组。因此，它需要比1D数组更多的空间。 - juanchopanza

正如我所指出的，一个4x4的vector<vector<int>>将会（依赖于系统）需要164个字节，其中100个字节是开销。我不会称之为“微不足道”（它是一个大于2.5的因子），特别是如果你需要处理许多这样的向量或者经常需要复制它们。（当然，随着列数的增加，这个问题的重要性会逐渐降低。） - Pixelchemist

Answer 4

现有的答案都只将1维数组与指针数组进行比较。

在C语言中（但不包括C++），还有第三种选择：可以动态分配具有运行时维度的连续2维数组：

int (*p)[num_columns] = malloc(num_rows * sizeof *p);

并且可以像这样访问：p[row_index][col_index]。

我希望它与1-D数组情况非常相似，但它为您提供更好的语法来访问单元格。

在C++中，您可以通过定义一个类来实现类似的功能，该类在内部维护一个1-D数组，但可以通过重载运算符使用2-D数组访问语法公开它。同样，我预计它与普通的1-D数组具有类似或相同的性能。

- M.M

---

说实话，这听起来有点奇怪，我一直以为几乎任何有效的C都是有效的C++.. g++ 4.8.3可以编译这段代码http://pastebin.com/Te2n1XhZ... - graywolf

@Paladin C和C++是不同的编程语言，它们各自拥有一些另一个语言所没有的特性，并且一些共同的特性也被实现得不同。尝试以标准模式调用g++，你会得到一条诊断信息，因为默认情况下它启用了一些扩展功能。 - M.M

@M.M 在C语言中（但不包括C++），有第三个选项 为什么只有在C语言中呢？在C++中，您可以轻松地执行int (*p)[num_cols] = new int[num_rows][num_cols]; delete[] p;。 - vsoftco

在你的 C++ 代码中，num_cols 必须是一个常量表达式，但在我的代码中它可以在运行时确定。 - M.M

@M.M 哦，我明白了，谢谢！确实，lhs是C语言中指向VLA的指针，好观点！ - vsoftco

Answer 5

1D和2D数组的另一个区别在于内存分配。我们无法确定2D数组的成员是否是连续的。

- Polymorphism

---

是的。如果涉及到的数组在那1%的性能关键代码中，这可能会产生严重影响。 - Engineer

用malloc分配一个大块内存，然后从该块中取出连续的部分用于2D数组，这样不是可以保证连续的内存吗？我相信在游戏等领域中会使用到这种方法。 - Gertjan Brouwer

Answer 6

这取决于你的二维数组是如何实现的。考虑下面的代码：

int a[200], b[10][20], *c[10], *d[10];
for (ii = 0; ii < 10; ++ii)
{
   c[ii] = &b[ii][0];
   d[ii] = (int*) malloc(20 * sizeof(int));    // The cast for C++ only.
}

这里有三种实现：b、c和d。

访问b[x][y]或a[x*20 + y]没有太大区别，因为一种是你进行计算，另一种是编译器为你进行计算。c[x][y]和d[x][y]速度较慢，因为机器必须找到c[x]指向的地址，然后从那里访问第y个元素。这不是一个直接的计算。在某些机器上（例如AS400，它具有36字节（而不是位）指针），指针访问非常缓慢。这完全取决于使用的架构。在x86类型的架构中，a和b的速度相同，c和d比b慢。

- cup

Answer 7

我喜欢Pixelchemist提供的详细答案。这个解决方案的简化版本可能如下所示。首先，声明尺寸：

constexpr int M = 16; // rows
constexpr int N = 16; // columns
constexpr int P = 16; // planes

接下来，创建一个别名以及获取和设置方法：

template<typename T>
using Vector = std::vector<T>;

template<typename T>
inline T& set_elem(vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
    // check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

template<typename T>
inline const T& get_elem(const vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
    // check indexes here...
    return m_[i_*N*P + j_*P + k_];
}

最后，可以按以下方式创建向量并进行索引：

Vector array3d(M*N*P, 0);            // create 3-d array containing M*N*P zero ints
set_elem(array3d, 0, 0, 1) = 5;      // array3d[0][0][1] = 5
auto n = get_elem(array3d, 0, 0, 1); // n = 5

在初始化时定义向量大小可以提供最佳性能。该解决方案修改自此答案。函数可以重载以支持单个向量的不同维度。这种解决方案的缺点是M、N、P参数会隐式传递给get和set函数。可以通过像Pixelchemist一样在类中实现解决方案来解决这个问题。

- Adam Erickson