2017-09-16 46 views
5

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

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

所以,如果我在輸入這個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似乎比唯一號碼數量更大)。

有人偷有很大的想法?)

回答

7

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

因此,實現起來 -

# 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變體表現非常好。選擇三個變體中的一個將取決於輸入數組形狀參數,並且在某種程度上取決於其中的唯一元素的數量。

+0

太好了。它完全按照需要工作。非常感謝。 – Grigoriy

+0

'a + np.arange(a.shape [0])[:,無] * N'現在看起來像魔術。你能提供關於'抵消'價值的想法的解釋嗎? – Grigoriy

+0

哦,我明白了:你在每一行中抵消了值,使它們獨一無二。 – Grigoriy