dzh*_*lil 6 python indexing scipy sparse-matrix
即使一切似乎都是矢量化的,下面的代码运行得太慢了.
from numpy import *
from scipy.sparse import *
n = 100000;
i = xrange(n); j = xrange(n);
data = ones(n);
A=csr_matrix((data,(i,j)));
x = A[i,j]
问题似乎是索引操作是作为python函数实现的,并且调用A[i,j]结果导致以下分析输出
500033 function calls in 8.718 CPU seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
100000 7.933 0.000 8.156 0.000 csr.py:265(_get_single_element)
1 0.271 0.271 8.705 8.705 csr.py:177(__getitem__)
(...)
也就是说,python函数_get_single_element被调用100000次,这实在是效率低下.为什么不在纯C中实现？有没有人知道解决这个限制的方法,并加快上述代码？我应该使用不同的稀疏矩阵类型吗？
您可以使用A.diagonal()更快速地检索对角线(0.0009秒与我的机器上的3.8秒).但是,如果您想进行仲裁索引,那么这是一个更复杂的问题,因为您没有使用切片作为索引列表._get_single_element函数被调用100000次,因为它只是遍历传递给它的迭代器(i和j).切片将是A [30:60,10]或类似的东西.
另外,csr_matrix(eye(n,n))为了简单起见,我会使用与迭代器相同的矩阵.
好的,既然你的问题确实是能够快速访问大量随机元素,我会尽我所能回答你的问题.
答案很简单:没人接触过它.从我所看到的Scipy稀疏矩阵模块领域仍有大量工作要做.在C中实现的一部分是不同稀疏矩阵格式之间的转换.
您可以尝试实际潜入稀疏矩阵模块并尝试加速它们.我这样做了,并且当使用csr矩阵尝试使用上面的代码进行随机访问时,能够将时间缩短到不到原来的三分之一.我必须直接访问_get_single_element并显着减少代码,包括取出绑定检查.
然而,使用lil_matrix仍然更快(尽管初始化矩阵的速度较慢),但我不得不使用列表解析进行访问,因为没有为您正在进行的索引类型设置lil矩阵.使用csr_matrix的列表推导仍然使lil矩阵方法顺便前进.最终,lil矩阵更快地访问随机元素,因为它没有被压缩.
使用原始形式的lil_matrix运行的时间大约是上面列出的代码的五分之一.如果我取出一些绑定的检查并直接调用lil_matrix的_get1()方法,我可以将时间进一步缩短约原始时间的7%.为了清楚起见,速度从3.4-3.8秒增加到大约0.261秒.
最后,我尝试创建自己的函数,直接访问lil矩阵的数据,避免重复的函数调用.这个时间约为0.136秒.这没有利用被排序的数据,这是另一种潜在的优化(特别是如果您访问同一行上的许多元素).
如果你想要比那更快,你可能必须编写自己的C代码稀疏矩阵实现.
好吧,如果你打算访问很多元素,我建议使用lil矩阵,但这完全取决于你需要做什么.例如,你还需要乘以矩阵吗？请记住,矩阵之间的更改至少有时(在某些情况下)非常快,因此不排除更改为不同的矩阵格式以执行不同的操作.
如果您不需要在矩阵上进行任何代数运算,那么也许您应该使用defaultdict或类似的东西.defaultdicts的危险在于,每当要求一个元素不在dict中时,它会将该项设置为默认值并存储它以便可能出现问题.