Trovare in modo efficiente intersezioni di righe di due array numpy 2-D

Question

Sto cercando di trovare un modo efficiente per trovare intersezioni di riga di due np.arrays.

Due matrici hanno le stesse forme e non possono verificarsi valori duplicati in ogni riga.

Ad esempio:

import numpy as np 

a = np.array([[2,5,6], 
       [8,2,3], 
       [4,1,5], 
       [1,7,9]]) 

b = np.array([[2,3,4], # one element(2) in common with a[0] -> 1 
       [7,4,3], # one element(3) in common with a[1] -> 1 
       [5,4,1], # three elements(5,4,1) in common with a[2] -> 3 
       [7,6,9]]) # two element(9,7) in common with a[3] -> 2 

mio output desiderato è: np.array([1,1,3,2])

E 'facile da fare questo con un ciclo:

def get_intersect1ds(a, b): 
    result = np.empty(a.shape[0], dtype=np.int) 
    for i in xrange(a.shape[0]): 
     result[i] = (len(np.intersect1d(a[i], b[i]))) 
    return result 

Risultato:

>>> get_intersect1ds(a, b) 
array([1, 1, 3, 2]) 

Ma esiste un modo più efficiente per farlo?

Answer 1

Se non si hanno i duplicati all'interno di una riga si può provare a replicare quello np.intersect1d fa sotto il cofano (vedere il codice sorgente here):

>>> c = np.hstack((a, b)) 
>>> c 
array([[2, 5, 6, 2, 3, 4], 
     [8, 2, 3, 7, 4, 3], 
     [4, 1, 5, 5, 4, 1], 
     [1, 7, 9, 7, 6, 9]]) 
>>> c.sort(axis=1) 
>>> c 
array([[2, 2, 3, 4, 5, 6], 
     [2, 3, 3, 4, 7, 8], 
     [1, 1, 4, 4, 5, 5], 
     [1, 6, 7, 7, 9, 9]]) 
>>> c[:, 1:] == c[:, :-1] 
array([[ True, False, False, False, False], 
     [False, True, False, False, False], 
     [ True, False, True, False, True], 
     [False, False, True, False, True]], dtype=bool) 
>>> np.sum(c[:, 1:] == c[:, :-1], axis=1) 
array([1, 1, 3, 2]) 

Answer 2

non riesco a pensare a una soluzione di pura-NumPy pulita, ma il seguente suggerimento dovrebbe velocizzare le cose, potenzialmente in modo drammatico:

1. uso numba. E 'semplice come decorare la vostra funzione get_intersect1ds con @autojit
2. passaggio assume_unique = True quando si chiama intersect1d

Answer 3

Questa risposta potrebbe non essere praticabile, perché se l'ingresso ha forma (N, M), si genera una matrice intermedia con la dimensione (N, M, M), ma è sempre divertente vedere cosa si può fare con la radiodiffusione:

In [43]: a 
Out[43]: 
array([[2, 5, 6], 
     [8, 2, 3], 
     [4, 1, 5], 
     [1, 7, 9]]) 

In [44]: b 
Out[44]: 
array([[2, 3, 4], 
     [7, 4, 3], 
     [5, 4, 1], 
     [7, 6, 9]]) 

In [45]: (np.expand_dims(a, -1) == np.expand_dims(b, 1)).sum(axis=-1).sum(axis=-1) 
Out[45]: array([1, 1, 3, 2]) 

per grandi array, il metodo potrebbe essere reso più memoria-friendly effettuando l'operazione in batch.