高维数组是如何通过底层连续存储实现的？

给定数组arr，它的连续存储形式为c。假设数组arr的shape为：(d_0, d_1, ..., d_n)​，则c的大小为prod(d_0, d_1, ... d_n)。

使用(idx_0, idx_1, ..., idx_n)来表示这n+1个dim上的索引。即arr[idx_0, idx_1, ..., idx_n] = val。

此外strides=(s_0, s_1, ..., s_n)表示每个dim上的的步长。

有了这些内容的支持，就可以将一个连续的数组转化成逻辑上的高维数组。arr的shape定义了每个维度的大小，也就是每个维度上索引值的取值范围：(0 <= idx_0 < d_0, 0 <= idx_1 < d_1, ..., 0 <= idx_n < d_n)。arr是一个高维的数组，它的底层存储形式为c，那么如何将arr的值和c对应起来呢？arr和c的对应可以通过下面的式子来实现：arr[idx_0, idx_1, ..., idx_n] = c[idx_0 * s_0 + idx_1 * s_1 +, ..., idx_n * s_n]。

一个关键的问题，如何知道strides的值。看一个简单的例子：
$$b=\left[\begin{array}{c}0,1,2\\ 3,4,5\end{array}\right]$$

$$d=[0,1,2,3,4,5]$$

b是高维数组，shape为(2， 3)，d是它的底层存储形式。它们的映射关系为b[i, j] = d[i*3 + j*1]。由此可见，在这里s_0 = 3, s_1 = 1。所以这就是strides的意义。再看一个shape为(3, 2, 3)的高维数组e，及其连续存储形式f：

$$e=\left[\begin{array}{c}\left[\begin{array}{c}0,1,2\\ 3,4,5\end{array}\right]\\ \\ \left[\begin{array}{c}6,7,8\\ 9,10,11\end{array}\right]\\ \\ \left[\begin{array}{c}12,13,14\\ 15,16,17\end{array}\right]\end{array}\right]$$

$$f=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]$$

它们的映射关系为e[i, j, k] = f[i*(2*3) + j*2 + k*1]。当把这个逐步扩展到3,4维数组的时候，就可以发现strides的计算规律了。下面是具体的算法：

def compact_strides(shape):
    """ Utility function to compute compact strides """
    stride = 1
    res = []
    for i in range(1, len(shape) + 1):
        res.append(stride)
        stride *= shape[-i]
    return tuple(res[::-1])
1
2
3
4
5
6
7
8

有的时候，我们只想获取一小块数据，而不需要整个高维数组。numpy.ndarray支持高维数组的切片，那么这个是如何实现的呢？

Python中支持切片的功能，主要是通过三个数来实现的：slice = (start, stop, step)。为了对每个维度进行索引，对于n+1个维度，就有n+1个slice。对第i个维度的切片，我们使用slice_i = (start_i, stop_i, step_i)来表示。因此，所有的slice为(slice_0, slice_1, ..., slice_n)。OK，给定了这样一组切片，我们怎么完成底层数组到高维数组的映射呢？

我们首先需要知道切片之后的形状。对于第i个维度，它的大小为sd_i = math.ceil((stop_i - start_i) / step_i)。因此，切片之后的新的数组的形状为：sd_0, sd_1, ..., sd_n。它表示了新的数组的每个维度上索引的取值范围：0 <= idx_0 < sd_0, ..., 0 <= idx_n < sd_n。

start_i表示第i个维度上的其实位置，也就可以理解为第i个维度的偏移量，不妨记为offset_i。step_i表示第i个维度上的步幅的大小，因此它和s_i一起发挥作用。

然后，映射可以通过下面的式子来实现：slice_arr[idx_0, ..., idx_n] = c[ s_0 * (idx_0 * step_0 + start_0) + , ..., s_n * (idx_n * step_n + start_n) ]。