迭代器解引用/upper_bound致性能差异？两种DP算法耗时排查

云原生阿岚

2026-8-7

性能差异排查：两种DP算法的耗时对比

问题概述

两种DP算法操作数相近（约8000万次），最终输出的vector结果完全一致，但本地Core i7 32G环境下耗时差距达10倍：
- 直接计算s*(s-1)/2的版本耗时<2秒；
- 使用upper_bound、迭代器遍历/解引用的版本耗时约20秒。
服务器环境下后者仅需200ms，本地与服务器的性能差异显著。
背景细节：
1. vset存储600个小于2×10^5的i*(i-1)/2型有序数值；
2. 测试用例为n=199977。

代码实现

代码1（耗时<2秒）

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;

代码2（耗时20秒）

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;