Вычисляя Евклидово расстояние


Код: у меня есть список из ~15,000 евклидовы точки, которые представляют собой связный граф. Я пытаюсь решить/примерные задачи коммивояжера с помощью этого графика.

Проблема: найти соседей, т. е. расчет расстояния между каждой точкой, очень медленно.

Очки хранятся в векторе как City объекты:

class City {
public:
    City(int id, int xCoord, int yCoord);

    int getCityID() const;
    int getXCoord() const;
    int getYCoord() const;

    void addNeighbor(const City &city);
    void removeNeighbor(int cityID);
    unsigned long getNeighborCount();
    Neighbor nearestNeighbor();
private:
    int id;
    int xCoord;
    int yCoord;
    std::vector<Neighbor> neighbors;
};

И соседей добавляются так:

void City::addNeighbor(const City &city) {
    int distance = Utilities::distanceSquared(*this, city);

    // Prevent cities listing themselves as neighbors
    if (distance > 0) {
        Neighbor neighbor(city.getCityID(), distance);
        neighbors.push_back(neighbor);
    }
}

А расстояние вычисляется по этой функции:

unsigned int Utilities::distanceSquared(City a, City b) {
    return static_cast<unsigned int>(
        pow(b.getXCoord() - a.getXCoord(), 2) + 
        pow(b.getYCoord() - a.getYCoord(), 2)
    );
}

Наконец, я проверить скорость этой операции так:

// Get input
std::string filename = "tsp_example_3.txt";
std::vector<City> input = Utilities::readFile(filename);

for (int c1 = 0; c1 < input.size(); c1++) {
    for (int c2 = 0; c2 < input.size(); c2++) {
        input[c1].addNeighbor(input[c2]);
        // Utilities::distanceSquared(input[c1], input[c2]); // ~30 seconds
    }
} 

Когда я просто вычислить расстояние между точками (Utilities::distanceSquared()), Она занимает около 30 секунд (я не уверен, если это хорошо или плохо для делаем простые математические действия на ~225,000,000 целых чисел). Когда я пытаюсь использовать мой addNeighbor() функции, программа работает, по крайней мере десяти минут без заполнения.

Любой идеи, как я могу ускорить эту операцию?



Комментарии
1 ответ

Я вижу несколько вещей, которые могут помочь вам улучшить ваш код.

Сортировать ввода

Если входные данные уже отсортированы, мы можем гарантировать, что City идентификатор векторов строго неубывания. Я хотел добавить эти две вещи для этого.

std::sort(input.begin(), input.end());

И тогда эта функция-член:

bool City::operator<(const City &other) const { 
return id < other.id;
}

Не повторить расчеты

Если есть что-то очень странное, расстояние от города A в город B является таким же, как расстояние от города Б до города А. По этой причине, мы можем заполнить векторов двух одновременно:

for (int c1 = 0; c1 < input.size(); c1++) {
for (int c2 = c1; c2 < input.size(); c2++) {
input[c1].addNeighbor(input[c2]);
input[c2].addNeighbor(input[c1]);
}
}

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

input[c1].addNeighbor(input[c2]);

И переписать функцию такой член:

void City::addNeighbor(City &city) {
if (getCityID() == city.getCityID()) {
return;
}
unsigned distance = Utilities::distanceSquared(*this, city);
neighbors.emplace_back(Neighbor{city.getCityID(), distance});
city.neighbors.emplace_back(Neighbor{getCityID(), distance});
}

Обратите внимание, что мы не рассчитав расстояние, если они один и тот же идентификатор, но не, если расстояние между ними равна нулю. В этом случае аргумент функции должен не быть const потому что мы должны также изменить его.

Также, хотя вы не предоставили код для этого, я замечаю, что у вас есть NearestNeighbor() функция. Существует несколько эффективных способов справиться с этим, в зависимости от того как вы собираетесь его использовать. Можно отсортировать векторы (однажды), когда население их полной или можно использовать std::priority_queue вместо std::vector.

Пройти константные ссылки, где практические

Передача объекта по значению может привести к копию объекта. Например эта функция:

unsigned int Utilities::distanceSquared(City a, City b);

вместо этого должно быть написано так:

unsigned int Utilities::distanceSquared(const City &a, const City &b);

Избежать плавающей точкой, если нужны только целые числа

Целочисленные операции, как правило, быстрее, чем операции с плавающей точкой. Вот как я напишу твое distanceSquared функции:

namespace Utilities {
unsigned int distanceSquared(const City &a, const City &b) {
int dx{b.getXCoord() - a.getXCoord()};
int dy{b.getYCoord() - a.getYCoord()};
return dx*dx + dy*dy;
}
}

Как @TobySpeight правильно, это предполагает, что переполнение не происходит. На моих случайно сгенерированных тестовых данных, диапазоны X и y ограничены, так что гарантировано, с моим компилятором, что переполнение не может возникнуть, но стоит проверка, что за свои реальные данные, а также.

2
ответ дан 13 марта 2018 в 02:03 Источник Поделиться