CODEWITHSUNDEEP
c++
tom
tom

Reputation: 1

Is accessing container element time-consuming?

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)

Upvotes: 0

Views: 137

Answers (2)

MarkB
MarkB

Reputation: 1988

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).

Upvotes: 2

pptaszni
pptaszni

Reputation: 8217

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 quickbench I see not that much difference between running just the algorithm and storing the results in std::map or std::unordered_map. I used randomized integers for testing, which is maybe not the best for GCD algorithm, but you can try other approaches.

Code under benchmark without storage:

constexpr int N = 10000;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> distrib(1, N);
benchmark::DoNotOptimize(gcd(distrib(gen), distrib(gen)));

and with storage:

benchmark::DoNotOptimize(res[gcd(distrib(gen), distrib(gen))]++);

Results:

results

Upvotes: 2

Related Questions