NumPy: counting sizes of row-wise intersections between two arrays

arrays, numpy, python, vectorization

Solution

Here is one approach that takes on the order of a second for inputs of size 100000 and 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)

Here's the idea: suppose each entry of `x` and `y` takes a value in some small set, say, `values = [1,3,6,9,11,15,28,40]`. Consider a row of `x`:

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

and a row of `y`:

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

We can represent `x[0]` as a sparse vector that is the same length as `values`. The `i`th entry will be one if the `i`th value appears in `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]

How many elements are in the intersection between `x_hat` and `y_hat`? It's simply the dot product: 3. The above code does just this, but in batch.

The function works with sparse matrices, and the result is a sparse matrix, in order to save memory. Note that a dense 100000 x 50000 array of int32s is already 20 gigabytes, which may or may not exceed your RAM. See here for help on working with sparse arrays.

I tested the above code by generating arrays `x` and `y` with:

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

It completed in 2 seconds on my 5-year-old machine with 24GB of main memory. Here, `1000` serves as the range of possible values that `x` and `y` can take on. Making it smaller means that the matrices involved will be less sparse, and the code will take longer.

Problem

I have 2 arrays filled by integers lower than 100. A number can't appear twice in a row. - Array1: nrow=100 000 ; ncol=5 - Array2: nrow=50 000 ; ncol=5 I'd like to create a 3rd array (Intersection) with the number of similar element between each row of Array1 and each row of 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 ``` Here is an example: ``` 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) ``` This naive solution with nested loops is very slow. How could I vectorize it ?

Original source