与常见的词典相比,为什么lil_matrix和dok_matrix如此之慢？

Question

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

LiL矩阵:

class scipy.sparse.lil_matrix(arg1,shape = None,dtype = None,copy = False)[source]基于行的链表稀疏矩阵

这是用于逐步构造稀疏矩阵的有效结构.

DoK矩阵:

class scipy.sparse.dok_matrix(arg1,shape = None,dtype = None,copy = False)[source]基于密钥的字典稀疏矩阵.

这是用于逐步构造稀疏矩阵的有效结构.

但是当我运行基准测试时,与构建值的字典字典(后来可以很容易地转换为稀疏矩阵)相比,后者的结果比使用任何稀疏矩阵模型快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

他们各自的时间减少了一半.消耗时间最多的是索引.因为+=它必须同时做a __getitem__和a __setitem__.

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

当我尝试csr用你的代码制作一个矩阵时,我得到一个:

/usr/lib/python2.7/dist-packages/scipy/sparse/compressed.py:690:SparseEfficiencyWarning:更改csr_matrix的稀疏结构是很昂贵的.lil_matrix效率更高.SparseEfficiencyWarning)

速度减慢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)

利用a 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)})一样快