NumPy: подсчет размеров пересечений строк между двумя массивами

Question

У меня есть 2 массива, заполненных целыми числами ниже 100. Число не может появляться дважды в строке.

• Array1: nrow = 100 000; ncol = 5
• Array2: nrow = 50 000; Ncol = 5

Я хотел бы создать 3-й массива (пересечения) с числом аналогичного элемента между каждой строкой array1 и каждой строкой array2.

def Intersection(array1, array2): 
    Intersection = np.empty([ array1.shape[0] , array2.shape[0] ], dtype=int8) 
    for i in range(0, array1.shape[0]): 
     for j in range(0, array2.shape[0]): 
      Intersection[i,j] = len(set(array1[i,]).intersection(array2[j,])) 
    return Intersection 

Вот пример:

array1 = np.array([[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [7,8,9,10,11] ]) 
array2 = np.array([[1, 3, 7, 20, 21], [1, 43, 104, 115, 116], [6,30,91,110,121] ]) 
#Expected result: 
array([[2, 1, 0], 
     [1, 0, 1], 
     [1, 0, 0]], dtype=int8) 

Это наивное решение с вложенными циклами происходит очень медленно. Как я мог векторизовать его?

Answer 1

Вот один подход, который берет на себя порядка секунды для входа размером 100000 и 50000:

import numpy as np 
import scipy.sparse 

def intersection_counts(x,y): 
    # find the size of the input arrays 
    n_x, n_d = x.shape 
    n_y, n_d = y.shape 

    # get a list of the unique values appearing in x and y, as well 
    # as a list of inverse indices (see docs for np.unique) 
    values, ix = np.unique(np.vstack((x,y)), return_inverse=True) 
    n_unique = len(values) 

    # reshape the inverse array. ix_x_hat will be an array the same size 
    # as x, where ix_x_hat[i,j] gives the index of x[i,j] in values. That 
    # is to say, values[ix_x_hat[i,j]] == x[i,j] 
    ix_hat = ix.reshape(-1, n_d) 
    ix_x_hat = ix_hat[:n_x] 
    ix_y_hat = ix_hat[n_x:] 

    # create a sparse matrix where entry [i,j] is 1 if and only if 
    # row i of x contains values[j] 
    x_hat = scipy.sparse.lil_matrix((n_x, n_unique), dtype=int) 
    x_hat[np.arange(n_x)[:,None], ix_x_hat] = 1 

    # create a sparse matrix where entry [i,j] is 1 if and only if 
    # row i of y contains values[j] 
    y_hat = scipy.sparse.lil_matrix((len(y), len(values)), dtype=int) 
    y_hat[np.arange(n_y)[:,None], ix_y_hat] = 1 

    # the dot product gives the solution 
    return x_hat.dot(y_hat.T) 

Вот идея: пусть каждая запись x и y принимает значение в каком-то небольшом наборе , скажем, values = [1,3,6,9,11,15,28,40]. Рассмотрим ряд x:

x[0] = [11, 6, 40, 1, 3] 

и ряд y:

y[0] = [3, 11, 6, 9, 15] 

Мы можем представить x[0] как разреженный вектор, который имеет ту же длину, как values. Запись i го будет один, если i ое значение появляется в x:

#   [1, 3, 6, 9,11,15,28,40] 
x_hat[0] = [1, 1, 1, 0, 1, 0, 0, 1] 
y_hat[0] = [0, 1, 1, 1, 1, 1, 0, 0] 

Сколько элементов в пересечении между x_hat и y_hat? Это просто точечный продукт: 3. Вышеприведенный код делает именно это, но в пакетном режиме.

Функция работает с разреженными матрицами, а результат является разреженной матрицей для сохранения памяти. Обратите внимание: плотный массив int32s размером 100000 x 50000 уже составляет 20 гигабайт, что может превышать или не превышать вашу оперативную память. См. here для получения справки по работе с разреженными массивами.

Я тестировал код выше, генерируя массивы x и y с:

x = np.random.randint(0,1000,(100000,5)) 
y = np.random.randint(0,1000,(50000,5)) 

Совершил за 2 секунды на моей 5-летней машины с 24 Гб оперативной памяти. Здесь 1000 служит в качестве диапазона возможных значений, которые могут принимать x и y. Уменьшение этого означает, что задействованные матрицы будут менее редкими, и код займет больше времени.