如何用面具加速 numpy 点积？

Question

我有 2 个 numpy 数组，m1 和 m2，其中 m1 是大小 (nx1)，m2 是大小 (1xn)，我想执行乘法 m1.dot(m2) 产生大小为 (nxn)

的矩阵 m

我想通过仅使用 m1 和 m2 中最高的 k 个元素并使所有其他元素为 0（所有元素均为正）来计算近似值 m_approx。

我正在尝试加快乘法运算，因为大小 n 对我来说很大 (~10k)。我想选择一个小的 k 说 100 并真正加快乘法。我尝试使用 numpy 稀疏矩阵，它确实使点积更快，但将 m1 和 m2 转换为稀疏向量非常慢。我怎样才能做到这一点？我觉得戴口罩可能是实现这一目标的一种方式，但不确定如何实现？

Answer 1

这可以使用 np.argpartition to get the indices of largest k elements and np.ix_ 来解决，用于选择和设置从 m1 和 m2 中选择的元素的点积。因此，我们基本上有两个阶段来实现这一点，如下所述。

首先，获取m1和m2中最大k个元素对应的索引，像这样-

m1_idx = np.argpartition(-m1,k,axis=0)[:k].ravel()
m2_idx = np.argpartition(-m2,k)[:,:k].ravel()

最后，设置输出数组。使用 np.ix_ 分别沿行和列广播 m1 和 m2 索引，以选择要设置的输出数组中的元素。接下来，计算 m1 和 m2 中最高 k 元素之间的点积，这可以使用 [=] 的索引从 m1 和 m2 中获得32=] 和 m2_idx，像这样 -

out = np.zeros((n,n))
out[np.ix_(m1_idx,m2_idx)] = np.dot(m1[m1_idx],m2[:,m2_idx])

让我们用一个示例运行验证实现，方法是运行将其与另一个实现进行比较，该实现将较低的 n-k 元素显式设置为 0s in m1, m2 然后进行点积。这是一个示例运行执行检查 -

1) 输入：

In [170]: m1
Out[170]: 
array([[ 0.26980423],
       [ 0.30698416],
       [ 0.60391089],
       [ 0.73246763],
       [ 0.35276247]])

In [171]: m2
Out[171]: array([[ 0.30523552, 0.87411242, 0.01071218, 0.81835438, 0.21693231]])

In [172]: k = 2

2) 运行建议实施：

In [173]: # Proposed solution code
     ...: m1_idx = np.argpartition(-m1,k,axis=0)[:k].ravel()
     ...: m2_idx = np.argpartition(-m2,k)[:,:k].ravel()
     ...: out = np.zeros((n,n))
     ...: out[np.ix_(m1_idx,m2_idx)] = np.dot(m1[m1_idx],m2[:,m2_idx])
     ...:

3) 使用替代实现来获取输出：

In [174]: # Explicit setting of lower n-k elements to zeros for m1 and m2
     ...: m1[np.argpartition(-m1,k,axis=0)[k:]] = 0
     ...: m2[:,np.argpartition(-m2,k)[:,k:].ravel()] = 0
     ...: 

In [175]: m1  # Verify m1 and m2 have lower n-k elements set to 0s
Out[175]: 
array([[ 0.        ],
       [ 0.        ],
       [ 0.60391089],
       [ 0.73246763],
       [ 0.        ]])

In [176]: m2
Out[176]: array([[ 0.       , 0.87411242, 0.        , 0.81835438, 0.        ]])

In [177]: m1.dot(m2)  # Use m1.dot(m2) to directly get output. This is expensive.
Out[177]: 
array([[ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.52788601,  0.        ,  0.49421312,  0.        ],
       [ 0.        ,  0.64025905,  0.        ,  0.59941809,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ]])

4) 验证我们提出的实施方案：

In [178]: out   # Print output from proposed solution obtained earlier
Out[178]: 
array([[ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.52788601,  0.        ,  0.49421312,  0.        ],
       [ 0.        ,  0.64025905,  0.        ,  0.59941809,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ]])

如何用面具加速 numpy 点积？

How to speed up numpy dot product with masks?

arrays

performance

numpy

matrix-multiplication