11

给定一个 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 中实现这个的想法，但我不知道这是否会带来好的结果。

提前致谢。

4

2 回答 2

13

稀疏矩阵乘法例程是直接用 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比矩阵的列数多一个条目，并且 columnj中的项目位于data[indptr[j]:indptr[j+1]]并且位于 rows 中indices[indptr[j]:indptr[j+1]]。

因此，要乘以稀疏列向量，您可以迭代列向量的data和indices，并且对于每一(d, r)对，提取矩阵的相应列并将其乘以d，即data[indptr[r]:indptr[r+1]] * d和indices[indptr[r]:indptr[r+1]]。

于 2013-09-03T19:13:52.117 回答
4

最近我有同样的问题。我是这样解决的。

def sparse_col_vec_dot(csc_mat, csc_vec):
    curr_mat = csc_mat.tocsr()
    ret curr_mat* csc_vec

这里的技巧是我们必须将矩阵的一个版本作为行表示，将另一个版本作为列表示。

于 2016-10-16T23:11:35.210 回答