Calculating Euclidean distance

Question

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?

Answer 1

I see a few things that may help you improve your code.

Sort the input

If the input is sorted, we can assure that the City id for vectors is strictly non-decreasing. I'd add these two things for that.

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

And then this member function:

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

Don't repeat calculations

Unless there's something very strange, the distance from city A to city B is the same as the distance from city B to city A. For that reason, we can populate the vectors two at a time:

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]);
    }
} 

This is also why I suggested to sort the input vector. I would also suggest calculating the distance once and then using it for both vector additions. Doing that will require a little more code restructuring. The inner loop can simply be this:

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

And rewrite the member function like this:

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});
}

Note that we avoid calculating the distance if they are the same ID, but not if the distance between them is actually zero. In this case the argument to the function must not be const because we need also to modify it.

Also, although you did not provide the code for it, I notice that you have a NearestNeighbor() function. There are some efficient ways to deal with that, depending on how you intend to use it. One could sort the vectors (once) when population of them is complete or one might use a std::priority_queue instead of a std::vector.

Pass const references where practical

Passing an object by value can cause an object copy. For example this function:

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

should instead be written like this:

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

Avoid floating point if only integers are needed

Integer operations are usually faster than floating point operations. So here's how I'd write your distanceSquared function:

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;
}
}

As @TobySpeight correctly points out, this assumes that no overflow occurs. On my randomly generated test data, the ranges of the x and y coordinates are restricted so that is guaranteed, with my compiler, that no overflow can occur, but it's worth verifying that for your real data as well.