第 6 章 数据结构Chapter 6 Data structures

我们先介绍如何从列表 ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$ 中取出值。定义函数 $\mathrm{list.get}\colon\mathcal{L}_{K}(\mathcal{V})\times[K]\to\mathcal{V}$ 为We first present how to retrieve values from a list ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$. We define the function $\mathrm{list.get}\colon\mathcal{L}_{K}(\mathcal{V})\times[K]\to\mathcal{V}$ as

该函数关于 ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$ 连续且可微，但关于 $i\in[K]$ 不可微，因为后者是离散变量。在 $\mathcal{V}=\mathbb{R}$ 的特殊情形下，$\mathcal{L}_{K}(\mathcal{V})$ 等价于 $\mathbb{R}^{K}$，因此可以写成The function is continuous and differentiable in ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$ but not in $i\in[K]$, as it is a discrete variable. In the particular case $\mathcal{V}=\mathbb{R}$, $\mathcal{L}_{K}(\mathcal{V})$ is equivalent to $\mathbb{R}^{K}$ and we can therefore write

其中，$\{{\bm{e}}_{1},\dots,{\bm{e}}_{K}\}$ 是 $\mathbb{R}^{K}$ 的标准基。where $\{{\bm{e}}_{1},\dots,{\bm{e}}_{K}\}$ is the standard basis of $\mathbb{R}^{K}$.

接下来，我们介绍如何替换列表 ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$ 中的取值。我们定义函数 $\mathrm{list.set}\colon\mathcal{L}_{K}(\mathcal{V})\times[K]\times\mathcal{V}\to\mathcal{L}_{K}(\mathcal{V})$ 为We now present how to replace values from a list ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$. We define the function $\mathrm{list.set}\colon\mathcal{L}_{K}(\mathcal{V})\times[K]\times\mathcal{V}\to\mathcal{L}_{K}(\mathcal{V})$ as

其中 $j\in[K]$。本着函数式编程的精神，即使只改动了一个元素，该函数返回的也是整个新列表。同样，该函数关于 ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$ 与 ${\bm{v}}\in\mathcal{V}$ 连续且可微，关于 $i\in[K]$ 则不可微。在 $\mathcal{V}=\mathbb{R}$ 的特殊情形下，对于给定列表 ${\bm{l}}=(l_{1},\dots,l_{K})$，可以通过下式设置值 $v\in\mathbb{R}$：for $j\in[K]$. In the functional programming spirit, the function returns the whole new list, even though a single element has been modified. Again, the function is continuous and differentiable in ${\bm{l}}\in\mathcal{L}_{K}(\mathcal{V})$ and ${\bm{v}}\in\mathcal{V}$ but not in $i\in[K]$. In the particular case $\mathcal{V}=\mathbb{R}$, given a list ${\bm{l}}=(l_{1},\dots,l_{K})$, we can set the value $v\in\mathbb{R}$ by

也就是说，我们在 ${\bm{l}}$ 中位置 $i\in[K]$ 处减去旧值 $l_{i}$，再加上新值 $v$。That is, we subtract the old value $l_{i}$ and add the new value $v$ at the location $i\in[K]$ in ${\bm{l}}$.

定长列表可以用数组实现，从而支持对各元素的 $O(1)$ 随机访问。数组在硬件上的对应物是随机存取存储器（RAM），其中内存可按地址（位置）取用。A fixed-length list can be implemented as an array, which enables $O(1)$ random access to individual elements. The hardware counterpart of an array is random access memory (RAM), in which memory can be retrieved by address (location).

为了初始化列表，我们定义 $\mathrm{list.init}\colon\mathcal{V}\to\mathcal{L}_{1}(\mathcal{V})$ 为In order to initialize a list, we define $\mathrm{list.init}\colon\mathcal{V}\to\mathcal{L}_{1}(\mathcal{V})$ as

其中，我们用 $({\bm{v}})$ 表示一个 $1$ 元组。where we used $({\bm{v}})$ to denote a $1$-tuple.

为了向左侧或右侧添加新值，我们定义 $\mathrm{list.pushLeft}\colon\mathcal{L}_{K}(\mathcal{V})\times\mathcal{V}\to\mathcal{L}_{K+1}(\mathcal{V})$ 为In order to add new values either to the left or to the right, we define $\mathrm{list.pushLeft}\colon\mathcal{L}_{K}(\mathcal{V})\times\mathcal{V}\to\mathcal{L}_{K+1}(\mathcal{V})$ as

以及 $\mathrm{list.pushRight}\colon\mathcal{L}_{K}(\mathcal{V})\times\mathcal{V}\to\mathcal{L}_{K+1}(\mathcal{V})$ 为and $\mathrm{list.pushRight}\colon\mathcal{L}_{K}(\mathcal{V})\times\mathcal{V}\to\mathcal{L}_{K+1}(\mathcal{V})$ as

为了从左侧或右侧移除值，我们定义 $\mathrm{list.popLeft}\colon\mathcal{L}_{K}(\mathcal{V})\to\mathcal{L}_{K-1}(\mathcal{V})\times\mathcal{V}$ 为In order to remove values either from the left or from the right, we define $\mathrm{list.popLeft}\colon\mathcal{L}_{K}(\mathcal{V})\to\mathcal{L}_{K-1}(\mathcal{V})\times\mathcal{V}$ as

以及 $\mathrm{list.popRight}\colon\mathcal{L}_{K}(\mathcal{V})\to\mathcal{L}_{K-1}(\mathcal{V})\times\mathcal{V}$ 为and $\mathrm{list.popRight}\colon\mathcal{L}_{K}(\mathcal{V})\to\mathcal{L}_{K-1}(\mathcal{V})\times\mathcal{V}$ as

集合 $\mathcal{L}_{0}(\mathcal{V})$ 是只含空列表的单元素集。The set $\mathcal{L}_{0}(\mathcal{V})$ is a singleton which contains the empty list.

pushLeft 与 pushRight 函数只能分别把值插入列表开头和末尾。现在我们研究 insert 函数，其目标是在任意位置添加新值，并将所有值右移，使列表大小增加 $1$。我们定义函数 $\mathrm{list.insert}:\mathcal{L}_{K}(\mathcal{V})\times[K+1]\times\mathcal{V}\rightarrow\mathcal{L}_{K+1}(\mathcal{V})$ 为The pushLeft and pushRight functions can only insert values at the beginning and at the end of a list, respectively. We now study the insert function, whose goal is to be able to add a new value at an arbitrary location, shifting all values to the right and increasing the list size by $1$. We define the function $\mathrm{list.insert}:\mathcal{L}_{K}(\mathcal{V})\times[K+1]\times\mathcal{V}\rightarrow\mathcal{L}_{K+1}(\mathcal{V})$ as

其中 $j\in[K+1]$。与 $\mathrm{list.set}$ 函数一样，$\mathrm{list.insert}$ 关于 ${\bm{l}}$ 与 ${\bm{v}}$ 显然是连续且可微的，关于 $i$ 则不可微，因为后者是离散变量。作为特例，我们自然得到for $j\in[K+1]$. As for the $\mathrm{list.set}$ function, $\mathrm{list.insert}$ is readily continuous and differentiable in ${\bm{l}}$ and ${\bm{v}}$, but not in $i$, as it is a discrete variable. As special cases, we naturally recover

对于 $\mathrm{list.init}$、$\mathrm{list.push}$ 和 $\mathrm{list.pop}$ 函数，其关于自变量的连续性与可微性都是显然的（无需连续松弛）。至于 $\mathrm{list.set}$ 函数，$\mathrm{list.insert}$ 函数关于 ${\bm{l}}$ 和 ${\bm{v}}$ 连续且可微，但关于 $i$ 则不然。The $\mathrm{list.init}$, $\mathrm{list.push}$ and $\mathrm{list.pop}$ functions are readily continuous and differentiable with respect to their arguments (a continuous relaxation is not needed). As for the $\mathrm{list.set}$ function, the $\mathrm{list.insert}$ function is continuous and differentiable in ${\bm{l}}$ and ${\bm{v}}$, but not in $i$.

在底层，变长列表可以实现为链表或动态数组。链表提供 $O(K)$ 随机访问，而动态数组允许 $O(1)$ 随机访问，代价是需要进行内存重分配。Under the hood, a variable-length list can be implemented as a linked list or as a dynamic array. A linked list gives $O(K)$ random access while a dynamic array allows $O(1)$ random access, at the cost of memory reallocations.

$\mathrm{list.pushRight}$ 和 $\mathrm{list.popRight}$ 函数可用于实现栈（后进先出，又称 LIFO 行为）。$\mathrm{list.pushLeft}$ 和 $\mathrm{list.popRight}$ 函数可用于实现队列（先进先出，又称 FIFO 行为）。The $\mathrm{list.pushRight}$ and $\mathrm{list.popRight}$ functions can be used to implement a stack (last in first out a.k.a. LIFO behavior). The $\mathrm{list.pushLeft}$ and $\mathrm{list.popRight}$ functions can be used to implement a queue (first in first out a.k.a. FIFO behavior).

为了能够关于索引对 $\mathrm{list.get}$ 求导，一个自然的想法是用分布 ${\bm{\pi}}_{i}\in\triangle^{K}$ 替换整数索引 $i\in[K]$，我们可以将其解释为软索引。于是整数索引 $i\in[K]$ 等价于 delta 分布 ${\bm{\pi}}_{i}\in\{{\bm{e}}_{1},\dots,{\bm{e}}_{K}\}$。我们将连续松弛 $\mathrm{list.softGet}\colon\mathcal{L}_{K}(\mathcal{V})\times\triangle^{K}\to\conv(\mathcal{V})$ 定义为In order to be able to differentiate $\mathrm{list.get}$ w.r.t. indexing, a natural idea is to replace the integer index $i\in[K]$ by a distribution ${\bm{\pi}}_{i}\in\triangle^{K}$, which we can interpret as a soft index. An integer index $i\in[K]$ is then equivalent to a delta distribution ${\bm{\pi}}_{i}\in\{{\bm{e}}_{1},\dots,{\bm{e}}_{K}\}$. We define the continuous relaxation $\mathrm{list.softGet}\colon\mathcal{L}_{K}(\mathcal{V})\times\triangle^{K}\to\conv(\mathcal{V})$ as

其中 $\mathrm{cond}$ 已在第 5.7 节中研究。在 $\mathcal{V}=\mathbb{R}$ 的特殊情形下，可得where $\mathrm{cond}$ is studied in Section 5.7. In the particular case $\mathcal{V}=\mathbb{R}$, we obtain

这一点如图 6.1 所示。This is illustrated in Fig. 6.1.

分布 ${\bm{\pi}}_{i}=(\pi_{i,1},\dots,\pi_{i,K})$ 的选择编码了各元素 $({\bm{l}}_{1},\dots,{\bm{l}}_{K})$ 关于 ${\bm{l}}_{i}$ 的重要性。如果我们认为 $|i-j|$ 越小，${\bm{l}}_{i}$ 与 ${\bm{l}}_{j}$ 的相关性就越强，那么定义以 $i$ 为中心的分布（即分布的众数在 $i$ 处取得）就是合理的。例如，将范围限制在邻居 ${\bm{l}}_{i-1}$ 和 ${\bm{l}}_{i+1}$（即大小为 $1$ 的窗口），我们可以定义稀疏分布The choice of the distribution ${\bm{\pi}}_{i}=(\pi_{i,1},\dots,\pi_{i,K})$ encodes the importance of the elements $({\bm{l}}_{1},\dots,{\bm{l}}_{K})$ w.r.t. ${\bm{l}}_{i}$. If we consider that the smaller $|i-j|$ is, the more related ${\bm{l}}_{i}$ and ${\bm{l}}_{j}$ are, then it makes sense to define a distribution centered around $i$ (i.e., such that the mode of the distribution is achieved at $i$). For example, limiting ourselves to the neighbors ${\bm{l}}_{i-1}$ and ${\bm{l}}_{i+1}$ (i.e., a window of size $1$), we can define the sparse distribution

在这种特殊情形下，$\mathrm{list.get}$ 函数的连续松弛可以表示为离散卷积，In this particular case, the continuous relaxation of the $\mathrm{list.get}$ function can then be expressed as a discrete convolution,

其中 $\kappa(-1)\coloneqq\frac{1}{4}$、$\kappa(1)\coloneqq\frac{1}{4}$、$\kappa(0)\coloneqq\frac{1}{2}$，且对于 $j\not\in\{-1,0,1\}$ 有 $\kappa(j)\coloneqq 0$。假设 $\mathcal{V}=\mathbb{R}^{M}$，则 $\mathrm{list.softGet}$ 的计算复杂度为 $O(M\cdot|\mathrm{supp}({\bm{\pi}}_{i})|)$。where $\kappa(-1)\coloneqq\frac{1}{4}$, $\kappa(1)\coloneqq\frac{1}{4}$, $\kappa(0)\coloneqq\frac{1}{2}$, and $\kappa(j)\coloneqq 0$ for $j\not\in\{-1,0,1\}$. Assuming $\mathcal{V}=\mathbb{R}^{M}$, the computational complexity of $\mathrm{list.softGet}$ is $O(M\cdot|\mathrm{supp}({\bm{\pi}}_{i})|)$.

为了对索引求导，我们可以将连续松弛 $\mathrm{list.softSet}\colon\mathcal{L}_{K}(\mathcal{V})\times\triangle^{K}\times\mathcal{V}\to\mathcal{L}_{K}(\conv(\mathcal{V}))$ 定义为To differentiate w.r.t. indexing, we can define the continuous relaxation $\mathrm{list.softSet}\colon\mathcal{L}_{K}(\mathcal{V})\times\triangle^{K}\times\mathcal{V}\to\mathcal{L}_{K}(\conv(\mathcal{V}))$ as

其中 $j\in[K]$，且 $I\sim\mathrm{Categorical}({\bm{\pi}}_{i})$。等价地，可以写为where $j\in[K]$ and $I\sim\mathrm{Categorical}({\bm{\pi}}_{i})$. Equivalently, we can write

其中 $\mathrm{ifelse}$ 已在第 5.6 节中研究。由于where $\mathrm{ifelse}$ is studied in Section 5.6. Since

这一松弛相当于使用逐元素期望。因此，$\mathrm{list.softSet}$ 输出的列表取值于 $\conv(\mathcal{V})$ 而非 $\mathcal{V}$。不过要注意，当 $\mathcal{V}=\mathbb{R}^{M}$ 时，也有 $\conv(\mathcal{V})=\mathbb{R}^{M}$。this relaxation amounts to using an element-wise expectation. As a result, the list output by $\mathrm{list.softSet}$ takes values in $\conv(\mathcal{V})$ instead of $\mathcal{V}$. Note however that when $\mathcal{V}=\mathbb{R}^{M}$, then $\conv(\mathcal{V})=\mathbb{R}^{M}$ as well.

为了关于索引对取值插入求导，我们可以将连续松弛 $\mathrm{list.softInsert}\colon\mathcal{L}_{K}(\mathcal{V})\times\triangle^{K+1}\times\mathcal{V}\to\mathcal{L}_{K+1}(\conv(\mathcal{V}))$ 定义为To differentiate value insertion w.r.t. indexing, we can define the continuous relaxation $\mathrm{list.softInsert}\colon\mathcal{L}_{K}(\mathcal{V})\times\triangle^{K+1}\times\mathcal{V}\to\mathcal{L}_{K+1}(\conv(\mathcal{V}))$ as

其中 $I\sim\mathrm{Categorical}({\bm{\pi}}_{i})$。对于 $j\in[K+1]$，三个必要的概率很容易通过下式计算where $I\sim\mathrm{Categorical}({\bm{\pi}}_{i})$. The three necessary probabilities can easily be calculated for $j\in[K+1]$ by

在多维列表（数组或张量）中，列表 ${\bm{l}}\in\mathcal{L}_{K_{1},\dots,K_{T}}(\mathcal{V})$ 的每个元素 ${\bm{l}}_{\bm{i}}\in\mathcal{V}$ 现在都可以用多元整数 ${\bm{i}}=(i_{1},\dots,i_{T})\in[K_{1}]\times\dots\times[K_{T}]$ 来索引，其中 $T\in\mathbb{N}$ 是 ${\bm{l}}$ 的轴数。我们总是可以通过将多维索引 ${\bm{i}}\in[K_{1}]\times\dots\times[K_{T}]$ 替换为展平索引 $i\in[K_{1}\dots K_{T}]$，把多维列表展平为一维列表；反过来，将展平的一维数组转换为多维数组也是可行的。因此，对于 $K\coloneqq K_{1}\dots K_{T}$，$[K]$ 与 $[K_{1}]\times\dots\times[K_{T}]$ 之间存在双射。In multi-dimensional lists (arrays or tensors), each element ${\bm{l}}_{\bm{i}}\in\mathcal{V}$ of a list ${\bm{l}}\in\mathcal{L}_{K_{1},\dots,K_{T}}(\mathcal{V})$ can now be indexed by a multivariate integer ${\bm{i}}=(i_{1},\dots,i_{T})\in[K_{1}]\times\dots\times[K_{T}]$, where $T\in\mathbb{N}$ is the number of axes of ${\bm{l}}$. We can always flatten a multi-dimensional list into a uni-dimensional list by replacing the multi-dimensional index ${\bm{i}}\in[K_{1}]\times\dots\times[K_{T}]$ by a flat index $i\in[K_{1}\dots K_{T}]$. The converse operation, converting a flat uni-dimensional array into a multi-dimensional array, is also possible. Therefore, there is a bijection between $[K]$ and $[K_{1}]\times\dots\times[K_{T}]$ for $K\coloneqq K_{1}\dots K_{T}$.

这意味着，前文关于一维情形下软索引的讨论可直接推广到多维情形。所需的只是定义一个概率分布 ${\bm{\pi}}_{\bm{i}}\in\triangle^{K_{1}\times\dots\times K_{T}}$ 的能力。例如，在处理图像时，我们可以定义一个概率分布，使其概率质量只落在像素 ${\bm{i}}$ 的相邻像素上，这是图像处理中的标准做法。另一种简单做法是采用各轴概率分布的乘积。This means that the previous discussion on soft indexing in the uni-dimensional setting readily applies to the multi-dimensional setting. All it takes is the ability to define a probability distribution ${\bm{\pi}}_{\bm{i}}\in\triangle^{K_{1}\times\dots\times K_{T}}$. For example, when working with images, we can define a probability distribution putting probability mass only on the neighboring pixels of pixel ${\bm{i}}$, a standard approach in image processing. Another simple approach is to use a product of axis-wise probability distributions.

$\mathrm{dict.get}$ 函数的目标是取回与某个键相关联的值，前提是字典包含该键。形式上，我们将 $\mathrm{dict.get}\colon\mathcal{D}_{L}(\mathcal{K},\mathcal{V})\times\mathcal{K}\to\mathcal{V}\cup\{\infty\}$ 函数定义为The goal of the $\mathrm{dict.get}$ function is to retrieve the value associated with a key, assuming that the dictionary contains this key. Formally, we define the $\mathrm{dict.get}\colon\mathcal{D}_{L}(\mathcal{K},\mathcal{V})\times\mathcal{K}\to\mathcal{V}\cup\{\infty\}$ function as

该函数关于字典 ${\bm{d}}$ 连续且可微，但关于键 ${\bm{k}}$ 则不然。等价地，我们可以将该函数写为The function is continuous and differentiable in the dictionary ${\bm{d}}$, but not in the key ${\bm{k}}$. Equivalently, we can write the function as

分母体现了这样一个事实：若字典 ${\bm{d}}$ 中没有键与键 ${\bm{k}}$ 相匹配，则该函数无定义。假设 ${\bm{k}}\in\{{\bm{k}}_{1},\dots,{\bm{k}}_{L}\}$ 且 $\mathcal{V}=\mathbb{R}^{M}$，我们也可以将其写为The denominator encodes the fact that the function is undefined if no key in the dictionary ${\bm{d}}$ matches the key ${\bm{k}}$. Assuming ${\bm{k}}\in\{{\bm{k}}_{1},\dots,{\bm{k}}_{L}\}$ and $\mathcal{V}=\mathbb{R}^{M}$, we can also write

这表明，我们可以把 $\mathrm{dict.get}$ 看作最近邻搜索。which shows that we can see $\mathrm{dict.get}$ as a nearest neighbor search.

$\mathrm{dict.set}$ 函数的目标是替换与某个已有键相关联的值。形式上，我们将 $\mathrm{dict.set}:\mathcal{D}_{L}(\mathcal{K},\mathcal{V})\times\mathcal{K}\times\mathcal{V}\rightarrow\mathcal{D}_{L}(\mathcal{K},\mathcal{V})$ 函数定义为The goal of the $\mathrm{dict.set}$ function is to replace the value associated with an existing key. Formally, we define the $\mathrm{dict.set}:\mathcal{D}_{L}(\mathcal{K},\mathcal{V})\times\mathcal{K}\times\mathcal{V}\rightarrow\mathcal{D}_{L}(\mathcal{K},\mathcal{V})$ function as

如果字典中没有键与输入键 ${\bm{k}}$ 相匹配，则该函数保持字典不变。该函数关于 ${\bm{d}}$ 和 ${\bm{v}}$ 连续且可微，但关于 ${\bm{k}}$ 则不然。The function leaves the dictionary unchanged if no key in the dictionary matches the input key ${\bm{k}}$. The function is continuous and differentiable in ${\bm{d}}$ and ${\bm{v}}$, but not in ${\bm{k}}$.

尽管我们将字典视为键—值对的列表，但在实践中，字典（又称关联数组）通常使用哈希表或搜索树来实现。字典在硬件上的对应物称为内容寻址存储器（CAM），又称关联存储器。While we view dictionaries as lists of key-value pairs, in practice, a dictionary (a.k.a. associative array) is often implemented using a hash table or search trees. The hardware counterpart of a dictionary is called content-addressable memory (CAM), a.k.a. associative memory.