Як зменшити час виконання алгоритму - c ++, алгоритм

Мені доведеться алгоритм, який знаходить дванайближчі точки на землі. Я написав код нижче, і він працює для моїх тестів, але час виконання занадто довгий. Я намагався змінити код, але це не допомогло. Можливо, хтось матиме уявлення, що мені робити?

struct Points
{
std::string key;
double latitude;
char latSign;
double longitude;
char longSign;
};

typedef std::pair<std::pair<std::string, std::string>, double> myType;

double toFraction(short deegres, short minutes)
{
return (double)deegres + (minutes / 60.0);
}

double orthodroma(const Points &a, const Points &b)
{
double radian = M_PI / 180;
return acos((cos((90 - a.latitude) * radian) *
cos((90 - b.latitude) * radian)) +
(sin((90 - a.latitude) * radian) *
sin((90 - b.latitude) * radian) *
cos((a.longitude - b.longitude) * radian))) *
(180 / M_PI);
}

bool sortByLatitude(const Points &a, const Points &b)
{
return a.latitude > b.latitude;
}

myType bruteForce(const std::vector<Points> &vec, int begin, int n)
{
myType result;
double min = 1000000;
int _i, _j;
if(n > 300)
{
}
for(int i = begin; i < (n + begin) - 1; i++)
{
for(int j = i + 1; j < n + begin; j++)
{
double tmp;
tmp = orthodroma(vec[i], vec[j]);
if(tmp < min)
{
min = tmp;
_i = i;
_j = j;
}
}
}
result.first.first = vec[_i].key;
result.first.second = vec[_j].key;
result.second = min;
return result;
}

myType divideAndConquer(std::vector<Points> &vec, int begin, int n)
{
if(n <= 3)
{
return bruteForce(vec, begin, n);
}
std::sort(vec.begin(), vec.end(), sortByLatitude);
int middle = n / 2;
Points point = vec[middle];
myType left = divideAndConquer(vec, begin, middle);
myType right = divideAndConquer(vec, middle, (n - middle));
bool which;
double minDist = std::min(left.second, right.second);
if(left.second < right.second)
which = false;
else
which = true;
std::vector<Points> arr;
for(int i = 0; i < n; i++)
{
if(abs(vec[i].latitude - point.latitude) < minDist)
{
arr.push_back(vec[i]);
}
}
int size = arr.size();
if(size < 2)
{
if(which)
return right;
else
return left;
}
else
{
myType one = bruteForce(arr, 0, size);
if(which)
{
if(one.second < right.second)
return one;
else
return right;
}
else
{
if(one.second < left.second)
return one;
else
return left;
}
}
}

PS. Мені доводиться використовувати метод поділу conquer.

Відповіді:

Кілька ідей, які можуть трохи покращити ефективність:

• сортуйте масив лише один раз (до першого рекурсивного виклику методу ділення та підкорити).

• при додаванні балів у arr вектор, ви можете почати з середнього положення,спочатку рухається вперед, а потім рухається назад. Перевага полягає в тому, що ви можете розірвати кожну з цих петель, як тільки одна точка буде достатньо далеко від середньої точки. Оскільки масив відсортований за широтою, гарантується, що решта точок виявиться за межами потрібного діапазону.

• ви можете передати додатковий параметр методу divideAndConquer, що представляє відому досі мінімальну відстань. Це може призвести до менших arr масиви, швидше обробляються. Наразі може статися так, що ми отримуємо дуже невелику відстань для лівого підмасиву. Однак, розв'язуючи правильний підмасив, рекурсивні дзвінки наразі не мають інформації про вже знайдену невелику відстань.

Щоб знайти найближчі дві точки, потрібно спочатку перевірити відстань до найближчої точки для кожної точки.

Ви повинні використовувати дерево KD для швидкого пошуку найближчих сусідів. Ви можете використовувати порівняльну відстань, щоб зберегти операцію sqrt ().

Це велике kd дерева бібліотека