openmpとセグメンテーションフォールトを使ってKを最も近い近傍に配置

Question

"dat"のデータポイントのk最近傍点（KNN）を作成しようとしているので、最初のステップは各ポイントと他のすべての間の距離行列を作成することです各点について、K最近傍点を見つける。次のコードは、openmpなしで完璧に動作します。しかし、私がopenmpを使用すると、セグメント化エラーが発生します。私はこのエラーがk最小の要素のインデックスを含む最小のものをどのように更新するかと関係していると思います。私は、ベクトルの最小値で「縮小」を使用する必要があるかもしれないと思っていましたが、どのように使用するのか、あるいは間違っているか分からないので、このセグメンテーションの誤りを克服する方法については、

vector<vector<double> > dist(dat.size(), vector<double>(dat.size())); 
size_t p,j; 
ptrdiff_t i; 
vector<double> sumKnn; 
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 = p+1; 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][j-p-1]=j; 
      mycont++; 
     } 
     else 
     { 
      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.push_back(sum); 
} 

Answer 1

並列化。 FLANNライブラリhttp://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANNをダウンロードするだけです。

Answer 2

は、だから私は（すべての距離が計算されます）このアルゴリズムを並列化することは、おそらく、特にポイントの非常に大きな数字のために、より高速なツリーベースのアルゴリズムを使用する場合と比較して高速化するつもりはないされていることを@izomorphiusに同意します。

まだ、これはかなり簡単に行うことができます。問題は、複数のスレッドが共有ベクトルに対して同時にpush_back（）やerase（）などの処理を行うことができないことです。そして、率直に言って、これらのことには間違ったアプローチが使われているように見えます。これらのもののサイズを知っているので、単に配列を使うのがおそらく方法です。

いずれにしても、消去とプッシュバックを使用せずに、最小の[] []配列で手動で移動することで、push_back（）を使用する代わりにsumKnnの静的配列に書き込むだけで、働く

#pragma omp critical 
{ 
smallest[p].erase(smallest[p].begin()+index); 
smallest[p].push_back(j); 
} 

と

#pragma omp critical 
sumKnn.push_back(sum); 

しかし、私はより良いが、KD-ツリーまたはの木isteadをK-意味使用することを、同意する：あなたは "クリティカル" ディレクティブを使用することができます

#include <cmath> 
#include <cstdlib> 
#include <vector> 

using namespace std; 

int main(int argc, char **argv) { 

    const int size = 25; // number of pts 
    const int k = 2;  // number of neighbours 
    const int c = 2;  // number of dimensions 

    vector<vector<double> > dat(size, vector<double>(c)); 
    for (int i=0; i<size; i++) { 
     vector<double> pt(c); 
     for (int d=0; d<c; d++) { 
      pt.push_back(rand()*1./RAND_MAX); 
     } 
     dat.push_back(pt); 
    } 

    vector<vector<double> > dist(size, vector<double>(size)); 
    double sumKnn[size]; 

    vector<vector<int > > smallest(size, vector<int>(k)); 
#pragma omp parallel for default(none) shared(dat, dist, smallest, sumKnn) 
    for(size_t p=0;p<size;++p) 
    { 
     int mycont=0; 
     for (size_t j = p+1; j < size; ++j) 
     { 
      double ecl = 0.0; 
      for (ptrdiff_t 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][j-p-1]=j; 
       mycont++; 
      } 
      else 
      { 
       double max=0.0; 
       int index=0; 
       for(int i=0;i<k;i++) 
       { 
        if(max < dist[p][smallest[p][i]]) 
        { 
         index=i; 
         max=dist[p][smallest[p][i]]; 
        } 
       } 
       if(max>dist[p][j]) 
       { 
        for (int ii=index; ii<k-1; ii++) 
         smallest[p][ii] = smallest[p][ii+1]; 
        smallest[p][k-1] = j; 
       } 
      } 
     } 
     double sum=0.0; 
     for(int r=0;r<k;r++) 
      sum+= dist[p][smallest[p][r]]; 
     sumKnn[p] = sum; 
    } 


    return 0; 
}