提高Scipy稀疏矩阵乘法性能

Question

给定Scipy CSC稀疏矩阵"sm",其尺寸(170k x 170k)具有4.4亿个非零点,稀疏CSC矢量"v"(170k x 1)具有一些非零点,有什么可以是为提高操作性能而做的:

resul = sm.dot(v)

？

目前大约需要1秒钟.初始化矩阵作为CSR将时间增加到3秒,因此CSC表现更好.

SM是产品之间相似性的矩阵,V是表示用户购买或点击的产品的向量.所以对于每个用户来说,sm都是一样的.

我使用的是Ubuntu 13.04,Intel i3 @ 3.4GHz,4核心.

研究SO我读了关于Ablas包的内容.我输入了终端:

~$ ldd /usr/lib/python2.7/dist-packages/numpy/core/_dotblas.so

结果导致:

    linux-vdso.so.1 =>  (0x00007fff56a88000)
    libblas.so.3 => /usr/lib/libblas.so.3 (0x00007f888137f000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f8880fb7000)
    libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f8880cb1000)
    /lib64/ld-linux-x86-64.so.2 (0x00007f888183c000)

据我所知,这意味着我已经在使用Ablas的高性能套件.我仍然不确定这个软件包是否已经实现了并行计算,但它看起来并没有.

多核处理有助于提升性能吗？如果是这样,是否有任何库可能有助于python？

我也在考虑在Cython中实现这个的想法,但我不知道这是否会带来好的结果.

提前致谢.

Answer 1

稀疏矩阵乘法例程直接用C++编写,只要快速浏览一下源代码,就不会有任何优化库的钩子.此外,它似乎没有利用第二矩阵是最小化计算的向量这一事实.因此,您可以通过访问稀疏矩阵的内容并自定义乘法算法来加快速度.下面的代码在纯Python/Numpy中这样做,如果向量真的有"一些非空点",它与scipy的C++代码的速度相匹配:如果你在Cython中实现它,速度的提升应该是显而易见的:

def sparse_col_vec_dot(csc_mat, csc_vec):
    # row numbers of vector non-zero entries
    v_rows = csc_vec.indices
    v_data = csc_vec.data
    # matrix description arrays
    m_dat = csc_mat.data
    m_ind = csc_mat.indices
    m_ptr = csc_mat.indptr
    # output arrays
    sizes = m_ptr.take(v_rows+1) - m_ptr.take(v_rows)
    sizes = np.concatenate(([0], np.cumsum(sizes)))
    data = np.empty((sizes[-1],), dtype=csc_mat.dtype)
    indices = np.empty((sizes[-1],), dtype=np.intp)
    indptr = np.zeros((2,), dtype=np.intp)

    for j in range(len(sizes)-1):
        slice_ = slice(*m_ptr[[v_rows[j] ,v_rows[j]+1]])
        np.multiply(m_dat[slice_], v_data[j], out=data[sizes[j]:sizes[j+1]])
        indices[sizes[j]:sizes[j+1]] = m_ind[slice_]
    indptr[-1] = len(data)
    ret = sps.csc_matrix((data, indices, indptr),
                         shape=csc_vec.shape)
    ret.sum_duplicates()

    return ret

快速解释发生了什么:CSC矩阵在三个线性阵列中定义:

• data 包含非零条目,以列主要顺序存储.
• indices 包含非零条目的行.
• indptr有一个条目多于矩阵的列数,列中的项目在行j中data[indptr[j]:indptr[j+1]]并且在行中indices[indptr[j]:indptr[j+1]].

因此,通过一个稀疏列向量相乘,可以遍历data和indices列向量,并且对于每个(d, r)对,提取矩阵的对应的列,并通过乘以d,即data[indptr[r]:indptr[r+1]] * d和indices[indptr[r]:indptr[r+1]].