Python 최적화 : 큰 배열, 메모리 문제

Question

python/numypy 코드를 실행하는 데 속도 문제가 있습니다. 나는 그것을 더 빨리, 어쩌면 다른 사람으로 만드는 법을 모른다.

두 개의 삼각 측량이있는 표면이 있다고 가정합니다. 하나는 M 점으로, 다른 하나는 N 점으로 거친 것입니다. 또한 모든 점에서 거친 메쉬에 대한 데이터가 있습니다 (N floats). 다음을하려고합니다.

미세한 메쉬의 모든 점에 대해 거친 메쉬에서 k 개의 가장 가까운 점을 찾아 평균값을 얻습니다. 짧음 : 굵은 것에서 벌금으로 데이터를 보간합니다.

내 코드는 지금 이렇게됩니다. 대용량 데이터 (제 경우 M = 2e6, N = 1e4)를 사용하면 코드가 약 25 분 동안 실행됩니다. 명시 적 for 루프가 numpy로되지 않기 때문에 추측 할 수 있습니다. 스마트 색인 생성으로 어떻게 해결할 수 있습니까? RAM을 부는 M × N 어레이.

import numpy as np 

p_fine.shape => m x 3 
p.shape => n x 3 

data_fine = np.empty((m,)) 
for i, ps in enumerate(p_fine): 
    data_fine[i] = np.mean(data_coarse[np.argsort(np.linalg.norm(ps-p,axis=1))[:k]]) 

건배!

Answer 1

먼저 자세한 도움말을 보내 주셔서 감사합니다.

첫 번째로, Divakar는 해결책이 상당히 빨라졌습니다. 내 데이터를 사용하면 코드는 청크 크기에 따라 2 분 미만으로 실행됩니다.

또한 sklearn 주위에 내 방식을 시도하고 내 데이터의 크기에 매우 빠른 었죠

def sklearnSearch_v3(p, p_fine, k): 
    neigh = NearestNeighbors(k) 
    neigh.fit(p) 
    return data_coarse[neigh.kneighbors(p_fine)[1]].mean(axis=1) 

으로 결국, 내가 얻을 다음

import numpy as np 
from sklearn.neighbors import NearestNeighbors 

m,n = 2000000,20000 
p_fine = np.random.rand(m,3) 
p = np.random.rand(n,3) 
data_coarse = np.random.rand(n) 
k = 3 

수익률

%timeit sklearv3(p, p_fine, k) 
1 loop, best of 3: 7.46 s per loop 

Answer 2

우리는 대형 데이터 세트 및 메모리로 작업 한

접근 번호는 문제입니다, 그래서 루프 내에서 계산을 최적화하기 위해 노력할 것입니다. 이제, 우리는과 같이, np.argsort과 실제 정렬 대신에 np.linalg.norm 부분 np.argpartition를 대체 할 np.einsum을 사용할 수 있습니다 -

가

out = np.empty((m,)) 
for i, ps in enumerate(p_fine): 
    subs = ps-p 
    sq_dists = np.einsum('ij,ij->i',subs,subs) 
    out[i] = data_coarse[np.argpartition(sq_dists,k)[:k]].sum() 
out = out/k 

접근 # 2

이제 다른 방법으로 우리는 또한 대한 Scipy's cdist을 사용할 수 있습니다

그러나 여기에 메모리가 바인딩되어 있으므로 이러한 작업을 수행 할 수 있습니다. ns 청크. 기본적으로, 우리는 행이 수백만 개이고 cdist을 사용하는 키가 큰 배열 p_fine에서 행을 가져 와서 각 반복마다 단 하나의 스칼라가 아닌 출력 요소의 덩어리를 얻습니다. 이것으로 루프 카운트를 그 청크의 길이만큼 자른다.

out = np.empty((m,)) 
L = 10 # Length of chunk (to be used as a param) 
num_iter = m//L 
for j in range(num_iter): 
    p_fine_slice = p_fine[L*j:L*j+L] 
    out[L*j:L*j+L] = data_coarse[np.argpartition(cdist\ 
          (p_fine_slice,p),k,axis=1)[:,:k]].mean(1) 

런타임 테스트

설정 - -

# Setup inputs 
m,n = 20000,100 
p_fine = np.random.rand(m,3) 
p = np.random.rand(n,3) 
data_coarse = np.random.rand(n) 
k = 5 

def original_approach(p,p_fine,m,n,k): 
    data_fine = np.empty((m,)) 
    for i, ps in enumerate(p_fine): 
     data_fine[i] = np.mean(data_coarse[np.argsort(np.linalg.norm\ 
               (ps-p,axis=1))[:k]]) 
    return data_fine 

def proposed_approach(p,p_fine,m,n,k):  
    out = np.empty((m,)) 
    for i, ps in enumerate(p_fine): 
     subs = ps-p 
     sq_dists = np.einsum('ij,ij->i',subs,subs) 
     out[i] = data_coarse[np.argpartition(sq_dists,k)[:k]].sum() 
    return out/k 

def proposed_approach_v2(p,p_fine,m,n,k,len_per_iter): 
    L = len_per_iter 
    out = np.empty((m,))  
    num_iter = m//L 
    for j in range(num_iter): 
     p_fine_slice = p_fine[L*j:L*j+L] 
     out[L*j:L*j+L] = data_coarse[np.argpartition(cdist\ 
           (p_fine_slice,p),k,axis=1)[:,:k]].sum(1) 
    return out/k 

타이밍 -

In [134]: %timeit original_approach(p,p_fine,m,n,k) 
1 loops, best of 3: 1.1 s per loop 

In [135]: %timeit proposed_approach(p,p_fine,m,n,k) 
1 loops, best of 3: 539 ms per loop 

In [136]: %timeit proposed_approach_v2(p,p_fine,m,n,k,len_per_iter=100) 
10 loops, best of 3: 63.2 ms per loop 

In [137]: %timeit proposed_approach_v2(p,p_fine,m,n,k,len_per_iter=1000) 
10 loops, best of 3: 53.1 ms per loop 

In [138]: %timeit proposed_approach_v2(p,p_fine,m,n,k,len_per_iter=2000) 
10 loops, best of 3: 63.8 ms per loop 

,691

그래서, 마침내 우리는 지금 같은 구현을 할 것이다

그래서, 1000에서 len_per_iter PARAM 세트 달콤한 자리에서 두 번째로 원래의 접근 방식을 통해 약 2x 처음 제안 된 접근 방식 개선과 20x있다. 바라기를 이것은 당신의 25 분 런타임을 조금 넘게 가져올 것입니다. 나는 그렇게 생각하지 않는다!