Finden Indizes entsprechende Zeilen in zwei 2-D-Arrays

Question

Angenommen, I zwei 2-D-Arrays wie folgt:

array([[3, 3, 1, 0], 
     [2, 3, 1, 3], 
     [0, 2, 3, 1], 
     [1, 0, 2, 3], 
     [3, 1, 0, 2]], dtype=int8) 

array([[0, 3, 3, 1], 
     [0, 2, 3, 1], 
     [1, 0, 2, 3], 
     [3, 1, 0, 2], 
     [3, 3, 1, 0]], dtype=int8) 

Einige Zeilen in jedem Array eine entsprechende Reihe, die von Wert übereinstimmt (aber nicht unbedingt durch Index) in dem anderen Array, und einige nicht.

Ich möchte eine effiziente Möglichkeit finden, Paare von Indizes in den zwei Arrays, die übereinstimmenden Zeilen entsprechen, zurückzugeben. Wenn sie Tupel sein wäre, würde ich

(0,4) 
(2,1) 
(3,2) 
(4,3) 

Answer 1

Diese ist eine alle numpy Lösung - das ist nicht unbedingt besser als eine iterative Python. Es muss immer noch alle Kombinationen betrachten.

In [53]: np.array(np.all((x[:,None,:]==y[None,:,:]),axis=-1).nonzero()).T.tolist() 
Out[53]: [[0, 4], [2, 1], [3, 2], [4, 3]] 

Das Zwischenfeld ist (5,5,4). Die np.all reduziert sie auf:

array([[False, False, False, False, True], 
     [False, False, False, False, False], 
     [False, True, False, False, False], 
     [False, False, True, False, False], 
     [False, False, False, True, False]], dtype=bool) 

Der Rest nur ist, um die Indizes zu extrahieren, wo diese True

In rohen Tests ist, dieses mal bei 47.8 uns; die andere Antwort mit dem L1 Wörterbuch bei 38,3 us; und ein dritter mit einer Doppelschleife bei 496 us.

Answer 2

Ich kann nicht denken Sie an eine numpy spezifische Art und Weise zurück erwarten, es zu tun, aber hier ist, was ich mit regelmäßigen Listen tun würde:

>>> L1= [[3, 3, 1, 0], 
...  [2, 3, 1, 3], 
...  [0, 2, 3, 1], 
...  [1, 0, 2, 3], 
...  [3, 1, 0, 2]] 
>>> L2 = [[0, 3, 3, 1], 
...  [0, 2, 3, 1], 
...  [1, 0, 2, 3], 
...  [3, 1, 0, 2], 
...  [3, 3, 1, 0]] 
>>> L1 = {tuple(row):i for i,row in enumerate(L1)} 
>>> answer = [] 
>>> for i,row in enumerate(L2): 
... if tuple(row) in L1: 
...  answer.append((L1[tuple(row)], i)) 
... 
>>> answer 
[(2, 1), (3, 2), (4, 3), (0, 4)] 

Answer 3

Sie können den void-Datentyp-Trick verwenden, um 1D-Funktionen in den Zeilen Ihrer beiden Arrays zu verwenden. a_view und b_view sind 1D-Vektoren, wobei jeder Eintrag eine vollständige Zeile darstellt. Ich habe dann gewählt, ein Array zu sortieren und np.searchsorted zu verwenden, um die Elemente des anderen Arrays in diesem zu finden. Wenn das Array, das wir sortieren, die Länge m hat und das andere die Länge n hat, dauert die Sortierung m * log(m), und die binäre Suche nach np.searchsorted dauert n * log(m), also insgesamt (n + m) * log(m). Sie wollen daher die kürzeste der beiden Arrays sortieren:

def find_rows(a, b): 
    dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1])) 

    a_view = np.ascontiguousarray(a).view(dt).ravel() 
    b_view = np.ascontiguousarray(b).view(dt).ravel() 

    sort_b = np.argsort(b_view) 
    where_in_b = np.searchsorted(b_view, a_view, 
           sorter=sort_b) 
    where_in_b = np.take(sort_b, where_in_b) 
    which_in_a = np.take(b_view, where_in_b) == a_view 
    where_in_b = where_in_b[which_in_a] 
    which_in_a = np.nonzero(which_in_a)[0] 
    return np.column_stack((which_in_a, where_in_b)) 

Mit a und b Ihre zwei Probenarrays:

In [14]: find_rows(a, b) 
Out[14]: 
array([[0, 4], 
     [2, 1], 
     [3, 2], 
     [4, 3]], dtype=int64) 

In [15]: %timeit find_rows(a, b) 
10000 loops, best of 3: 29.7 us per loop 

Auf meinem System die Wörterbuch Ansatz Uhren schneller bei etwa 22 uns für Ihren Test Daten, aber mit Arrays von 1000x4, ist dieser numplige Ansatz ungefähr 6x schneller als der reine Python (483 us vs 2.54 ms).