SciPy 稀疏矩阵（4）：LIL（上）

“

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

”

矩阵和向量组的关系

在当今的数字化时代，矩阵已经成为了一个无处不在的概念。它不仅在数学和物理领域有着广泛的应用，而且在计算机科学、经济学、社会学等多个领域都扮演着重要的角色。在内容创作中，矩阵同样也是一个极具表现力的工具。它可以被用来展示数据的分布、关联和趋势，帮助创作者更直观地呈现复杂的信息。例如，在数据分析领域，矩阵可以清晰地展示数据之间的关系，让读者更加深入地理解数据的内在规律。而在社会学领域，矩阵则可以用来表示不同群体之间的关系，帮助读者更好地理解社会结构和社会动态。因此，对于内容创作者来说，掌握矩阵的运用技巧，可以让自己的创作更具表现力和说服力。

在数学和物理中，向量组是一个非常重要的概念。向量组是由一组向量组成的集合，这些向量可以是实数、复数或者其他任何数学对象。向量组在各种领域都有着广泛的应用，例如在物理学的力学、电磁学、量子力学等领域，以及在工程、计算机科学、经济等多个领域都有重要的应用。向量组的性质和运算规则是线性代数的重要内容，对于理解和应用向量组非常重要。向量组可以按照不同的方式进行分类，例如按照向量的维数可以分为一维、二维、三维等等。此外，向量组还可以按照向量的个数进行分类，可以分为有限个向量和无限个向量。

矩阵和向量组是线性代数中的重要概念，它们之间存在着密切的关系。矩阵可以看作是向量组的扩展，而向量组则可以看作是矩阵的特例。矩阵是由若干行和若干列组成的二维数组，而向量组则是由若干向量组成的集合。矩阵的每一行可以看作是一个向量，而向量组中的每个向量也可以看作是一个行向量。此外，矩阵的秩与向量组的秩也有着密切的联系。矩阵的秩等于其行向量组的秩，也等于其列向量组的秩。因此，了解矩阵和向量组之间的关系对于深入理解线性代数中的概念和性质非常重要。

矩阵是有序向量组：矩阵是数学中的基本概念之一，它是一个由数字组成的矩形阵列。在形式上，矩阵是由若干行和若干列组成的，每一行和每一列都有一定的顺序。这个顺序就决定了矩阵是一个有序向量组。也就是说，矩阵中的元素按照一定的规则排列，这个规则规定了每个元素的位置和方向。这个规则非常重要，因为不同的规则会导致不同的矩阵，从而具有不同的性质和用途。因此，当我们谈论矩阵时，必须明确其所遵循的规则和排列方式。矩阵的应用非常广泛，包括线性代数、数值分析、计算机图形学等领域。矩阵的重要性在于其具有多种数学性质和算法，可以解决各种实际问题。通过矩阵的变换、求解线性方程组、计算行列式等操作，我们可以轻松地处理大量数据并得到精确的结果。矩阵的应用范围不断扩大，特别是在人工智能和机器学习领域中，矩阵运算更是无处不在。无论是图像处理、语音识别还是自然语言处理，都需要用到矩阵的运算。因此，对于从事这些领域的研究人员和工程师来说，掌握矩阵的基本概念和性质是必不可少的。总之，矩阵是一个有序向量组，它按照一定的规则排列而成，具有多种数学性质和算法。掌握矩阵的基本概念和应用方法，对于从事科学研究和技术开发的人来说是必不可少的。

稀疏向量的压缩存储

在矩阵运算中，我们常常将矩阵视为有序的向量组。对于稀疏矩阵，我们同样可以将其视为有序稀疏向量组。通过针对每个稀疏向量进行压缩存储，我们可以实现对稀疏矩阵的压缩存储。这种压缩方法不仅可以节省存储空间，而且可以提高矩阵运算的效率。因为稀疏矩阵中的非零元素在存储和运算过程中需要占用更多的存储空间和计算资源。而压缩存储可以有效地减少这些开销，使得矩阵运算更加高效。因此，针对有序稀疏向量组的压缩存储是稀疏矩阵处理中一个非常有效的方法。

稀疏向量的压缩存储是一种高效的数据存储方式，它只存储非零元素的索引和值，而不是存储整个向量。这种方式可以大大减少存储空间的使用，并加快向量运算的速度。通过只存储非零元素，可以避免存储大量的零值，从而减少了存储空间的浪费。同时，由于只存储非零元素，在进行向量运算时，可以只对非零元素进行操作，从而提高了运算的效率。因此，稀疏向量的压缩存储在处理大规模数据和高维数据时具有非常重要的作用。

对于稀疏向量的压缩存储，虽然只涉及到非零元素的索引和值，但其代码实现方式多种多样。一一详述这些实现方式既不现实，也完全没有必要。实际上，稀疏向量的存储策略主要可以分为两种：二元组容器法和两个序列法。

二元组容器法

我们首先看到二元组容器法，二元组容器法指的是把多个二元组放到一个容器中，按照这种方法可以定义出如下类：

代码语言：javascript复制

class Element:
    def __init__(self, index, value):
        self.index, self.value = index, value


class SparseVector:
    def __init__(self, elements):
        self.elements = list(elements)

二元组在这里直接被我定义成了一个类，非常简单。至于稀疏向量就是多个二元组类的实例构成的一个容器，因此其属性初始化函数的参数就是多个二元组类的实例。需要注意的是我在属性初始化的时候使用 list 把多个二元组的实例转换成了序列，当然也可以转换成集合或者其他数据结构，做法不唯一。与此同时，针对稀疏向量类我们还可以添加一些功能，比如获取向量的维数、二元组的索引重复该如何处理等等。

两个序列法

两个序列法就没有太多可供自由发挥的实现方式，它的实现方式非常的单一，先把多个二元组按照一定的顺序排好，然后依次读取二元组的索引构成第 1 个序列（记作索引序列），依次读取二元组的元素值构成第 2 个序列（记作元素值序列），按照这种方法可以定义出如下类：

代码语言：javascript复制

class Element:
    def __init__(self, index, value):
        self.index, self.value = index, value


class SparseVector:
    def __init__(self, elements):
        self.indices, self.values = [], []
        for element in elements:
            self.indices.append(element.index)
            self.values.append(element.value)

两个序列法实现起来就是这么简单。需要注意的是我采用两个列表来表示对应的两个序列，当然换成其他前驱和后继均只有一个的数据结构（比如链表）也是可以的。与此同时，针对稀疏向量类我们还可以添加一些功能，比如获取向量的维数、多个二元组的索引重复该如何处理等等。

稀疏矩阵的压缩存储

对于基于稀疏向量的稀疏矩阵的压缩存储，虽然只涉及到稀疏向量的顺序，但其代码实现方式多种多样。一一详述这些实现方式既不现实，也完全没有必要。实际上，基于稀疏向量的稀疏矩阵的存储策略主要可以分为两种：稀疏向量序列法和索引值分离法。接下来我通过把矩阵看成是有序行向量组，并且稀疏向量的存储策略选用两个序列法来实现两种基于稀疏向量的稀疏矩阵的存储策略。

稀疏向量序列法

稀疏向量序列法没有太多可供自由发挥的实现方式，它的实现方式非常的单一，就是把多个稀疏向量按照一定的顺序排好，按照这种方法可以定义出如下类：

代码语言：javascript复制

class Element:
    def __init__(self, index, value):
        self.index, self.value = index, value


class SparseVector:
    def __init__(self, elements):
        self.indices, self.values = [], []
        for element in elements:
            self.indices.append(element.index)
            self.values.append(element.value)


class SparseMatrix:
    def __init__(self, sparse_vectors):
        self.sparse_vectors = sparse_vectors

稀疏向量序列法实现起来就是这么简单，需要注意的是构造函数的参数 sparse_vectors 一定只能是序列，不可以是集合，因为矩阵中不管是任意两行还是任意两列都不能交换顺序！与此同时，针对稀疏矩阵类我们还可以添加一些功能，比如获取矩阵的行和列等等。

索引值分离法

索引值分离法就没有太多可供自由发挥的实现方式，它的实现方式非常的单一，先把多个稀疏向量按照一定的顺序排好，然后依次读取稀疏向量的索引序列构成第 1 个序列（记作行向量组索引序列），依次读取稀疏向量的元素值序列构成第 2 个序列（记作行向量组元素值序列），按照这种方法可以定义出如下类：

代码语言：javascript复制

class Element:
    def __init__(self, index, value):
        self.index, self.value = index, value


class SparseVector:
    def __init__(self, elements):
        self.indices, self.values = [], []
        for element in elements:
            self.indices.append(element.index)
            self.values.append(element.value)


class SparseMatrix:
    def __init__(self, sparse_vectors):
        self.row_vectors_indices, self.row_vectors_values = [], []
        for sparse_vector in sparse_vectors:
            self.row_vectors_indices.append(sparse_vector.indices)
            self.row_vectors_values.append(sparse_vector.values)

索引值分离法实现起来就是这么简单。需要注意的是我采用两个列表来表示对应的行向量组索引序列和行向量组元素值序列，当然换成其他前驱和后继均只有一个的数据结构（比如链表）也是可以的。与此同时，针对稀疏矩阵类我们还可以添加一些功能，比如获取矩阵的行和列等等。

SciPy LIL 格式的稀疏矩阵

在开始 SciPy LIL 格式的稀疏矩阵之前我花了一些篇幅讲解稀疏向量的二元组存储策略外加上基于稀疏向量的稀疏矩阵的存储策略，这主要是因为 SciPy LIL 格式的稀疏矩阵用的存储策略就是基于稀疏向量的稀疏矩阵的存储策略的第 2 种方法：索引值分离法。和上述定义除了属性名有一点不同（意思是一样的），其他几乎没有什么区别。在 SciPy LIL 格式的稀疏矩阵中，行向量组索引序列就是属性名 rows，行向量组元素值序列就是属性名 data。还有两点需要注意：第一，这两个序列并不是使用 Python 列表，而是其元素为 Python 列表的 NumPy 数组；第二，行向量组索引序列中的元素（序列）都是排好序的（便于使用二分查找来提高查找效率）。之所以这种格式叫做 LIL，是因为 LIL 是 Lists In List 的缩写。

实例化

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

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

案例

实例化一个 4 行 5 列元素类型为双精度浮点数的全 0 矩阵：

代码语言：javascript复制

>>> from scipy import sparse
>>> import numpy as np
>>> np.random.seed(0)
>>> mtx = sparse.lil_matrix((4, 5))

通过高阶索引给矩阵的部分元素赋值：

代码语言：javascript复制

>>> from numpy.random import rand
>>> data = np.round(rand(2, 3))
>>> data
array([[1., 1., 1.],
       [1., 0., 1.]])
>>> mtx[:2,[1, 2, 3]] = data
>>> mtx
<4x5 sparse matrix of type '<class 'numpy.float64'>'
        with 5 stored elements in List of Lists format>
>>> print(mtx)
  (0, 1)        1.0
  (0, 2)        1.0
  (0, 3)        1.0
  (1, 1)        1.0
  (1, 3)        1.0
>>> mtx.todense()
matrix([[0., 1., 1., 1., 0.],
        [0., 1., 0., 1., 0.],
        [0., 0., 0., 0., 0.],
        [0., 0., 0., 0., 0.]])
>>> mtx.toarray()
array([[0., 1., 1., 1., 0.],
       [0., 1., 0., 1., 0.],
       [0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0.]])

我们可以发现，它输出的格式不叫 Lists In List，而叫做 List of Lists，其实这两者的意思是一样的，Lists In List 是说很多个列表在一个列表中，List of Lists 是说从属于很多个列表的一个列表。需要注意的是这里的单复数千万不能乱改，因为一旦改了意思就发生了千差万别的变化！

更多的索引操作和切片操作：

代码语言：javascript复制

>>> mtx = sparse.lil_matrix([[0, 1, 2, 0], [3, 0, 1, 0], [1, 0, 0, 1]])
>>> mtx.todense()
matrix([[0, 1, 2, 0],
        [3, 0, 1, 0],
        [1, 0, 0, 1]], dtype=int32)
>>> print(mtx)
  (0, 1)        1
  (0, 2)        2
  (1, 0)        3
  (1, 2)        1
  (2, 0)        1
  (2, 3)        1
>>> mtx[:2,:]
<2x4 sparse matrix of type '<class 'numpy.intc'>'
        with 4 stored elements in List of Lists format>
>>> mtx[:2,:].todense()
matrix([[0, 1, 2, 0],
        [3, 0, 1, 0]], dtype=int32)
>>> mtx[1:2,[0,2]].todense()
matrix([[3, 1]], dtype=int32)
>>> mtx.todense()
matrix([[0, 1, 2, 0],
        [3, 0, 1, 0],
        [1, 0, 0, 1]], dtype=int32)

目前为止，我们可以发现 LIL 格式的稀疏矩阵按照行列索引访问或者修改对应值的操作可以看成是先通过行索引找到两个有序顺序表，然后对这两个有序顺序表执行一些操作。因此，这样的操作完全可以看成是有序顺序表中的一些操作，对应关系如下表所示：

LIL 格式的稀疏矩阵的操作	有序顺序表的操作	时间复杂度
按照行列索引查找对应值	有序顺序表的二分查找	O(log₂n)
按照行列索引修改对应值（非零元素改非零元素）	有序顺序表的二分查找（找到并修改）	O(log₂n)
按照行列索引修改对应值（零元素改非零元素）	有序顺序表的二分查找（找不到并插入）	O(n)
按照行列索引修改对应值（非零元素改零元素）	有序顺序表的二分查找（找到并删除）	O(n)

通过上表，理解为什么 SciPy 官方文档为什么说 LIL 格式的稀疏矩阵插入一个元素（零元素改非零元素）的最坏时间复杂度是 O(n) 就非常简单了。

优缺点

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

1. 非常灵活的切片操作。
2. 能够非常高效地改变稀疏结构。

当然，SciPy LIL 格式的稀疏矩阵也有缺点：

1. 执行矩阵运算的操作的效率非常低。
2. 因为是基于有序行向量组的压缩存储，所以列切片的效率非常低。

索引 效率 压缩 存储 scipy

0 人点赞