Satır başına bin eleman - NumPy için Vectorized 2D Bincount

Question

Tamsayı değerleri olan bir NumPy dizim var. Matrisin değerleri matriste 0'dan maks. Elemana kadar değişir (diğer bir deyişle, 0'dan maksimum veri öğesine sunulan tüm sayılar). Her satırdaki elemanların sayısını aramak ve bunları matris değerlerine göre kodlamak için etkili (etkili, hızlı tam anlamıyla vectorized çözüm) oluşturmam gerekiyor.

Benzer bir soruya ya da bir şekilde bunu çözmemize yardımcı olan bir soru bulamadım. i girişteki bu data varsa

Yani:

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

İstenen çıkış geçerli:

# 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 

Sadece data her satırda benzersiz değerleri sayarak birini tekrarlayarak bunu çözmek için nasıl bir, ve daha sonra data dizisindeki tüm olası değerleri dikkate alarak sonuçları birleştirmek.

Bu durumu vektör etmek için NumPy kullanıldığında, anahtar problemi her bir rakamın birer birer aranmasının yavaş olması ve çok sayıda benzersiz sayının mevcut olduğu varsayımıdır, bu etkili bir çözüm olamaz. Genellikle hem N hem de benzersiz sayılar sayısı oldukça büyüktür (bu arada, N benzersiz sayılar sayısından daha büyük görünmektedir).

birileri harika fikirleri var mı?)

Answer 1

Eh o 1D dizilerle np.bincount yapar gelmez temelde ne bu. Ancak, onu her satırda yinelemeli olarak kullanmalıyız (basitçe düşünmek). Bunu vectorized yapmak için, her satırı bu maksimum sayıya göre dengeleyebiliriz. Buradaki fikir, her satır için farklı sayıdaki satırların, aynı sayılara sahip diğer satır öğelerinden etkilenmemeleridir.

Dolayısıyla, uygulama olacak -

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

Numune koşmak -

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 Düzenlemeler

Biz daha ileri hızlandırıcılar için numba kazandırabilir. Şimdi, numba, birkaç ayarlamaya izin veriyor.

• İlk olarak, JIT derlemesine izin verir. Paralel semantiğe sahip olduğu bilinen işlevlerdeki işlemleri otomatik olarak paralel hale getiren deneysel parallel deneysel modelini de eklediler.

• Son ince ayar prange ürününü range için bir alt birim olarak kullanmak olacaktır. Dokümanlar, döngüler için döngüye paralel olarak OpenMP'ye ve Cython’un sıralamasına benzer şekilde döngüler çalıştırdığını belirtir. prange, büyük olasılıkla daha büyük veri kümeleriyle iyi bir performans sergiliyor;no-Python modu için njit ile birlikte bu yeni iki düzeltmelerle birlikte Yani

, biz üç varyantı olurdu -

# 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 

Bütünlüğü için ve daha sonra test etmeyi loopy versiyonu olacağını -

# 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 

Çalışma testi

Olgu 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 

Olgu 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 

Olgu 3: numba varyantları çok iyi performans gösterdiğini gibi

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 

görünüyor. Üç varyanttan birini seçmek, giriş dizisi şekil parametrelerine ve bir dereceye kadar içerisindeki benzersiz öğelerin sayısına bağlı olacaktır.