多维数组的设计

date

Feb 21, 2023

slug

anatomy_of_an_high_dimensional_array_1

status

Published

多维数组的内存布局

数组通常作为连续数据存储在一段连续的内存中，在这个内存段中，可以自由选择如何排列数组元素。通常有以下两种排列方式：row-major 和 column-major：

row-major 将数组一行一行的连续存储，此时每一行中的连续元素在内存中彼此相邻；

column-major将数组一列一列的存储起来，此时每一列的连续元素在内存中彼此相邻。

虽然上述专业术语特指二维数组的行和列，但是可以将这个概念推广到任意维度的数组：例如在 row-major 布局中，行索引变化最慢，列索引变化最块，推广到多个维度，就是其中沿着第一轴（维度）的索引最慢，沿着最后一个轴（维度）的索引最快。column-major 则相反。

以二维数组为例，两种布局方式如下图所示：

多维度数组的索引

利用 shape 来索引数组

数据存储在内存中之后，应该如何索引呢？可以利用数组的 shape ，来建立数组索引下标到数组内存偏移量的映射。例如，对于二维数组，可以通过如下方式来索引数组中的元素：

Row major: A[i, j] => Adata[i * A.shape[1] + j]

Column major: A[i, j] => Adata[j * A.shape[0] + i]

以 row-major 存储方式为例，通过shape 索引有如下图所示：

此外，也可以简单扩展到多维数组的情况，

通过 strides 来索引数组

此外，还有另外一种方式，是使用 strides 和 offset 来描述数组索引到数组内存偏移量的映射，这种方式可以用于描述不同的映射策略，并且可以在不操作内存的情况下仅通过简单地修改 strides 和 offset 来实现多维数组上的许多常见操作，例如转置、广播、切片索引等。Numpy便是采用这种方式来描述多维数组与内存之间的映射。当然，也可以把上述两种使用 shape 建立映射的方式简单理解为是利用strides 建立映射的一个特例，毕竟后者可以转换为前者。

当利用 strides 建立数组索引下标与数组在内存偏移量的映射时，使用如下三个属性来描述一个多维数组：

shape, 表示数组的形状

strides, 表示每个维度步长

offset, 表示从起始位置的偏移量

以二维数组为例，利用该方式，数组索引下标到内存偏移量的映射关系如下：

下图展示了一个二维数组 A 及其采用 row-major 方式在内存中的布局：

对于该二维数组，其数据存放位置为Adata，且有属性：shape = (3,4), strides=(4, 1), offset = 0。对其进行索引时，可以通过如下映射关系：A[i][j] = Adata[offset + i * strides[0] + j * strides[j]]，例如 A[2][3] = Adata[0 + 2 * 4 + 3 * 1] = Adata[11]。

注：此处可以先不用管 strides 为什么是 (4, 1)，后面会介绍其代表含义。

在不操作上述数组内存Adata的情况下，此时如果设置shape=(4, 3), stride = (3, 1), offset=0，那么通过 A[i][j] = Adata[offset + i * strides[0] + j * strides[j]] 映射关系索引得到的多维数组将如下图所示：

显然，相较于最开始表示的数组，此时该内存段内数据所表示的数组形状发生了改变，但是我们却并没有对内存进行操作，且仅仅是改变了 strides 和 shape 这两个属性。

同样，在不操作上述数组内存Adata 的情况下，此时如果设置shape=(4, 3), stride = (1, 3), offset=0，那么通过 A[i][j] = Adata[offset + i * strides[0] + j * strides[j]] 映射关系可索引得到多维数组如下图所示：

显然，相较于最开始表示的数组，此时该内存段内数据所表示的数组发生了转置，而我们并没有对内存进行任何操作，且仅仅是改变了strides 和 shape 这两个属性。

同样的，还可以令 shape=(2, 2), stride = (3, 1), offset=4，此时得到的仅仅是原始多维数组的一部分，如下所示：

可见，同样一份内存，仅仅改变 shape、strides、offset 即可改变该内存数据所表示的多维数组，在Numpy中，这样的操作称为视图（View）。

现在已经知道可以在不产生任何显著计算成本（不对内存进行任何操作）的情况下重构多维数组，因为仅仅涉及改变数组的三个属性，那这三个属性具体应该如何设置呢？

Strides 如何影响多维度数组

前面提到，一段连续的内存中存储的数据被看作什么样的高维数组（视图）是由shape、strides、offset 来决定的。具体是如何影响的呢？

首先是shape，shape 决定了该高维数组的形状与维数（ndims），进而决定了索引该高维数组时的每个维度的下标范围。其次是strides，strides 长度与shape 长度相同，里面每一个数值表示了对应维度下相邻两个数值在Adata 距离。最后是offset，表示了该高维数组首个数值距离内存Adata上首位置的偏移。以二维数组为例，下图展示了shape、strides、offset的作用。

shape 通常是我们最直接操作的对象，例如 reshape、boradcast、transpose 等操作都是通过 shape 来影响视图的，且一般是直接用用户给定的。

strides 是根据具体视图来计算的，可以说 strides 是高维数组的核心，他给了我们看待连续内存块的不同方式，因而对于同一块连续的内存，可以有多种视图。

给定一块包含 12个数值的连续内存，假设shape 为（3，4），从 strides 的含义可以很容易得到 strides=(4, 1)；那如果 shape=(2,3,2)呢？下图为 shape=(2,3,2)时所表示的三维度数组

从维度2开始计算strides，显然，在维度2上，相邻元素在内存中也是相邻的，因此strides[2] = 1；然后看维度1，在维度1上，高维数组的相邻元素在内存中的间隔为2，此处的2其实是维度2上共有两个元素。最后是维度0，在维度0上，相邻两个元素在内存中的间距为6，此处的6为维度1和维度2 上总共有6个元素（2 * 3 = 6）。所以，strides 其实就是 shape 的后缀积，且后缀积最后一个元素为1，长度与shape相同。后缀积的计算方式可以有下图例：

offset为偏离量，即从该内存起始位置开始偏移多少个元素。只有在切片索引的时候才会用到，因此，offset的计算将在介绍切片索引的时候解释。

一些不操作内存即可改变多维数组的操作

Reshape

reshape，即改变当前数组的形状。

reshape 不会改变高维数组中元素的数量，因此 offset 不会改变。strides即按照后缀积的方式来计算即可。

Transpose

transpose 或者 permute 表示对高维数组的维度进行重新排列，若以二维数组（即矩阵）为例，重新排列维度就是指转置。

transpose 会修改高维数组的 shape 和 strides，但因为不会改变高维数组中元素的个数，因此不会修改offset。

首先来看shape，因为仅仅是把维度调换了次序，因此每个维度的元素数量还是没有改变，所以，新的shape只需要按照维度排序的顺序也重新排列即可。例如，原先shape = (2,3,4)，经过transpose(0,2,1) 之后，新的shape应该是(2, 4, 3)。

至于strides，回想 strides[i] 表示在维度i上相邻两个元素在内存中的间距。那把维度的次序调换之后，调换前后所对应的维度的strides 应该是不会被改变的，因此，只需要把strides 按照维度的调换次序也跟着调换即可。例如，原先strides = (6,2,1)，经过transpose(0,2,1) 之后，新的shape应该是(6, 1,2)。

Broadcast

broadcast，称为广播，多维数组在进行运算时遇到 shape 不匹配问题，可以通过广播来使得shape 匹配。需要注意的是，绝不是可以广播任意的shape，一般被广播的维度i要么原先的shape[i]=1，要么，是新增加一个维度。例如，对于shape=(2, 1, 4) 的多维度数组，要么在维度1（shape[1]=1，因此可以广播）上进行广播，如广播为shape=(2, 100, 4)的多维度数组；要么通过广播增加维度，如广播为shape=(100, 2, 1, 4)的四维数组，此时增加的维度，一定是增加到了最高的维度，即在 shape 的最前面。

广播操作首先肯定会改变shape，毕竟shape是广播操作的参数，且通过对比参数shape与原先的shape，还可以得知是在哪个维度进行了广播以及是否通过广播增加了维度。具体而言，因为容器shape的长度表示了多维数组的维度，所以首先可以通过计算广播前后 shape 的长度得知是否增加了维度以及增加了几维；然后，通过从后往前比对广播前后的shape容器的数值便可知道在哪个维度上进行了广播。例如，有shape = (3, 4, 1, 5)的四维数组，执行 boradcast(2, 3, 4, 10, 5)操作后，new_shape=(2, 3, 4, 10, 5)，显然，len(new_shape) ≠ len(shape)，因此可知增加了 len(new_shape) - len(shape)) 个维度，此外，从后往前对比 new_shape与 shape的中数值，可以发现，shape[-2]≠ new_shape[-2]，因此可知倒数第二个维度的长度发生了改变。

表面上看，broadcast 操作增加了多维数组中的元素个数，但是我们可以发现，不管是增加维度还是改变某个维度的长度，增加的元素都是另外维度数值的重复。例如，对于如下 (3*3)的二维数组，进行boradcast之后，为(3 * 3 * 3)的三维数组，即增加了一个维度，且增加的维度上的元素为原先二维数组的重复，因此，可以在不操作内存的情况下，实现广播。考虑到增加的元素的对应关系，即 B[i][j][k] = B[0][j][k] = A[j][k] = Adata[j * strides[0] + k * strides[k]] = Adata[i* 0 + j * strides[0] + k * strides[k]]。因此，只需要将所增加的维度对应的strides修改为0即可。对于长度被修改的维度，同理，令改维度对应的长度为0即可。

GetItem

getitem，对多维数组的切片索引，即通过切片 slice 选取多维数组中的部分元素，slice通常包括三个数值，分别为 start、end、step，代表的含义分别为起始位置，终止位置，跨越步长。通常索引的时候，在每个维度上均有一个 slice 用来选取该维度的数值。如下图例，对于 (3*4) 的二维数组，对齐进行索引，其中，维度 0 的切片为 (0：3：2)，所选中的行为第0行和第2行；维度1的切片为 (1:4:2)，选中的列为第1列和第3列，因此，A[0:3:2, 1:4:2] 所选中的元素为图中红色标注的元素，为 (2*2) 的二维数组。

对数组的切片索引不仅会改变数组的shape和strides，还会改变offset，如上如所示，通过切片索引得到的 (2*2) 数组的首个元素在内存中的位置显然不在起始位置（起始位置为0）。首先是shape，shape 可以通过对各个维度的切片计算得到，例如，对于上图所示的索引，在维度1上，切片为(1:4:2)，那么切片之后改维度的长度为 ceil((4-1) / 2 ), 其中 ceil 为向上取整。推广一下，任一维度切片之后的长度为ceil((end-start)/step)。

其次是strides，再次回忆strides的含义，strides[i]表示维度i上，相邻元素在连续内存布局中的间隔。现在我们通过切片来索引，且切片中有step来进行跨步的选取元素，因此，通过该切片选取后，新的数组在该维度上的strides 应该为原先步长 * step。例如，对于上图所示的索引，初始数组A.strides=(4,1)，在维度1上，切片为(1:4:2)，那么切片之后改维度的new_strides[i] = strides[i] * 2=2。推广一下，任一维度切片之后的new_strides[i]=strides[i] * slice[i].step。

最后是 offset ，回忆 offset 的含义，其表示多维数组中首个元素(即下标均为0)在其连续内存段中的偏移量。思考偏移是怎么发生的呢，为什么切片索引会产生偏移量呢？其不过是切片的时候，每个维度的slice.start 不是0导致的偏移，因此只需要把所有维度的偏移加起来即可，那具体到某个维度时，该如何计算该维度的偏移量呢？以上图为例子，上图中对于维度1，slice[1].start=1，然后在该维度产生了3个元素的偏移量，3是怎么来的呢？3就是该维度原先的步长 strides[1]=3。如果 slice[1].start=2，此时产生的偏移量即为 2 * 3。推广一下，任一维度 i 的偏移量为 slice[i].start * strides[i]。总的偏移量即为多为维度的偏移量相加。

参考

Deep Learning Systems (dlsyscourse.org)

Memory layout of multi-dimensional arrays