Elementy pojemnika na wiersz - Vectorized 2D Bincount dla NumPy

Question

Mam tablicę NumPy z wartościami całkowitymi. Wartości macierzy mieszczą się w zakresie od 0 do maks. Elementu w macierzy (innymi słowy, wszystkie liczby od 0 do max elementu danych w nim przedstawionego). Muszę zbudować efektywne (efektywne szybkie szybkie w pełni wektoryzowane rozwiązanie) do wyszukiwania liczby elementów w każdym wierszu i zakodować je zgodnie z wartościami macierzy.

Nie mogłem znaleźć podobnego pytania lub pytania, które w jakiś sposób pomogły rozwiązać ten problem.

Więc jeśli mam ten data na wejściu:

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

pożądane wyjście jest:

# 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 

wiem jak rozwiązać ten problem przez zliczenie wartości unikatowe w każdym rzędzie data iteracji jeden po jeden, a następnie łącząc wyniki biorąc pod uwagę wszystkie możliwe wartości w tablicy data.

Podczas używania NumPy do wektoryzacji ten kluczowy problem polega na tym, że wyszukiwanie każdego numeru po kolei jest powolne, a przy założeniu, że przedstawionych jest wiele niepowtarzalnych liczb, nie może to być skuteczne rozwiązanie. Zasadniczo zarówno liczba N, jak i unikalne liczby liczb są dość duże (przy okazji, N wydaje się być większa niż liczba unikalnych liczb).

Czy ktoś ma świetne pomysły?)

Answer 1

Dobrze, że w zasadzie to, co robi np.bincount robi z 1D tablic. Ale musimy go używać iteracyjnie w każdym wierszu (myśląc o tym po prostu). Aby był wektoryzowany, mogliśmy przesunąć każdy wiersz o tę maksymalną liczbę. Chodzi o to, aby w każdym rzędzie znajdowały się różne pojemniki, tak aby nie oddziaływały na nie inne elementy o tych samych numerach.

Stąd realizacja byłaby -

# 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) 

Sample Run -

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 Wariacje

Możemy przynieść numba dalszych speedups. Teraz numba pozwala na kilka poprawek.

• Po pierwsze, umożliwia kompilację JIT.

• Niedawno wprowadzono eksperymentalne urządzenie parallel, które automatycznie przeprowadza równoległe operacje w funkcji, o której wiadomo, że ma semantykę równoległą.

• Ostatecznym usprawnieniem byłoby użycie prange jako subsythetu dla range. Dokumenty mówią, że uruchamia to pętle równolegle, podobnie do równoległego OpenMP dla pętli i prążków Cythona. prange radzi sobie dobrze z większymi zestawami danych, co prawdopodobnie wynika z konieczności dostosowania do pracy równoległej.

Tak, z tych nowych dwóch poprawek wraz z njit dla NO-Python trybie, mielibyśmy trzech wariantach -

# 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 

Dla kompletności i testowania później, wersja loopy byłoby -

# 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 

Test Runtime

Case # 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 

Case # 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 

Case # 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 

Wygląda warianty numba radzą sobie bardzo dobrze. Wybór jednego z trzech wariantów zależy od parametrów wejściowych kształtu tablicy i do pewnego stopnia od liczby unikalnych elementów w nim.