我想迭代构建稀疏矩阵,并注意到根据 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.
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 比普通字典更喜欢字典的用例?
最佳答案
当我将 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)}
)
关于python - 为什么 lil_matrix 和 dok_matrix 与普通的字典相比这么慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27770906/