Numba로 신경질적인 최적화

Question

아래 코드 예제에서 'obj'및 'ps'라고 표시된 구에 두 세트의 점이 있습니다. 'ps'지점에서 특정 각도 거리보다 가까운 모든 'obj'점을 확인하고 싶습니다.

제 생각에는 각 점을 3D 단위 벡터로 나타내고 점 제품을 cos (최대 거리)로 비교하는 것입니다. numpy 브로드 캐스팅을 사용하면 쉽게이 작업을 수행 할 수 있지만 응용 프로그램에 n_obj ~ 500,000 및 n_ps ~ 50,000가 있으므로 방송의 메모리 요구량이 너무 큽니다. 아래에 나는 numba를 사용하여 나의 현재 테이크를 풀었다. 이것이 더 이상 최적화 될 수 있습니까?

from numba import jit 
import numpy as np 
from sklearn.preprocessing import normalize 

def gen_points(n): 
    """ 
    generate random 3D unit vectors (not uniform, but irrelevant here) 
    """ 
    vec = 2*np.random.rand(n,3)-1. 
    vec_norm = normalize(vec) 
    return vec_norm 

#@jit(nopython=True) 
@jit 
def angdist_threshold_numba(vec_obj,vec_ps,cos_maxsep): 
    """ 
    finds obj that are closer than maxsep to a ps 
    """  
    nps = len(vec_ps) 
    nobj = len(vec_obj)  

    #closeobj_all = [] 
    closeobj_all = np.empty(0) 
    dotprod = np.empty(nobj) 
    a = np.arange(nobj) 
    for ps in range(nps): 
     np.sum(vec_obj*vec_ps[ps],axis=1,out=dotprod) 
     #closeobj_all.extend(a[dotprod > cos_maxsep]) 
     closeobj_all = np.append(closeobj_all, a[dotprod > cos_maxsep]) 

    return closeobj_all 


vec_obj = gen_points(50000) #in reality ~500,000 
vec_ps = gen_points(5000) #in reality ~50,000 
cos_maxsep = np.cos(0.003) 

closeobj_all = np.unique(angdist_threshold_numba(vec_obj,vec_ps,cos_maxsep)) 

이

코드에 주어진 테스트 케이스를 사용하여 성능입니다 :

@jit(nopython=True) 

사용하여 속도를 내가 시도

%timeit np.unique(angdist_threshold_numba(vec_obj,vec_ps,cos_maxsep)) 
1 loops, best of 3: 4.53 s per loop 

을하지만이

NotImplementedError: Failed at nopython (nopython frontend) 
(<class 'numba.ir.Expr'>, build_list(items=[])) 

실패

편집 : numba 업데이트 후 0.26 빈리스트의 생성은 파이썬 모드에서도 실패합니다. 이것은 np.empty (0)로 바꾸고, .extend()를 np.append()로 대체하여 수정할 수 있습니다 (위 참조). 이것은 거의 성능을 변경하지 않습니다. https://github.com/numba/numba/issues/858 np.empty()에 따르면

지금 nopython 모드에서 지원됩니다,하지만, 난 여전히 (= nopython true)를 @jit으로이 프로그램을 실행할 수 없습니다 :

TypingError: Internal error at <numba.typeinfer.CallConstraint object at 0x7ff3114a9310> 

Answer 1

list.append 달리 당신이 numpy.append 전화를해서는 안됩니다 루프에! 이는 단일 요소를 추가하는 경우에도 전체 배열을 복사해야하기 때문입니다. 고유 한 obj에만 관심이 있으므로 부울 배열을 사용하여 지금까지 발견 된 일치 항목에 플래그를 지정할 수 있습니다.

Numba는 모든 루프를 작성하는 것이 가장 효과적입니다. 그래서 예를 들면 :

@jit(nopython=True) 
def numba2(vec_obj, vec_ps, cos_maxsep): 
    nps = vec_ps.shape[0] 
    nobj = vec_obj.shape[0] 
    dim = vec_obj.shape[1] 
    found = np.zeros(nobj, np.bool_) 
    for i in range(nobj): 
     for j in range(nps): 
      cos = 0.0 
      for k in range(dim): 
       cos += vec_obj[i,k] * vec_ps[j,k] 
      if cos > cos_maxsep: 
       found[i] = True 
       break 
    return found.nonzero() 

추가 된 이점은 우리가 현재 obj에 일치하는 항목을 발견하면 우리는 즉시 ps 배열을 통해 루프를 벗어날 수 있다는 것입니다.

3 차원 공간에 대한 함수를 특수화하여 좀 더 빠른 속도를 얻을 수 있습니다. 또한, 어떤 이유로, 다른 속도 향상에 도우미 함수 결과에 모든 배열과 관련된 차원을 통과 : 나는 20,000 obj 얻을

def numba3(vec_obj, vec_ps, cos_maxsep): 
    nps = len(vec_ps) 
    nobj = len(vec_obj) 
    out = np.zeros(nobj, bool) 
    numba3_helper(vec_obj, vec_ps, cos_maxsep, out, nps, nobj) 
    return np.flatnonzero(out) 

@jit(nopython=True) 
def numba3_helper(vec_obj, vec_ps, cos_maxsep, out, nps, nobj): 
    for i in range(nobj): 
     for j in range(nps): 
      cos = (vec_obj[i,0]*vec_ps[j,0] + 
        vec_obj[i,1]*vec_ps[j,1] + 
        vec_obj[i,2]*vec_ps[j,2]) 
      if cos > cos_maxsep: 
       out[i] = True 
       break 
    return out 

타이밍과 2000 ps :

%timeit angdist_threshold_numba(vec_obj,vec_ps,cos_maxsep) 
1 loop, best of 3: 2.99 s per loop 
%timeit numba2(vec_obj, vec_ps, cos_maxsep) 
1 loop, best of 3: 444 ms per loop 
%timeit numba3(vec_obj, vec_ps, cos_maxsep) 
10 loops, best of 3: 134 ms per loop