SciPy 稀疏矩阵（3）：DOK

散列表

散列表（Hash Table）是一种非常重要的数据结构，它允许我们根据键（Key）直接访问在内存存储位置的数据。这种数据结构是一种特殊类型的关联数组，对于每个键都存在一个唯一的值。它被广泛应用于各种程序设计和应用中，扮演着关键的角色。散列表的主要优点是查找速度快，因为每个元素都存储了它的键和值，所以我们可以直接访问任何元素，无论元素在数组中的位置如何。这种直接访问的特性使得散列表在处理查询操作时非常高效。因此，无论是进行数据检索、缓存操作，还是实现关联数组，散列表都是一种非常有用的工具。这种高效性使得散列表在需要快速查找和访问数据的场景中特别有用，比如在搜索引擎的索引中。散列表的基本实现涉及两个主要操作：插入（Insert）和查找（Lookup）。插入操作将一个键值对存储到散列表中，而查找操作则根据给定的键在散列表中查找相应的值。这两种操作都是 O(1) 时间复杂度，这意味着它们都能在非常短的时间内完成。这种时间复杂度在散列表与其他数据结构相比时，如二分搜索树或数组，显示出显著的优势。然而，为了保持散列表的高效性，我们必须处理冲突，即当两个或更多的键映射到同一个内存位置时。这是因为在散列表中，不同的键可能会被哈希到同一位置。这是散列表实现中的一个重要挑战。常见的冲突解决方法有开放寻址法和链地址法。开放寻址法是一种在散列表中解决冲突的方法，其中每个单元都存储一个键值对和一个额外的信息，例如，计数器或下一个元素的指针。当一个元素被插入到散列表中时，如果当前位置已经存在另一个元素，那么下一个空闲的单元将用于存储新的元素。然而，这个方法的一个缺点是，在某些情况下，可能会产生聚集效应，导致某些单元过于拥挤，而其他单元过于稀疏。这可能会降低散列表的性能。链地址法是一种更常见的解决冲突的方法，其中每个单元都存储一个链表。当一个元素被插入到散列表中时，如果当前位置已经存在另一个元素，那么新元素将被添加到链表的末尾。这种方法的一个优点是它能够处理更多的冲突，而且不会产生聚集效应。然而，它也有一个缺点，那就是它需要更多的空间来存储链表。总的来说，散列表是一种非常高效的数据结构，它能够快速地查找、插入和删除元素。然而，为了保持高效性，我们需要处理冲突并采取一些策略来优化散列表的性能。例如，我们可以使用再哈希（rehashing）技术来重新分配键，以更均匀地分布散列表中的元素，减少聚集效应。还可以使用动态数组或链表等其他数据结构来更好地处理冲突。这些优化策略可以显著提高散列表的性能，使其在各种应用中更加高效。

基于散列表的三元组

上回说到，三元组的存储策略有 2 种，分别是三元组容器法和三个序列法。然而，无论采用上述的哪一种方法来表示稀疏矩阵都不能在时间复杂度为 O(1) 的情况下按照行列索引对元素进行访问。如果想存储三元组表示的稀疏矩阵的同时又要确保按照行列索引对元素进行访问的效率高，在存储三元组（非零元素）信息的过程中使用散列表是有必要的。考虑到散列表是按照键来快速计算（时间复杂度 O(1)）出对应值的内存地址，然后按照内存地址读取对应的值；又因为对于一个矩阵的元素访问操作而言，我们都是根据行列索引来获取对应位置的值。显然，我们需要把非零元素的行列索引作为散列表的键，非零元素的值作为散列表的值。

SciPy DOK 格式的稀疏矩阵

在开始 SciPy DOK 格式的稀疏矩阵之前我花了一些篇幅讲解散列表以及基于散列表的三元组，这主要是因为 SciPy DOK 格式的稀疏矩阵就是基于散列表的三元组。然而，众所周知，Python 中内置的数据结构：字典，就是实现的数据结构中的散列表。因此，SciPy 中的 DOK 没有自己去实现散列表，而是直接利用 Python 中内置的数据结构：字典。之所以这种格式叫做 DOK，是因为 DOK 是 Dictionary Of Keys 的缩写。

实例化

SciPy DOK 格式的稀疏矩阵类的定义位于 scipy.sparse 包中的 dok_matrix 类，对其进行实例化就能获取一个 SciPy DOK 格式的稀疏矩阵的实例。当然，构造实例的方法主要有 3 种：

1. dok_matrix(D)：D 是一个普通矩阵（二维数组）。
2. dok_matrix(S)：S 是一个稀疏矩阵。
3. dok_matrix((M, N), [dtype])：会实例化一个 M 行 N 列元素类型为 dtype 的全 0 矩阵。dtype 是一个可选参数，默认值为双精度浮点数。

案例

考虑到散列表可以在时间复杂度为 O(1) 的情况下按照关键字查找对应值，因此 SciPy 的 DOK 格式也可以在时间复杂度为 O(1) 的情况下按照行列索引查找或者修改对应元素的值，因此我们完全可以先构造一个全 0 矩阵，然后在指定位置上多次赋值即可：

>>> import numpy as np
>>> from scipy.sparse import dok_matrix
>>> mtx = dok_matrix((5, 5), dtype=np.float64)
>>> mtx
<5x5 sparse matrix of type '<class 'numpy.float64'>'
        with 0 stored elements in Dictionary Of Keys format>
>>> for ir in range(5):
...     for ic in range(5):
...         mtx[ir, ic] = 1.0*(ir != ic)
...
>>> mtx
<5x5 sparse matrix of type '<class 'numpy.float64'>'
        with 20 stored elements in Dictionary Of Keys format>
>>> mtx.todense()
matrix([[0., 1., 1., 1., 1.],
        [1., 0., 1., 1., 1.],
        [1., 1., 0., 1., 1.],
        [1., 1., 1., 0., 1.],
        [1., 1., 1., 1., 0.]])

索引操作和切片操作：

>>> mtx[1, 1]
0.0
>>> mtx[1, 1:3]
<1x2 sparse matrix of type '<class 'numpy.float64'>'
        with 1 stored elements in Dictionary Of Keys format>
>>> mtx[1, 1:3].todense()
matrix([[0., 1.]])
>>> mtx[[2, 1], 1:3].todense()
matrix([[1., 0.],
        [0., 1.]])

虽然我们之前试过把一个全 0 矩阵中的非主对角线上的零元素修改成了非零元素 1，存储的非零元素数量发生了变化，从 0 变成了 20。现在我们反过来看看，把其中某一个非零元素再改成 0，看看存储非零元素数量会不会变成 19：

>>> mtx[0, 1] = 0
>>> mtx
<5x5 sparse matrix of type '<class 'numpy.float64'>'
        with 19 stored elements in Dictionary Of Keys format>

到目前为止，我们可以发现 DOK 格式的稀疏矩阵按照行列索引访问或者修改对应值的操作完全可以看成是散列表中的一些操作，对应关系如下表所示：

优缺点

SciPy DOK 格式的稀疏矩阵有着以下优点：

1. 一点一点（逐个元素或者逐个矩阵块）地构造稀疏矩阵的效率非常高
2. 按照行列索引访问或者修改元素的时间复杂度为 O(1)
3. 切片操作灵活且高效
4. 改变非零元素的分布的效率非常高
5. 转换为 COO 格式的稀疏矩阵的效率非常高

当然，SciPy DOK 格式的稀疏矩阵也有缺点，这里的缺点也就只有一个，就是进行线性代数的矩阵运算的操作效率非常低，因为需要对散列表的键值对进行遍历。

下回预告

不管是 COO 格式的稀疏矩阵还是 DOK 格式的稀疏矩阵，它们都无一例外地对三元组进行了存储。因此，COO 格式的稀疏矩阵和 DOK 格式的稀疏矩阵可以放在一个板块中。然而，无论是 COO 格式的稀疏矩阵还是 DOK 格式的稀疏矩阵，进行线性代数的矩阵运算的操作效率都非常低。至于如何优化线性代数的矩阵运算的操作效率，继续改进三元组的存储方式可能不好办了，需要换一种存储方式。至于存储方式也不需要我们去实现，SciPy 已经实现了这样的稀疏矩阵存储方式，它就是另一个板块，这个板块共有 4 种稀疏矩阵格式，分别是{BSR, CSC, CSR, LIL}，下一回先介绍 LIL 格式的稀疏矩阵！