Bin元素每行 - NumPy矢量化2D Bincount

Question

我有一個整數值的NumPy數組。矩陣的值範圍從0到矩陣中的最大元素（換句話說，從0到最大數據元素中的所有數字）。我需要建立有效的（有效的手段快速全矢量化解決方案）搜索每行元素的數量，並根據矩陣值進行編碼。

我找不到一個類似的問題，或以某種方式幫助解決這個問題。

所以，如果我在輸入這個data：

# shape is (N0=4, m0=4) 
1 1 0 4 
2 4 2 1 
1 2 3 5 
4 4 4 1 

所需的輸出是：

# shape(N=N0, m=data.max()+1): 
1 2 0 0 1 0 
0 1 2 0 1 0 
0 1 1 1 0 1 
0 1 0 0 3 0 

我知道如何通過簡單的data每一行中計算了唯一的值是通過遍歷一個解決這個一個，然後結合考慮data陣列中所有可能值的結果。

雖然使用NumPy進行矢量化，但關鍵問題是逐個搜索每個數字的速度很慢，並且假設存在大量唯一的數字，這不是有效的解決方案。一般來說，N和唯一號碼數量都很大（順便說一下，N似乎比唯一號碼數量更大）。

有人偷有很大的想法？）

Answer 1

嗯，這基本上是什麼np.bincount與1D陣列一樣。但是，我們需要迭代地在每一行上使用它（簡單地考慮它）。爲了使其矢量化，我們可以通過該最大數字偏移每一行。這個想法是爲每一行設置不同的分檔，這樣它們就不會受到具有相同數字的其他行元素的影響。

因此，實現起來 -

# Vectorized solution 
def bincount2D_vectorized(a):  
    N = a.max()+1 
    a_offs = a + np.arange(a.shape[0])[:,None]*N 
    return np.bincount(a_offs.ravel(), minlength=a.shape[0]*N).reshape(-1,N) 

採樣運行 -

In [189]: a 
Out[189]: 
array([[1, 1, 0, 4], 
     [2, 4, 2, 1], 
     [1, 2, 3, 5], 
     [4, 4, 4, 1]]) 

In [190]: bincount2D_vectorized(a) 
Out[190]: 
array([[1, 2, 0, 0, 1, 0], 
     [0, 1, 2, 0, 1, 0], 
     [0, 1, 1, 1, 0, 1], 
     [0, 1, 0, 0, 3, 0]]) 

Numba調整菜譜方案

我們可以在numba帶來進一步的加速。現在，numba允許很少的調整。

• 首先，它允許JIT編譯。另外，最近他們已經引入了實驗parallel，其在已知具有並行語義的函數中自動並行化操作。

• 最後的調整將使用prange作爲range的子。文檔聲明它並行運行循環，類似於OpenMP並行for循環和Cython的prange。 prange在較大的數據集中表現良好，這可能是因爲設置並行工作所需的開銷。

因此，隨用隨njit爲無Python的方式沿着這些新建兩個調整，我們將有三個變種 -

# Numba solutions 
def bincount2D_numba(a, use_parallel=False, use_prange=False): 
    N = a.max()+1 
    m,n = a.shape 
    out = np.zeros((m,N),dtype=int) 

    # Choose fucntion based on args 
    func = bincount2D_numba_func0 
    if use_parallel: 
     if use_prange: 
      func = bincount2D_numba_func2 
     else: 
      func = bincount2D_numba_func1 
    # Run chosen function on input data and output 
    func(a, out, m, n) 
    return out 

@njit 
def bincount2D_numba_func0(a, out, m, n): 
    for i in range(m): 
     for j in range(n): 
      out[i,a[i,j]] += 1 

@njit(parallel=True) 
def bincount2D_numba_func1(a, out, m, n): 
    for i in range(m): 
     for j in range(n): 
      out[i,a[i,j]] += 1 

@njit(parallel=True) 
def bincount2D_numba_func2(a, out, m, n): 
    for i in prange(m): 
     for j in prange(n): 
      out[i,a[i,j]] += 1 

爲了完整和測試出後，糊塗的版本將是 -

# Loopy solution 
def bincount2D_loopy(a): 
    N = a.max()+1 
    m,n = a.shape 
    out = np.zeros((m,N),dtype=int) 
    for i in range(m): 
     out[i] = np.bincount(a[i], minlength=N) 
    return out 

運行測試

情況＃1：

In [312]: a = np.random.randint(0,100,(100,100)) 

In [313]: %timeit bincount2D_loopy(a) 
    ...: %timeit bincount2D_vectorized(a) 
    ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False) 
    ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False) 
    ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True) 
10000 loops, best of 3: 115 µs per loop 
10000 loops, best of 3: 36.7 µs per loop 
10000 loops, best of 3: 22.6 µs per loop 
10000 loops, best of 3: 22.7 µs per loop 
10000 loops, best of 3: 39.9 µs per loop 

情況＃2：

In [316]: a = np.random.randint(0,100,(1000,1000)) 

In [317]: %timeit bincount2D_loopy(a) 
    ...: %timeit bincount2D_vectorized(a) 
    ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False) 
    ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False) 
    ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True) 
100 loops, best of 3: 2.97 ms per loop 
100 loops, best of 3: 3.54 ms per loop 
1000 loops, best of 3: 1.83 ms per loop 
100 loops, best of 3: 1.78 ms per loop 
1000 loops, best of 3: 1.4 ms per loop 

情況＃3：

In [318]: a = np.random.randint(0,1000,(1000,1000)) 

In [319]: %timeit bincount2D_loopy(a) 
    ...: %timeit bincount2D_vectorized(a) 
    ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False) 
    ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False) 
    ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True) 
100 loops, best of 3: 4.01 ms per loop 
100 loops, best of 3: 4.86 ms per loop 
100 loops, best of 3: 3.21 ms per loop 
100 loops, best of 3: 3.18 ms per loop 
100 loops, best of 3: 2.45 ms per loop 

好像numba變體表現非常好。選擇三個變體中的一個將取決於輸入數組形狀參數，並且在某種程度上取決於其中的唯一元素的數量。