python - 在 python 中将稀疏向量添加到稀疏数组太慢

Question

我有一个稀疏矩阵，我想向它添加一个稀疏向量。我尝试过不同的稀疏格式，包括 csr、csc、lil、coo，以及将稀疏向量添加到稀疏矩阵的不同方法，包括 vstack 和 concatenate。

所有的方式和格式结果都非常慢。但是当我将向量转换为密集格式(通过 todense() )并将其附加到密集矩阵(特别是 numpy.ndarray )时，它很快就完成了。为什么？是否有我缺少的技巧或合适的格式？

这是我尝试使用“coo”格式时的代码:

from scipy.sparse import coo_matrix, rand
from time import time as timer
from numpy import array, concatenate, empty

### sparse appending in coo way ####
def sparse_append(A):
    dim = A.shape[1]
    mat = coo_matrix((0, dim))

    sparse_addtime = 0

    for vector in A:
        st = timer() 

        row = coo_matrix(vector)
        newdata = concatenate((mat.data, row.data))
        newrows = concatenate((mat.row, row.row + mat.shape[0]))
        newcols = concatenate((mat.col, row.col))

        mat = coo_matrix((newdata, (newrows, newcols)), shape = ((mat.shape)[0]+1, (mat.shape)[1]))

        et = timer() 
        sparse_addtime += et-st

    return sparse_addtime

#### dense append ####
def dense_append(A):
    dim = A.shape[1]
    mat = empty([0,dim])

    dense_addtime = 0

    for vector in A:
        st = timer()
        mat = concatenate((mat,vector))
        et = timer()
        dense_addtime += et-st

    return dense_addtime



### main ####
if __name__ == '__main__':
    dim = 400
    n = 200

    A = rand(n, dim, density = 0.1, format='lil')
    B = A.todense() #numpy.ndarray

    t1 = sparse_append(A)
    t2 = dense_append(B)

    print t1, t2

感谢任何帮助。

Answer 1

稀疏加法代码中最慢的部分是行转换。

row = coo_matrix(vector)

这大约占用了我运行它时 65% 的时间。这是因为它需要更改存储数据的存储格式。另一个较慢的部分是创建矩阵。

mat = coo_matrix((newdata, (newrows, newcols)), shape = ((mat.shape)[0]+1, (mat.shape)[1]))

这又占用了 30% 的时间。每次执行此操作时，您都在复制所有数据并分配一堆内存。添加行的最有效方法是修改矩阵，尤其是当它们已经是 lil 格式时。如果您一开始就知道矩阵的维度，则可以从一开始就创建具有正确形状的矩阵。稀疏格式是内存高效的，空行不是问题。否则，您可以使用 set_shape 每次都增加维度。

from scipy.sparse import lil_matrix, rand
from time import time as timer
from numpy import array, concatenate, empty

### sparse appending ####
def sparse_append(A):
    dim = A.shape[1]
    mat = lil_matrix(A.shape, dtype = A.dtype)

    sparse_addtime = 0
    i = 0
    for vector in A:
        st = timer()

        mat[i] = vector
        i += 1
        et = timer() 
        sparse_addtime += et-st

    return sparse_addtime



#### dense append ####
def dense_append(A):
    dim = A.shape[1]
    mat = empty([0,dim])

    dense_addtime = 0

    for vector in A:
        st = timer()
        mat = concatenate((mat,vector))
        et = timer()
        dense_addtime += et-st

    return dense_addtime



### main ####
if __name__ == '__main__':
    dim = 400
    n = 200

    A = rand(n, dim, density = 0.1, format='lil')
    B = A.todense() #numpy.ndarray

    t1 = sparse_append(A)
    t2 = dense_append(B)

    print t1, t2

像这样运行代码，我从稀疏加法中获得了更好的时间。