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

Question

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

LiL矩阵：

类scipy.sparse.lil_matrix（arg1，shape = None，dtype = None，copy =
False）[源]基于行的链表稀疏矩阵

这是用于增量构造稀疏矩阵的有效结构。

DoK矩阵：

类scipy.sparse.dok_matrix（arg1，shape = None，dtype = None，copy =
False）[源]基于密钥字典的稀疏矩阵。

这是用于增量构造稀疏矩阵的有效结构。

但是，当我运行基准测试与构建值字典字典（以后可以轻松地将其转换为稀疏矩阵）进行比较时，后者的速度比使用任何稀疏矩阵模型快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比普通的dict更喜欢吗？

Answer 1

当我将您更改+=为仅=用于2个稀疏数组时：

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

他们各自的时间减少了一半。消耗时间最多的是索引。使用+=它必须同时执行a__getitem__和a __setitem__。

当文档这么说dok并且lil更适合迭代构造时，它们意味着扩展其基础数据结构比其他格式更容易。

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

/usr/lib/python2.7/dist-
packages/scipy/sparse/compressed.py:690：SparseEfficiencyWarning：更改csr_matrix的稀疏结构非常昂贵。lil_matrix效率更高。稀疏效率警告）

速度降低30倍。

因此，速度要求与诸如之类的格式有关csr，而不与纯Python或numpy结构有关。

您可能想要查看Python代码，dok_matrix.__get_item__并dok_matrix.__set_item__查看这样做时会发生什么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)

利用adok是子类字典的事实。请注意，dok矩阵不是字典的字典。它的键是元组之类的(50,50)。

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

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

换句话说，由于您已经具有rowsandcols数组（或范围），因此请计算相应的data数组，然后构造稀疏数组。

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

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

现在，许多SO稀疏问题都来自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)}）一样快