为什么 lil_matrix 和 dok_matrix 与普通的字典相比这么慢？

Question

我想迭代构建稀疏矩阵，并注意到根据 SciPy 文档有两个合适的选项：

class scipy.sparse.lil_matrix(arg1, shape=None, dtype=None, copy=False)[source] Row-based linked list sparse matrix

This is an efficient structure for constructing sparse matrices incrementally.

DoK matrix:

class scipy.sparse.dok_matrix(arg1, shape=None, dtype=None, copy=False)[source] Dictionary Of Keys based sparse matrix.

This is an efficient structure for constructing sparse matrices incrementally.

但是当我运行基准测试与构建值字典（稍后可以很容易地转换为稀疏矩阵）相比时，后者比使用任何一个快 10-20 倍稀疏矩阵模型：

from scipy.sparse import dok_matrix, lil_matrix
from timeit import timeit
from collections import defaultdict

def common_dict(rows, cols):
    freqs = defaultdict(lambda: defaultdict(int))
    for row, col in zip(rows, cols):
        freqs[row][col] += 1

    return freqs

def dok(rows, cols):
    freqs = dok_matrix((1000,1000))
    for row, col in zip(rows, cols):
        freqs[row,col] += 1

    return freqs

def lil(rows, cols):
    freqs = lil_matrix((1000,1000))
    for row, col in zip(rows, cols):
        freqs[row,col] += 1

    return freqs


def benchmark():
    cols = range(1000)
    rows = range(1000)

    res = timeit("common_dict({},{})".format(rows, cols), 
                 "from __main__ import common_dict", 
                 number=100)

    print("common_dict: {}".format(res))

    res = timeit("dok({},{})".format(rows, cols), 
                 "from __main__ import dok", 
                 number=100)

    print("dok: {}".format(res))

    res = timeit("lil({},{})".format(rows, cols), 
                 "from __main__ import lil", 
                 number=100)

    print("lil: {}".format(res))

结果：

benchmark()

common_dict: 0.11778324202168733
dok: 2.2927695910912007
lil: 1.3541790939634666

是什么导致矩阵模型产生如此大的开销，有什么方法可以加快它的速度吗？是否存在 dok 或 lil 比普通的 dicts 更喜欢的用例？

Answer 1

当我将 2 个稀疏数组的 += 更改为 = 时：

for row, col in zip(rows, cols):
    #freqs[row,col] += 1
    freqs[row,col] = 1

他们各自的时间减半。最耗时的是索引。使用 += 它必须同时执行 __getitem__ 和 __setitem__.

当文档说 dok 和 lil 更适合迭代构造时，他们的意思是扩展其底层数据结构比其他格式更容易。

当我尝试用您的代码制作 csr 矩阵时，我得到：

/usr/lib/python2.7/dist-packages/scipy/sparse/compressed.py:690: SparseEfficiencyWarning: Changing the sparsity structure of a csr_matrix is expensive. lil_matrix is more efficient. SparseEfficiencyWarning)

和 30 倍慢的速度。

所以速度声明是相对于像 csr 这样的格式，而不是相对于纯 Python 或 numpy 结构。

您可能想查看 dok_matrix.__get_item__ 和 dok_matrix.__set_item__ 的 Python 代码，看看当您执行 freq[r,c] 时会发生什么。

构建 dok 的更快方法是：

freqs = dok_matrix((1000,1000))
d = dict()
for row, col in zip(rows, cols):
    d[(row, col)] = 1
freqs.update(d)

利用 dok 是子类字典这一事实。请注意 dok 矩阵不是字典的字典。它的键是像 (50,50).

这样的元组

构造相同稀疏数组的另一种快速方法是：

freqs = sparse.coo_matrix((np.ones(1000,int),(rows,cols)))

换句话说，因为你已经有了rows和cols数组（或范围），计算相应的data数组，然后构造稀疏数组。

但是，如果您必须在增量增长步骤之间对矩阵执行稀疏运算，那么 dok 或 lil 可能是您的最佳选择。

稀疏矩阵是为线性代数问题开发的，例如求解具有大稀疏矩阵的线性方程。多年前，我在 MATLAB 中使用它们来解决有限差分问题。对于这项工作，计算友好的 csr 格式是最终目标，而 coo 格式是一种方便的初始化格式。

现在许多 SO scipy 稀疏问题都来自 scikit-learn 和文本分析问题。它们还用于生物数据库文件。但仍然 (data),(row,col) 定义方法效果最好。

所以稀疏矩阵从来都不是为了快速增量创建而设计的。像字典和列表这样的传统 Python 结构在这方面要好得多。

这是一个更快的 dok 迭代，它利用了它的字典方法。 update 似乎和普通字典一样快。 get 大约比等效索引 (freq[row,col]) 快 3 倍。索引可能会用到get，但肯定有很多开销。

def fast_dok(rows, cols):
    freqs = dok_matrix((1000,1000))
    for row, col in zip(rows,cols):
         i = freqs.get((row,col),0)
         freqs.update({(row,col):i+1})
    return freqs

跳过 get，只做

         freqs.update({(row,col): 1)

甚至更快 - 比 defaultdict 示例的 defaultdict 更快，几乎与简单的字典初始化一样快 ({(r, c):1 for r,c in zip(rows, cols)})

Answer 2

您的测试不公平的原因有多种。首先，您将构建稀疏矩阵的开销包括在定时循环中。

其次，可以说更重要的是，您应该按照设计用途使用数据结构，同时对整个数组进行操作。也就是说，不是遍历行和列并每次都加 1，而是简单地向整个数组加 1。

为什么 lil_matrix 和 dok_matrix 与普通的字典相比这么慢？

Why are lil_matrix and dok_matrix so slow compared to common dict of dicts?

python

numpy

scipy