蟒蛇numpy的加快2D重复的搜索

Question

我需要找到重复的2D numpy的阵列。因此，我想要一个与输入相同长度的列表，指向相应值的第一次出现。例如，数组[[1,0,0]，[1,0,0]，[2,3,4]]具有两个相等的元素0和1.该方法应返回[0,0,2]（请参阅下面的代码中的例子）。 以下代码正在运行，但对于大型阵列来说速度很慢。

import numpy as np 


def duplicates(ar): 
    """ 
    Args: 
     ar (array_like): array 

    Returns: 
     list of int: int is pointing to first occurence of unique value 
    """ 
    # duplicates array: 
    dup = np.full(ar.shape[0], -1, dtype=int) 
    for i in range(ar.shape[0]): 
     if dup[i] != -1: 
      # i is already found to be a 
      continue 
     else: 
      dup[i] = i 
     for j in range(i + 1, ar.shape[0]): 
      if (ar[i] == ar[j]).all(): 
       dup[j] = i 
    return dup 


if __name__ == '__main__': 
    n = 100 
    # shortest extreme for n points 
    a1 = np.array([[0, 1, 2]] * n) 
    assert (duplicates(a1) == np.full(n, 0)).all(), True 

    # longest extreme for n points 
    a2 = np.linspace(0, 1, n * 3).reshape((n, 3)) 
    assert (duplicates(a2) == np.arange(0, n)).all(), True 

    # test case 
    a3 = np.array([[1, 0, 0], [1, 0, 0], [2, 3, 4]]) 
    assert (duplicates(a3) == [0, 0, 2]).all(), True 

任何想法如何加快过程（例如避免第二个循环）或替代实现？ 干杯

Answer 1

这里有一个量化的方法 -

def duplicates_1(a): 
    sidx = np.lexsort(a.T) 
    b = a[sidx] 

    grp_idx0 = np.flatnonzero((b[1:] != b[:-1]).any(1))+1 
    grp_idx = np.concatenate(([0], grp_idx0, [b.shape[0] ])) 
    ids = np.repeat(range(len(grp_idx)-1), np.diff(grp_idx)) 
    sidx_mapped = argsort_unique(sidx) 
    ids_mapped = ids[sidx_mapped] 

    grp_minidx = sidx[grp_idx[:-1]] 
    out = grp_minidx[ids_mapped] 
    return out 

使用的array-view，使我们在1D水平工作的概念，这里的第一种方法的改进 -

def duplicates_1_view1D(a): 
    a1D = view1D(a) 
    sidx0 = a1D.argsort() 
    b0 = a1D[sidx0] 

    N = len(b0) 
    grp_idx0 = np.concatenate(([0], np.flatnonzero(b0[1:] != b0[:-1])+1, [N])) 
    ids0 = np.repeat(range(len(grp_idx0)-1), np.diff(grp_idx0)) 
    sidx_mapped0 = argsort_unique(sidx0) 
    ids_mapped0 = ids0[sidx_mapped0] 

    grp_minidx0 = sidx0[grp_idx0[:-1]] 
    out0 = grp_minidx0[ids_mapped0] 
    return out0 

辅助功能 -

# https://stackoverflow.com/a/44999009/ @Divakar 
def view1D(a): # a is array 
    a = np.ascontiguousarray(a) 
    void_dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1])) 
    return a.view(void_dt).ravel() 

# https://stackoverflow.com/a/43411559/ @Divakar 
def argsort_unique(idx): 
    n = idx.size 
    sidx = np.empty(n,dtype=int) 
    sidx[idx] = np.arange(n) 
    return sidx 

Answer 2

你在做什么，你需要在每一个可能的配对比较N行，每个长度为M的，对彼此。这意味着至多它可以扩展为O(N^2 * M)，在没有重复的情况下。

更好的方法是散列的每一行。如果散列比例需要的时间为O(M)那么这应该按照O(N * M)的比例缩放。你可以做到这一点的字典：

def duplicates(ar): 
    """ 
    Args: 
     ar (array_like): array 

    Returns: 
     list of int: int is pointing to first occurence of unique value 
    """ 
    first_occurence = {} 
    # duplicates array: 
    dup = np.zeros(ar.shape[0], dtype=int) 
    for i in range(ar.shape[0]): 
     as_tuple = tuple(ar[i]) 
     if as_tuple not in first_occurence: 
      first_occurence[as_tuple] = i 
     dup[i] = first_occurence[as_tuple] 
    return dup 

Answer 3

我计时从Divakar和Jeremy答案两个测试案例在我的代码示例标有“为n个点＃最短极端”和“n个点＃最长的极端”。所有答案都能产生预期的结果并极大地提高速度。看起来Divakars矢量化方法一直是最快的。 感谢。所有功劳都归功于Divakar和Jeremy。

编辑： 实施矢量化的方法一些进一步的测试显示错误。对于示例阵列

[[ 0. 0. 0.] 
[ 1. 0. 0.] 
[ 1. 1. 0.] 
[ 0. 1. 0.] 
[ 2. 0. 0.] 
[ 3. 0. 0.] 
[ 3. 1. 0.] 
[ 2. 1. 0.]] 

矢量化方法检索全0列表。 view1D是第二快，所以我认为。

编辑2： Divakar修复了这个错误。由于