Параллельный алгоритм поиска K ближайших точек - PullRequest
Новая
       21

Параллельный алгоритм поиска K ближайших точек

1 голос
/ 05 марта 2012

Я реализовал следующий код, который использует точки данных в «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; 
}

1 Ответ

3 голосов
/ 05 марта 2012

Это скорее комментарий, чем ответ, но поле комментария слишком маленькое, ...

Одним из полезных аспектов OpenMP является то, что вы можете распараллеливать последовательную программу поэтапно. Таким образом, вашим первым шагом должно быть написание последовательного кода, который решит вашу проблему. Когда вы это сделаете, вы можете опубликовать снова и попросить помощи в распараллеливании.

Чтобы распараллелить вашу программу, найдите самый внешний оператор цикла и подумайте, как распределение итераций цикла по потокам повлияет на вычисления. Я подозреваю, что вы захотите создать общий вектор точек закрытия, когда циклы вращаются, а затем отсортировать его в конце только в одном потоке. Или, возможно, нет.

...