有没有办法对scipy.sparse矩阵进行快速布尔运算？

Question

我必须在高维（~30000）向量上解一个异或运算来计算汉明距离。例如，我需要计算一个向量与16个向量之间的异或运算，其中每行50'000x30'000矩阵中都有16个零星的True

到目前为止，我发现的最快的方法不是使用scipy.sparse，而是对每行使用简单的^操作

这：

l1distances=(self.hashes[index,:]^self.hashes[all_points,:]).sum(axis=1)

正好比这个快十倍：

sparse_hashes = scipy.sparse.csr_matrix((self.hashes)).astype('bool')
for i in range(all_points.shape[0]):
    l1distances[0,i]=(sparse_hashes[index]-sparse_hashes[all_points[i]]).sum()

但是十倍的速度仍然相当慢，因为从理论上讲，拥有16个激活的稀疏向量应该使计算与拥有16维向量相同

有什么解决办法吗？我在这里真的很挣扎，谢谢你的帮助

Answer 1

如果你的向量是高度稀疏的（比如16/30000），我可能会完全跳过对稀疏异或的处理

from scipy import sparse
import numpy as np
import numpy.testing as npt

matrix_1 = sparse.random(10000, 100, density=0.1, format='csc')
matrix_1.data = np.ones(matrix_1.data.shape, dtype=bool)

matrix_2 = sparse.random(1, 100, density=0.1, format='csc', dtype=bool)
vec = matrix_2.A.flatten()

# Pull out the part of the sparse matrix that matches the vector and sum it after xor
matrix_xor = (matrix_1[:, vec].A ^ np.ones(vec.sum(), dtype=bool)[np.newaxis, :]).sum(axis=1)

# Sum the part that doesnt match the vector and add it
l1distances = matrix_1[:, ~vec].sum(axis=1).A.flatten() + matrix_xor

# Double check that I can do basic math
npt.assert_array_equal(l1distances, (matrix_1.A ^ vec[np.newaxis, :]).sum(axis=1))