Code: I have a list of ~15,000 Euclidean points which represent a connected graph. I'm trying to solve/approximate the traveling salesman problem with this graph.
Problem: Finding neighbors, i.e. calculating the distance between each point, is very slow.
The points are stored in a vector as City
objects:
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;
};
And neighbors are added like so:
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);
}
}
And the distance is calculated by this function:
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)
);
}
Finally, I test the speed of this operation like so:
// 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
}
}
When I simply calculate the distance between points (Utilities::distanceSquared()
), it takes about 30 seconds (I'm not sure if this is good or bad for doing simple math on ~225,000,000 integers). When I try to use my addNeighbor()
function, the program runs for at least ten minutes without completing.
Any ideas on how I might speed up this operation?
pow()
is a slower operation. Replacing it with plain multiplication has sped up theUtilities::distanceSquared()
version to about 17 seconds, but theaddNeighbor()
is still hopelessly slow. \$\endgroup\$std::pow
to square an integer. \$\endgroup\$