scipy 稀疏矩阵与 cython

Question

我需要在一个叫做 Cython 的方法里对一个 scipy 的稀疏矩阵进行一系列操作。

为了高效地进行这些操作，我需要使用 lil_matrix 这种表示方式。lil（链表稀疏矩阵）在 Python 中的数据表示是用 列表的列表，而且每个列表的长度可以不同。

我该如何高效地将一个不同长度的列表的列表传递给 Cython（而不进行复制）？有没有其他方法可以在 Cython 中访问 lil 矩阵？

Answer 1

下面的例子展示了如何遍历一个 lil_matrix，并计算每一行的总和。

需要注意的是，我没有做任何声明，尽管这样做非常快，因为 Cython 已经对像列表这样的内置类型进行了优化。下面也展示了时间的测量结果……

import time

import numpy as np
cimport numpy as np

from scipy.sparse import lil_matrix

cdef iter_over_lil_matrix(m):
    cdef list sums, data_row
    sums = []
    for data_row in m.data:
        s = 0
        for value in data_row:
            s += value
        sums.append(s)
    return sums

def main():
    a = np.random.random((1e4*1e4))
    a[a>0.1] = 0
    a = a.reshape(1e4,1e4)
    m = lil_matrix(a)

    t0 = time.clock()
    sums = iter_over_lil_matrix(m)
    t1 = time.clock()
    print 'Cython lil_matrix Time', t1-t0

    t0 = time.clock()
    array_sums = a.sum(axis=1)
    t1 = time.clock()
    print 'Numpy ndarray Time', t1-t0

    t0 = time.clock()
    lil_sums = m.sum(axis=1)
    t1 = time.clock()
    print 'lil_matrix Time', t1-t0

    mcsr = m.tocsr()
    t0 = time.clock()
    csr_sums = mcsr.sum(axis=1)
    t1 = time.clock()
    print 'csr_matrix Time', t1-t0

    assert np.allclose(array_sums, sums)
    assert np.allclose(array_sums, np.asarray(lil_sums).flatten())
    assert np.allclose(array_sums, np.asarray(csr_sums).flatten())

时间以秒为单位 - 速度仅比超级优化的 NumPy 慢大约 2 倍 :D，远比 lil_matrix.sum() 方法快，因为它在计算之前会转换为 csr_matrix()，这一点得到了 @hpaulj 的澄清，并且下面的结果也证实了这一点。需要注意的是，csr_matrix.sum() 在列上的计算速度几乎比密集求和快一个数量级。

Cython lil_matrix Time 0.183935034665
Numpy ndarray Time 0.106583238273
lil_matrix Time 2.47158218631
csr_matrix Time 0.0140050888745

会让代码变慢的因素：

• 使用 for i in range(len(m.data)): 和 data_row = m.data[i]
• 声明像 np.ndarray[object, ndim=1] data 这样的缓冲区，并用 data=m.data 赋值

没有影响的因素：

• boundscheck 或 wraparound