查找两个二维数组中匹配行的索引

Question

假设我有两个2-D数组,如下所示:

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)

每个数组中的某些行具有相应的行,该行在另一个数组中按值(但不一定是索引)匹配,而某些行则没有.

我想找到一种有效的方法来返回两个对应于匹配行的数组中的索引对.如果他们是元组我会期望回来

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

Answer 1

这是一个完整的numpy解决方案 - 不一定比迭代Python更好.它仍然需要考虑所有组合.

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

中间数组是(5,5,4).将np.all其简化为:

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)

其余的只是提取指数 True

在原油测试中,这次是47.8 us; 另一个答案L1是38.3我们的字典; 还有第三个在496 us处有一个双循环.

Answer 2

我想不出一个特定的方式来做这件事,但这就是我对常规列表的处理方式:

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

您可以使用void数据类型技巧在两个数组的行上使用1D函数.a_view并且b_view是1D向量,每个条目代表一个完整的行.然后,我选择对数组进行排序,并用于np.searchsorted查找该数组中其他数组的项.如果我们排序的数组具有长度m而另一个具有长度n,则排序需要时间m * log(m),并且二进制搜索np.searchsorted确实需要时间n * log(m),总计为(n + m) * log(m).因此,您希望对两个数组中最短的数组进行排序:

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

使用a和b您的两个示例数组:

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

在我的系统中,字典方法在测试数据的时间约为22 us时更快,但对于1000x4的数组,这种numpy方法比纯Python方法(483 us vs 2.54 ms)快约6倍.