如何加快构建一个非常大的稀疏矩阵,其中每一行只有一个对应于一列的非零元素,并且每列有相等数量(平均)的非零元素?
我有一个巨大的(稀疏)矩阵,大小为 N1
-by-N2
,例如大小为 1e8
-by-5e4
,其中每一行只包含一个非零元素,该元素是随机选择的,没有被 numpy.random.choice(numpy.arange(N2),size=N2,replace=False)
.
据我所知,构建矩阵的唯一方法是在 for
循环中运行 numpy.random.choice()
N1
次。由于 N1
非常大,为了加快速度,我使用了 scipy.weave
:
import numpy as np
from scipy import weave
from scipy.weave import converters
import scipy.sparse as sparse # Cython import
def weave_sparse(N1,N2,w):
conn_matrix = sparse.dok_matrix((N1,N2))
fac = lambda N : np.random.choice(np.arange(N), size=N, replace=False)[0]
code = """
int i;
py::tuple arg(1);
arg[0] = N2;
for(i=0;i<N1;i++) conn_matrix[i,(int) fac.call(arg)] = w;
"""
weave.inline(code,['conn_matrix','N1','N2', 'w', 'fac'],
compiler='gcc',extra_compile_args=['-std=c++11 -Ofast'],force=0)
return conn_matrix
不过,对于接近 1e6
的 N1
和超出代码的时间,它需要很长时间才能完成。我怀疑可能有更有效的方法来构建稀疏矩阵。在人类可读的时间内加速和构建矩阵的任何其他策略?
最佳答案
您不需要 weave
来提高效率。这是一个适合您的示例。我使用了较小的 N1
和 N2
值以便于检查结果。我还使用了 csr_matrix
,但任何 scipy 稀疏矩阵类型都应该在很少或没有变化的情况下工作。
In [50]: from scipy.sparse import csr_matrix
N1
、N2
和数组 w
基本上是输入; w
是一个长度为 N1
的数组。它包含将放入每一行的值。在这里,我用 1 填充 w
。
In [51]: N1 = 15
In [52]: N2 = 12
In [53]: w = np.empty(N1, dtype=int)
In [54]: w[:] = 1
现在创建csr_matrix
:
In [55]: rows = np.arange(N1)
In [56]: cols = np.random.randint(0, N2, size=N1)
In [57]: conn_matrix = csr_matrix((w, (rows, cols)), shape=(N1, N2), dtype=int)
.A
属性只是.toarray()
方法的快捷方式;它返回一个常规的 numpy 数组:
In [58]: conn_matrix.A
Out[58]:
array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]], dtype=int64)
关于python-2.7 - 快速构建一个非常大的稀疏矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38460050/