1D或2Darrays，速度更快？
我需要表示2D场（轴x，y），我面临一个问题：我应该使用一维数组还是二维数组？
我可以想象，一维数组（y + x * n）的重新计算索引可能比使用二维数组（x，y）慢，但是我可以想象一维可以在CPUcaching中。
我做了一些谷歌search，但只发现关于静态数组的页面（并指出1D和2D基本相同）。 但我的arrays必须是dynamic的。
有啥
- 更快，
- 较小（RAM）
dynamic一维数组或dynamic二维数组？
谢谢 ：）
tl; dr：你应该使用一维方法。
注意：当比较dynamic1d或dynamic2d存储模式而不填充书籍时，不能深入研究影响性能的细节，因为代码的性能取决于大量的参数。 如果可能的话。
1.什么更快？
对于稠密matrix来说，一维方法可能会更快，因为它提供了更好的内存局部性，更less的分配和重新分配开销。
2.什么更小？
Dynamic-1D比2D方法消耗更less的内存。 后者也需要更多的分配。
备注
我在下面列出了一个很长的回答，有几个原因，但是我想首先对你的假设做一些评论。
我可以想象，重新计算一维数组（y + x * n）的索引可能比使用二维数组（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个。 （根据指示表 – 雾霾由于差异较小，我认为指数重新计算应该不会有很大的performance差异，我认为这种差异本身不太可能成为任何计划的瓶颈。
这带来了我们下一个（也是更有趣）的一点：
…但我可以想象一下，1D可能在CPUcaching中…
诚然，但2d也可以在CPUcaching中。 请参阅“缺点：内存位置”来解释为什么1d更好。
长的答案，或为什么dynamic二维数据存储（指针指针或vectorvector）对于简单 /小matrix是“坏”的。
注意：这是关于dynamic数组/分配scheme[malloc / new / vector等]。 一个静态的二维数组是一个连续的内存块，因此不会受到我将要介绍的缺点的影响。
问题
为了能够理解为什么dynamic数组的dynamic数组或向量的向量很可能不是select的数据存储模式，您需要了解这些结构的内存布局。
使用指针指针语法的示例情况
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; }
缺点
内存地点
对于这个“matrix”，你分配一个四个指针块和四个整数四个块。 所有的分配都是不相关的 ，因此可能导致任意的内存位置。
下面的图片会给你一个关于内存看起来如何的想法。
对于真正的二维情况 ：
- 紫色方块是
p本身所占据的记忆位置。 - 绿色正方形将内存区域
p指向（4 xint*）。 - 4个连续的蓝色方块的4个区域是绿色区域的每个
int*指向的区域
对于1d情况下的2D映射 ：
- 绿色方块是唯一需要的指针
int * - 蓝色正方形为所有matrix元素（16 x
int）整合存储器区域。
这意味着（使用左侧布局时），由于caching等原因，您可能会观察到比连续存储模式更差的性能（如右侧所示）。
比方说，caching行是“一次传输到caching中的数据量”，让我们想象一个程序访问整个matrix一个接一个的元素。
如果您有一个正确alignment的32位值的4倍4matrix，具有64字节caching行（典型值）的处理器能够“一次性”数据（4 * 4 * 4 = 64字节）。 如果你开始处理，并且数据还没有在caching中，你将面临caching未命中，数据将从主内存中获取。 这个负载可以一次获取整个matrix，因为它适合一个caching行，当且仅当它是连续存储（和正确alignment）。 处理这些数据时可能不会有更多的遗漏。
在dynamic的“真正的二维”系统中，每行/列的位置不相关，处理器需要分别加载每个存储单元。 尽pipe只需要64个字节，但对于4个不相关的内存位置加载4个高速caching行将在最坏的情况下实际传输256个字节并浪费75％的吞吐量带宽。 如果使用2dscheme处理数据，则会再次（如果尚未caching的话）在第一个元素上面临高速caching未命中。 但是现在，只有第一行/列将在第一次从主内存加载后进入caching，因为所有其他行都位于内存中的其他位置，而不是与第一行相邻。 一旦你到达一个新的行/列，将再次有一个caching未命中，并从主内存执行下一个负载。
长话短说：2d模式有较高的caching未命中的机会，由于数据的局部性，1dscheme提供了更好的性能潜力。
频繁分配/取消分配
- 多达
N + 1（4 + 1 = 5）分配（使用new，malloc，allocator :: allocate或其他）是创build所需的NxM（4×4）matrix所必需的。 - 相应数量的正确的相应的释放操作也必须被应用。
因此，与单个分配scheme相比，创build/复制这种matrix的成本更高。
越来越多的行越来越糟糕。
内存消耗开销
我将为32位int指针和32位指针指针指向一个大小。 （注意：系统依赖）
让我们记住：我们想要存储一个4×4的intmatrix，这意味着64个字节。
对于一个NxMmatrix，我们使用存储的指针指针scheme
-
N*M*sizeof(int)[实际的蓝色数据] + -
N*sizeof(int*)[绿色指针] + -
sizeof(int**)[紫色variablesp]字节。
这使得本例中的4*4*4 + 4*4 + 4 = 84个字节，当使用std::vector<std::vector<int>>时会变得更糟。 它将需要N * M * sizeof(int) + N * sizeof(vector<int>) + sizeof(vector<vector<int>>)字节，即4*4*4 + 4*16 + 16 = 144字节对于4 x 4 int，总共为64字节。
另外，根据使用的分配器，每个单独的分配可能（也很可能）会有另外16个字节的内存开销。 （一些“Infobytes”为了正确的释放，存储分配的字节数）。
这意味着最坏的情况是：
N*(16+M*sizeof(int)) + 16+N*sizeof(int*) + sizeof(int**)
= 4*(16+4*4) + 16+4*4 + 4 = 164 bytes ! _Overhead: 156%_
开销的份额将随着matrix的大小增长而减小，但仍将存在。
内存泄漏的风险
这些分配需要适当的exception处理，以避免内存泄漏，如果其中一个分配失败！ 您需要跟踪分配的内存块，并且在释放内存时不要忘记它们。
如果内存和下一行的new运行不能被分配（特别是当matrix非常大时）， std::bad_alloc被new抛出。
例：
在上面提到的新的/删除的例子中，如果我们想在bad_allocexception的情况下避免泄漏，我们将面对更多的代码。
// 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;
概要
在某些情况下，“真正的二维”内存布局是合适的，也就是说，如果每行的列数不是固定的，但是在最简单和普通的二维数据存储的情况下，它们会增加代码的复杂性，降低性能和程序的内存效率。
替代
您应该使用连续的内存块，并将您的行映射到该块上。
这样做的“C ++方法”可能是写一个类来pipe理你的内存，同时考虑重要的事情
- 什么是三的规则？
- 资源获取的含义是初始化（RAII）？
- C ++概念：Container（在cppreference.com上）
例
为了提供这样一个类如何看起来像一个想法，这里有一个简单的例子，有一些基本的function：
- 2D-尺寸constructible
- 2D-可resize
-
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()不执行任何“范围”检查 - 无需自行pipe理数据
- 不需要析构函数，复制构造函数或赋值运算符
所以，你不必为每个应用程序的正确的内存处理而烦恼，而只需要为你编写的类处理一次。
限制
有些情况下，dynamic的“真实”二维结构是有利的。 这是例如，如果
- matrix是非常大和稀疏（如果任何行甚至不需要分配，但可以使用nullptr处理）或如果
- 行的列数不一样（也就是说，如果你没有matrix，除了另一个二维结构）。
除非你正在谈论静态数组， 否则 1D更快 。
这里是一维数组（ std::vector<T> ）的内存布局：
+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+
这里的dynamic二维数组（ std::vector<std::vector<T>> ）也是一样的：
+---+---+---+ | * | * | * | +-|-+-|-+-|-+ | | V | | +---+---+---+ | | | | | | | | +---+---+---+ | V | +---+---+---+ | | | | | | +---+---+---+ V +---+---+---+ | | | | +---+---+---+
很明显，2D案例失去了caching局部性，并使用更多的内存。 它还引入了一个额外的间接寻址（因此还有一个额外的指针），但是第一个数组有额外的计算索引的开销，所以这些都是或多或less的。
一维和二维静态arrays
-
大小：两者都需要相同数量的内存。
-
速度：你可以假设没有速度差异，因为这两个数组的内存应该是连续的（整个2D数组应该在内存中显示为一个块，而不是在内存中散布的一堆块）。 （但是这可能是依赖于编译器的。）
1D和2Ddynamic数组
-
大小：由于二维数组需要的指针指向一组分配的一维数组，因此二维数组需要比一维数组多一点的内存。 （当我们谈论真正的大数组的时候，这个微小的位是微不足道的，对于小数组，这个微小的位相对来说可能相当大）。
-
速度：一维数组可能比二维数组快，因为二维数组的内存不会是连续的，所以caching未命中将成为一个问题。
使用什么工作，似乎最合乎逻辑，如果你面临速度问题，然后重构。
内存分配出现1D和2Darrays的另一个区别。 我们不能确定二维数组的成员是否是sequental。
现有的答案都只是比较一维数组与指针数组。
在C（但不是C ++）中有第三种select; 您可以拥有一个dynamic分配的连续二维数组，并具有运行时间维度：
int (*p)[num_columns] = malloc(num_rows * sizeof *p);
并且像p[row_index][col_index]那样被访问。
我期望这与一维数组的情况有非常相似的性能，但是它为您提供更好的访问单元格的语法。
在C ++中，可以通过定义一个内部维护一维数组的类来实现类似的function，但可以通过使用重载运算符的二维数组访问语法来公开它。 再一次，我会期望与普通的一维数组具有相似或相同的性能。
这真的取决于你的二维数组是如何实现的。
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. }
这里有3个实现：b，c和d访问b [x] [y]或[x * 20 + y]不会有太大的区别，因为一个是你正在做计算，另一个是编译器为你做。 c [x] [y]和d [x] [y]比较慢，因为机器必须findc [x]指向的地址，然后从那里访问第y个元素。 这不是一个直接的计算。 在一些机器上（例如有36字节（不是位）指针的AS400），指针访问非常慢。 这一切都依赖于使用的架构。 在x86types架构上，a和b的速度相同，c和d比b慢。
