找到K最近點的並行算法

Question

我實現了下面的代碼，它使用「dat」中的數據點來計算每個點與所有其他點「dist」之間的距離矩陣。然後，我使用這個距離矩陣來找到數據中「最小」數據中每個點的K個最近點，然後用它來找出K個最近鄰點的總和。

以下算法是一種使用OpenMP的並行算法，工作非常良好。我只需要建議讓它運行得更快。任何建議非常感謝。

vector<vector<double> > dist(dat.size(), vector<double>(dat.size())); 
size_t p,j; 
ptrdiff_t i; 
double* sumKnn = new double[dat.size()]; 
vector<vector<int > > smallest(dat.size(), vector<int>(k)); 
#pragma omp parallel for private(p,j,i) default(shared) 
for(p=0;p<dat.size();++p) 
{ 
    int mycont=0; 
    for (j = 0; j < dat.size(); ++j) 
    { 
     double ecl = 0.0; 
     for (i = 0; i < c; ++i) 
     { 
      ecl += (dat[p][i] - dat[j][i]) * (dat[p][i] - dat[j][i]); 
     } 
     ecl = sqrt(ecl); 
     dist[p][j] = ecl; 
     //dist[j][p] = ecl; 
     int index=0; 
     if(mycont<k && j!=p) 
     { 
      smallest[p][mycont]=j; 
      mycont++; 
     } 
     else if(j!=p) 
     { 
      double max=0.0; 
      int index=0; 
      for(int i=0;i<smallest[p].size();i++) 
      { 
       if(max < dist[p][smallest[p][i]]) 
       { 
        index=i; 
        max=dist[p][smallest[p][i]]; 
       } 
      } 
      if(max>dist[p][j]) 
      { 
       smallest[p].erase(smallest[p].begin()+index); 
       smallest[p].push_back(j); 
      } 
     }   
    } 
    double sum=0.0; 
    for(int r=0;r<k;r++) 
     sum+= dist[p][smallest[p][r]]; 
    sumKnn[p]=sum; 
} 

Answer 1

這比回答的評論，但評論框太小，...

之一的OpenMP的有用的方面是，你可以在parallelise步驟的串行程序。所以你的第一步應該是編寫一個解決你的問題的串行代碼。當你這樣做後，你可以再次發佈並尋求並行化的幫助。

要並行化您的程序，請找到最外層的循環語句，並考慮如何在線程之間分發循環迭代將影響計算。我懷疑你會想要創建一個共同的關閉點向量，因爲循環循環，然後在一個線程結束時將其排序。或者可能不是。