CODEWITHSUNDEEP
c++data-structuresgraphtime-complexity
masut
masut

Reputation: 51

Is there any other option to decrease this piece of code time complexity?

In this code, I'm iterating over a graph of vertices and comparing the weights of each vertex and its neighbors to find the maximum weight between them. Then store the number of times a vertex is marked by its neighbor vertices in X[i].

map<double, list<double>> adjacency;
map<double, double> degree;
map<double, double> W;
map<double, double> X;

void find_max_w()
{
    double max = 0.;
    int idx_max;
    for (const auto &pair : adjacency)
    {
        max = 0;
        W.find(pair.first)->second > max ? max = W.find(pair.first)->second, idx_max = pair.first : max = max;
        for (double d : pair.second)
        {
            W.find(d)->second > max ? max = W.find(d)->second, idx_max = d : max = max;
        }
        X.find(idx_max)->second += 1;
    }
}

apparently, accessing to a map by value is time-consuming, and I have three of these :

W.find(pair.first)->second > max ? max = W.find(pair.first)->second, idx_max = pair.first : max = max;

W.find(d)->second > max ? max = W.find(d)->second, idx_max = d : max = max;

X.find(idx_max)->second += 1;

I was wondering if there is any other way to implement this more efficiently and less time-consuming? for example, other data structures?

Upvotes: 0

Views: 71

Answers (1)

wohlstad
wohlstad

Reputation: 28094

You can consider to replace one or more of your std::maps with std::unordered_maps.

The complexity for searching an item in std::map, using std::map::find is:

Logarithmic in the size of the container.

This is for worse case (since not mentioned otherwise).

On the other hand the complexity for searching an item in std::unordered_map, using std::unordered_map::find is:

Constant on average, worst case linear in the size of the container.

(emphasis is mine)

The performance of both options depends on your data and must be profiled in order to select between them.
On average a search in an unordered_map is faster (O(1)), but there are cases it deteriorates to linear (O(n)). map is slower on average, but gives you stable performance (O(logn)).

Upvotes: 1

Related Questions