Is accessing container element time-consuming?-CodePudding

I want to count GCD of integers and save them. I find that the time consuming part is not to calculate GCD but to save result to the map. Do I use std::map in a bad way?

#include <set>
#include <iostream>
#include <chrono>
#include "timer.h"

using namespace std;

int gcd (int a, int b)
{
    int temp;
    while (b != 0)
    {
        temp = a % b;
        a = b;
        b = temp;
    }
    return(a);
}

int main() {
    map<int,int> res;
    {
        Timer timer;
        for(int i = 1; i < 10000; i  )
        {
            for(int j = 2; j < 10000; j  )
                res[gcd(i,j)]  ;
        }
    }

    {
        Timer timer;
        for(int i = 1; i < 10000; i  )
        {
            for(int j = 2; j < 10000; j  )
                gcd(i, j);
        }
    }
}

6627099us(6627.1ms)

0us(0ms)

CodePudding user response：

You should use some real benchmarking library to test this kind of code. In your particular case, the second loop where you discard the results of gcd was probably optimized away. With

CodePudding user response：

You are using std::map correctly. However, you are using an inefficient container for your problem. Given that the possible values of gcd(x,y) are bounded by N, a std::vector would be the most efficient container to store the results.

Specifically,

int main() {
    const int N = 10'000;
    std::vector<int> res(N, 0); // initialize to N elements with value 0.
    ...
}

Using parallelism will speed up the program even further. Each thread would have it's own std::vector to compute local results. Once a thread is finished, the results would be added to the result vector in a thread-safe manner (e.g. using std::mutex).