iterator dereferencing cost a huge time-CodePudding

I solved a problem with Set operations like upperbound, iterator dereferencing etc. It solves in around 20 seconds. The general problem is I am iterating over group of numbers (i*(i-1)/2) until it is less than 2 * 10^5, and then complete a DP vector. So in my algorithm for each number "x" I get the upper_bound,"up", then starting from the beginning iterate over the numbers until reach to "up". The solution does the same but it does not run upper_bound and dereferencing, but instead it directly calculate the i*(i-1)/2, which i previously calculated and stored in vset. the number of operations for both algorithm is almost same, around 80*10^6, which is not super big number. But my code takes 20 seconds, solution needs 2 seconds.
Please look at my code and let me know if you need more information about this:

1- vset has 600 numbers, which is all numbers in the form of i*(i-1)/2; less than 2*10^5
2- vset is already sorted as it is increasing
3- the final vector "v" in both algorithm is exactly same
4- cnt, number of operation for both is almost same. 80,000,000
5- you can test the codes with n = 199977.
6- On my computer, corei7 32G RAM, it takes 20 seconds, on server accepted around 200 Mili seconds, this is very strange to me.

typedef long long int llint;
int n; cin >> n;
vector<llint> v(n 1, INT_MAX); 
llint p = 1;
llint node = 2;

llint cnt = 0;
for (int i = 1; i <= n; i  )
{
    if (v[i] == INT_MAX)
    {
        for (int s = 1; (s * (s - 1)) / 2 <= i;   s)
            v[i] = min(v[i], v[i - (s * (s - 1)) / 2]   s) , cnt  ;
    }
    else cnt    ;
}
cout << cnt << endl; // works in less than 2 seconds

The Second solution takes 20 seconds.

typedef long long int llint;
int n; cin >> n;
vector<llint> v(n 1, INT_MAX); 
llint p = 1;
llint node = 2;
vector<int> vset;
while (p <= n) // only 600 numbers 
{
    v[p] = node;
    vset.push_back(p);
    node  ;
    p = node * (node - 1) / 2;
}
llint cnt = 0;
for (int i = 1; i <= n; i  )
  {
    if (v[i] == INT_MAX)
    {
        auto up = upper_bound(vset.begin(), vset.end(), i);
        for (auto it = vset.begin(); it != up; it  ) // at most 600 iteration
        {
            cnt  ;
            int j = *it;
            v[i] = min(v[j]   v[i - j], v[i]);
        }
    } 
    else cnt    ;
   }
cout << cnt << endl; // cnt for both is around 84,000,000

So the question is about something I cannot figure out: which operation(s) here is expensive? going through the iterator? dereferencing the iterator? there is no more difference here but the time is TEN TIMES MORE. thanks

CodePudding user response：

Thanks to all guys that commented and helped me to figure out the issue. I realized that the reason that I have slow performance was Debug Mode. So I changed it to Release Mode and it works in less than 2 seconds. There is a similar question, may help you more. I used Visual Studio C on Windows 10