蟒蛇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修復了這個錯誤。由於