python - 행당 Bin 요소-NumPy에 대한 벡터화 된 2D Bincount



performance matrix (1)

기본적으로 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 를 가져올 수 있습니다. 이제 numba 는 약간의 수정을 허용합니다.

  • 먼저 JIT 컴파일이 가능합니다.

  • 또한 최근에는 병렬 의미론을 갖는 것으로 알려진 기능의 작업을 자동으로 병렬화하는 실험 parallel 을 도입했습니다.

  • 마지막 조정은 prange를 range prange 로 사용하는 것입니다. 문서에서는 OpenMP 병렬 for 루프 및 Cython의 범위와 유사하게 루프를 병렬로 실행한다고 설명합니다. prange 는 병렬 작업을 설정하는 데 필요한 오버 헤드로 인해 더 큰 데이터 세트에서 잘 수행됩니다.

비-파이썬 모드에 대한 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