优化Python：大数组，内存问题

Question

我遇到了运行python/numypy代码的速度问题。我不知道如何让它更快，也许是别人？

假设有一个表面有两个三角形，一个有M点的罚款（..._罚款），一个有N个点的罚款。另外，每个点都有关于粗网格的数据（N个浮点数）。我正在尝试执行以下操作：

对于细网格上的每个点，找到粗网格上的k个最近点并获取平均值。短：内插数据从粗到细。

我现在的代码就是这样。对于大数据（在我的情况下，M = 2e6，N = 1e4）代码运行大约25分钟，猜测由于明确的循环不会进入numpy。任何想法如何用智能索引来解决这个问题？ M×N阵列吹RAM ..

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

方法＃1

我们正在与大型数据集和内存的工作是一个问题，所以我会尽量在循环中优化计算。现在，我们可以使用np.einsum与np.argsort更换到位实际排序的np.linalg.norm一部分np.argpartition，像这样 -

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为一个完全量化的解决方案，像这样 -

from scipy.spatial.distance import cdist 
out = data_coarse[np.argpartition(cdist(p_fine,p),k,axis=1)[:,:k]].mean(1) 

但是，由于我们这里的内存限制，我们可以执行这些化经营ns大块。基本上，我们将从具有数百万行的高排列p_fine中得到块的行，并使用cdist，并且因此在每次迭代中获得输出元素的块而不是仅一个标量。有了这个，我们会减少该块的长度。

所以，最后我们将有像这样的实现 -

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 

所以，有大约2x改进与第一提出的方法和20x在与甜蜜点与len_per_iter参数组在1000第二个原来的做法。希望这会使您的25分钟运行时间稍微减少一分钟。不错，我猜！