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



performance matrix (1)

好吧,這基本上就是 np.bincount 1D 數組的作用。 但是,我們需要在每行上迭代使用它(簡單地考慮一下)。 為了使其向量化,我們可以使每行偏移最大數量。 想法是每行具有不同的bin,以使它們不受編號相同的其他行元素的影響。

因此,實施將是-

# 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並行循環和Cython的prange。 prange 在較大的數據集上表現良好,這可能是由於設置並行工作所需的開銷。

因此,通過這兩項新的調整以及針對非Python模式的 njit ,我們將擁有三種變體-

# 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版本為-

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

我有一個帶有整數值的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 似乎大於唯一數字計數)。

有人有好主意嗎?)





vectorization