python - NumPy の行ベクトル化された 2D ビンカウントごとのビン要素



performance matrix (1)

整数値を持つ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 各行の一意の値を1つずつ繰り返してカウントし、 data 配列内のすべての可能な値を考慮して結果を組み合わせます。

これをベクトル化するためにNumPyを使用する際の重要な問題は、各番号を1つずつ検索するのが遅く、多くの一意の番号が提示されていると仮定すると、これが効果的な解決策にならないことです。 一般に、 N と一意の数字の両方のカウントはかなり大きくなります(ちなみに、 N は一意の数字のカウントよりも大きいようです)。

誰かが素晴らしいアイデアを持っていますか?)


それは基本的に 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 Tweaks

numba numba 、さらに高速化することができます。 現在、 numba では微調整はほとんど許可されていません。

  • まず、JITコンパイルを許可します。

  • また、最近、並列セマンティクスを持つことが知られている関数の操作を自動的に並列化する実験的 parallel を導入しました。

  • 最終的な微調整は、rangeを range 代替として使用すること range 。 文書は、これはループおよびCythonのプランジのOpenMP並列と同様に、ループを並列に実行すると述べています。 prange は、より大きなデータセットで良好に機能します。これは、おそらく並列作業のセットアップに必要なオーバーヘッドのためです。

したがって、これらの新しい2つの調整と非Pythonモードの njit を使用すると、3つのバリエーションがあります。

# 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 バリアントのパフォーマンスは非常に高いようです。 3つのバリアントから1つを選択することは、入力配列の形状パラメーターと、ある程度その中の一意の要素の数に依存します。





vectorization