c++ - 使用openmp和段错误的并行K最近邻

Question

我正在尝试对“dat”中的数据点进行 k 最近邻 (KNN)，所以我的第一步是在每个点和所有其他点之间构建一个距离矩阵，然后为每个点找到 K最近的邻居。以下代码在没有 openmp 的情况下可以完美地串行运行。但是，当我使用 openmp 时，它会出现段错误。我认为这个错误与我如何更新包含 k 最小元素索引的最小值有关。我想可能我需要使用最小 vector 的“缩减”，但我不确定如何使用它或者它是对还是错，所以非常感谢任何关于如何克服这个段错误的帮助。

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

你可以只使用“critical”指令:

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

和

#pragma omp critical
sumKnn.push_back(sum);

但我同意，最好是使用 kd-tree 或 k-means 树而不是并行化。您可以直接下载 FLANN 库 http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN .