我有一个O(N)NxN scipy.sparse.csr_matrix
的集合,每个稀疏矩阵都有N个元素的集合。我想把所有这些矩阵加在一起得到一个规则的NxN numpy数组。(N是1000的数量级)。矩阵中非零元素的排列方式是这样的,结果的和肯定不是稀疏的(实际上没有零元素)。
现在我正在做
reduce(lambda x,y: x+y,[m.toarray() for m in my_sparse_matrices])
这是可行的,但有点慢:当然,在那里进行的无意义的零处理的数量是绝对可怕的。
有更好的方法吗?在docs中没有什么对我来说是明显的。
**更新:**根据user 545424的建议,我尝试了另一种方法,即对稀疏矩阵求和,并将稀疏矩阵求和为密集矩阵。下面的代码显示了在可比时间内运行的所有方法(Python 2.6.6在amd 64 Debian上/Squeeze在四核i7上)
import numpy as np
import numpy.random
import scipy
import scipy.sparse
import time
N=768
S=768
D=3
def mkrandomsparse():
m=np.zeros((S,S),dtype=np.float32)
r=np.random.random_integers(0,S-1,D*S)
c=np.random.random_integers(0,S-1,D*S)
for e in zip(r,c):
m[e[0],e[1]]=1.0
return scipy.sparse.csr_matrix(m)
M=[mkrandomsparse() for i in xrange(N)]
def plus_dense():
return reduce(lambda x,y: x+y,[m.toarray() for m in M])
def plus_sparse():
return reduce(lambda x,y: x+y,M).toarray()
def sum_dense():
return sum([m.toarray() for m in M])
def sum_sparse():
return sum(M[1:],M[0]).toarray()
def sum_combo(): # Sum the sparse matrices 'onto' a dense matrix?
return sum(M,np.zeros((S,S),dtype=np.float32))
def benchmark(fn):
t0=time.time()
fn()
t1=time.time()
print "{0:16}: {1:.3f}s".format(fn.__name__,t1-t0)
for i in xrange(4):
benchmark(plus_dense)
benchmark(plus_sparse)
benchmark(sum_dense)
benchmark(sum_sparse)
benchmark(sum_combo)
print
并注销
plus_dense : 1.368s
plus_sparse : 1.405s
sum_dense : 1.368s
sum_sparse : 1.406s
sum_combo : 1.039s
尽管您可以通过改变N、S、D参数,使一种方法或另一种方法领先2倍左右......但是,考虑到可以跳过的零加法次数,您希望看到的数量级改进是无法比拟的。
5条答案
按热度按时间9o685dep1#
我想我已经找到了一种方法,如果你的矩阵非常稀疏,可以把它加速到原来的10倍。
ubby3x7f2#
@user545424已经发布了一个可能是最快的解决方案。本着同样的精神,更容易阅读,~同样的速度...**nonzero()**有各种各样有用的应用程序。
gkl3eglg3#
在转换成密集矩阵之前,你不能把它们加在一起吗?
d5vmydt94#
这并不是一个完整的答案(我也希望看到更详细的答案),但通过不创建中间结果,您可以轻松获得两个或更多的改进因素:
在我的机器(YMMV)上,这是最快的计算。通过将求和放在
()
而不是[]
中,我们在求和之前构造了一个生成器而不是整个列表。b0zn9rqh5#
转换为二维数组并使用内置的稀疏矩阵乘法。这比@user545424的方法更快。