c++ - 寻找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 的一个有用方面是您可以分步并行化串行程序。所以你的第一步应该是写一个串行代码来解决你的问题。完成后，您可以再次发帖并寻求有关并行化的帮助。

要并行化您的程序，请找到最外层的循环语句，并考虑跨线程分布循环迭代将如何影响计算。我怀疑您会希望在循环进行时创建一个共享的闭合点 vector ，然后仅在一个线程的末尾对其进行排序。或许不是。