系统程序员的多维数组视图：用步长替代嵌套索引

作为C程序员，我们大多数人对多维数组的指针运算采用嵌套式的思考方式： 一维数组的地址是 base + x。 二维数组的地址，在行主序布局下是 base + x + yx_size，在列主序布局下是 base + y + xy_size。 三维数组的地址，在行-列主序布局下是 base + x + (y + z*y_size)*x_size。 以此类推。

一个简单却强大的视角转变是：不再把各个维度看作彼此嵌套、有先后次序的关系，而是开始以更对称、更平等的方式来看待它们。唯一需要做的改变是为每个维度关联一个 stride，并把偏移量计算为乘积之和： 一维数组的地址现在变成 base + xx_stride。 二维数组的地址现在变成 base + xx_stride + yy_stride。 三维数组的地址现在变成 base + xx_stride + yy_stride + zz_stride。

一维数组的这一改变已经很有用，因为它让你能够为已有数组创建带 stride 的视图。例如，你可以跳过每隔一个的元素，使得只有偶数下标的元素可见，只需令 x_stride *= 2、x_size /= 2。如果你先执行 base += x_stride，你还能得到奇数下标元素的互补 stride 视图。新视图的 stride、大小和基址都由旧视图的 stride、大小和基址计算得出，因此这些变换可以递归地应用。如果你把「取每隔 2 个元素」的做法应用两次，你就得到每隔 4 个元素的视图。

其实，我们漏掉了一个退化情形，而它实际上非常有用。零维数组就是一个标量左值。为什么把这个看似平凡的情形包含进来是值得的呢？因为我们可以从原本用于低维数组的数据中创建高维视图。而其中最重要的例子之一就是标量广播。要为标量创建一个长度为 n 的向量视图，使用相同的基址、x_size 为 n、x_stride 为 0。这同样适用于把标量广播到矩阵和更高维数组：只需添加具有所需大小的新维度，并把所有新维度的 stride 设为 0。

标量视图之所以重要的另一个原因是，它们的作用就像指向单个标量的普通旧指针。这意味着你可以指向高维数组的某个条目，然后通过你的标量视图写入它，同时还能随时间观察到下层数据的变化（如果它发生变化的话）。

这个基本思路同样适用于把向量广播到矩阵。你可以选择把该向量当作行向量还是列向量。在前一种情况下，你把 y_stride 设为 0、y_size 设为矩阵所需的高度。如果你想把该向量当作列向量，做法相同，但交换 x 和 y 的 stride 与大小。

行向量 vs 列向量的例子展示了这种方法的另一个巨大优势：你可以仅仅通过置换描述符中的 stride 和大小来转置维度，而无需任何底层数据移动。使用转置视图的性能代价则更间接，取决于它如何影响内存访问顺序。不过，如果你确实想复制数据以符合某个给定视图，你只需调用你的通用数组复制函数，它会按照默认或指定的约定（例如行主序）来布局被复制的数据。这一观察对所有视图都成立，而不只是转置。例如，如果你在一维数组上采取很长的 stride，因而对缓存利用不佳，你可以通过该视图做一次复制，这样你就得到了一个仍然符合相同数组形状的紧凑排布版本的数据。

关于广播的最后一点说明：有时把它看作两个独立的步骤会很有用。第一步是把低维数组提升到更高维，而不复制数据。于是标量变成长度为 1 的向量，长度为 n 的向量变成 n×1 或 1×n 的矩阵。广播随后把大小为 1 的维度扩展到指定大小。提升的逆操作是降级，即把任何大小为 1 的维度折叠掉。

另一个可以看作广播思想延伸的 stride 技巧，是使用能生成重叠但非完全相同（不同于广播）的元素视图的 stride。举个例子，假设你想对一个向量做信号处理或数据分析，需要以长度为 n 的滑动窗口来查看数据。你可以创建一个矩阵视图，其中 y_stride = x_stride、y_size = x_size - n + 1。也就是说，假设你希望重叠窗口的步长为 1。你可以用 y_stride = k*x_stride 来支持步长为 k 的窗口。你可以把滑动和切片结合起来，生成矩阵的对角线、次对角线、超对角线等向量视图。

你还可以使用负 stride，只要相应地更新基址。其基本操作是通过取反 stride 来反转一个维度。你首先必须把基址偏移到该维度上的最后一个元素。作为练习，请证明使用反转和转置的组合，你可以生成图像的所有 90 度旋转。

创建重塑视图（其中底层数据以相同方式呈现，没有重复、重叠或遗漏）也可以非常有用。例如，你可以把向量重塑为矩阵，或把矩阵重塑为向量。你可以取任何高维数组并将其重塑为向量，以按内存布局顺序查看底层数据。重塑时元素总数保持不变，但分解为不同维度大小的方式会有所不同。Paul Khoung 提供的一个令人惊讶的例子是：如果你把一个长度为 2^n 的一维数组重塑为一个 n 维数组

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）