2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Doing some of my own research, I've learned that pow() is a slower operation. Replacing it with plain multiplication has sped up the Utilities::distanceSquared() version to about 17 seconds, but the addNeighbor() is still hopelessly slow. \$\endgroup\$ – Alex Johnson Mar 13 '18 at 14:19
  • \$\begingroup\$ There's no good reason to use std::pow to square an integer. \$\endgroup\$ – Toby Speight Mar 13 '18 at 16:18
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the thoughtful response. Making the changes you suggested improved the distanceSquared() version from 30 seconds to about 8 seconds and the addNeighbor() version from "forever" to about 40 seconds. I wonder, should I expect the addNeighbor() version to be 5 times slower? I know that it involves creating objects and adding them to a vector (whereas distanceSquared() was just calculating a value), but 5 times slower seems like a lot of overhead. \$\endgroup\$ – Alex Johnson Mar 13 '18 at 16:05
  • 1
    \$\begingroup\$ Do beware of integer overflow in that distance calculation (it was a problem with the original, too). Using a floating point type for dx, dy and the return type may be better. \$\endgroup\$ – Toby Speight Mar 13 '18 at 16:23
  • \$\begingroup\$ I've added code showing how to calculate the distance only once. \$\endgroup\$ – Edward Mar 13 '18 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.