Блог

Мне нужно решить операцию XOR для векторов с очень высокой размерностью (~ 30 000), чтобы вычислить расстояние Хэмминга. Например, мне нужно вычислить операцию XOR между одним вектором, полным False, с 16 редко расположенными True с каждой строкой матрицы 50’000×30’000.

На данный момент самый быстрый способ, который я нашел, — это не использовать 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-мерном.

Есть ли какое-либо решение? Я действительно борюсь здесь, спасибо за помощь!

Если ваш вектор очень разреженный (например, 16/30000), я бы, вероятно, просто полностью пропустил работу с разреженным xor.

 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))