Is there any way of optimising this function?

Question

This piece of code seems to be the worst offender in terms of time in my program. What my program is trying to do find the minimum number of individual "nodes" required to satisfy a network with two constraints:

1. Each node must connect to x number of other nodes
2. Each node must have y degrees of separation between it and each of the nodes it's connected to.

However for values of x greater than 600 this task takes a very long time, the task is on the order of exponential anyway so I expect it to take forever at some point but that also means that if any small changes could be made here it'd speed up the entire program by alot.

• uniint = unsigned long long int (64-bit)
• network is a vector of the form vector<vector<uniint>>

The piece of code:

/* Checks if id2 is in id1's list of connections */
inline bool CheckIfInList (uniint id1, uniint id2) 
{
    uniint id1size = network[id1].size();
    for (uniint itr = 0; itr < id1size; ++itr)
    {
        if (network[id1][itr] == id2)
        {
            return true;
        }
    }
    return false;
}

Answer 1

The only way is to sort the network[id1] array when you build it.

If you arrive here with a sorted array you can easiliy find, if exists, what you are looking for using a dichotomic search.

Answer 2

Use std::map or std::unordered_map for fast search. I guess it's impossible to MICRO optimize this code, std::vector is cool. But not for 600 elements search.

Answer 3

I'm guessing CheckIfInList() is called in a loop? Perhaps a vector is not the best choice, you could try vector<set<uniint>>. This will give you O(log n) for a look up of the inner collection instead of O(n)

Answer 4

For quick microoptimization, check whether your compiler optimizes the multiple calls to network[id1] away. If not, that is where you loose a lot of time, so remember the address:

vector<uniint>& connectedNodes = network[id1];
uniint id1size = connectedNodes.size();
for (uniint itr = 0; itr < id1size; ++itr)
{
    if (connectedNodes[itr] == id2)
    {
        return true;
    }
}
return false;

If your compiler already took care of that, I'm afraid that there's not much you can micro optimize about this method. The only real optimization can be achieved on the algorithmic level, starting with sorting the neighbour lists, moving on to using unordered_map<> instead of vector<>, and ending with asking yourself whether you can't somehow reduce the number of calls to CheckIfInList().

Answer 5

This is not as effective as HAL9000's suggestion, and is good for cases when you have an unsorted list/array. What you can do is to ask less question in each iteration if you put the value you looking for at the end of the vector.

uniint id1size = network[id1].size();
network[id1][id1size] = id2;
for (uniint itr = 0; network[id1][itr] == id2; ++itr);

//if itr != id1size return true else flase....

need to add checks if the last member in the vector was your id2. This way you don't need to ask each time whether you get to the end of the list.