Generate another random path through a complete graph

Question

What this does is generate a random path of cities to later calculate the length of the newly generated tour of cities, the TSP.

I am trying to figure out if there is a more efficient way to write this algorithm. I have tried using the std::shuffle and std::random_shuffle but did not notice any improvement in the run time. Any other resources I should try taking a look at?

std::vector<City> GetRandomPath(std::vector<City> oldPath)
{
    std::vector<City> newPath;

    newPath = oldPath;

    int randPoint = rand() % (oldPath.size()-1);
    int randPoint2 = rand() % (oldPath.size()-1 - randPoint) + randPoint;

    int k=1;
    for(int i =0; i < randPoint; i++)
    {
        newPath.push_back(oldPath.at(i));
    }
    for(int i=randPoint; i < randPoint2; i++)
    {

        newPath.push_back(oldPath.at(randPoint2-k));
        k++;
    }
    for(int i=randPoint2; i < oldPath.size(); i++)
    {
        newPath.push_back(oldPath.at(i));
    }

    return newPath;
}

Answer 1

From your code I'm guessing that you're doing some 2-opt for the TSP. And yes, it is possible to make it faster. The secret actually lies within your code, and is also the reason why your code isn't working.

Disclaimer: I am no expert at C++

When you do newPath = oldPath, you're making newPath a vector that is identical to, but not the same as oldPath. Then you push all elements from oldPath onto newPath, thus making it twice as big as oldPath.

But since you already have a concise way of copying all values to a new vector, let's use that to speed things up:

std::vector<City> GetRandomPathFast(std::vector<City> oldPath)
{
    std::vector<City> newPath = oldPath;

    int randPoint = rand() % (oldPath.size()-1);
    int randPoint2 = rand() % (oldPath.size()-1 - randPoint) + randPoint;

    int k = 1;
    for(int i=randPoint; i < randPoint2; i++)
    {
        newPath[i] = oldPath[randPoint2-k];
        k++;
    }
    return newPath;
}

By only modifying the values between randPoint and randPoint2, we get a significant speedup. We also get a path of the correct length, with a part of it reversed.

For benchmarking, I changed both your function and my new to use std::vector<int>, but numbers should carry over to your implementation.

Vector of length 1000, 10000 iterations of each function:
Time for GetRandomPath: 280.624 ms
Time for GetRandomPathFast: 22.136 ms