为什么变量位置不同,运行速度能有这么大差别啊

P1983 [NOIP2013 普及组] 车站分级

GalenoJiao @ 2024-07-19 16:47:15

// 能过的代码 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int n, m;
int g[MAXN][MAXN];// 用邻接矩阵不会重复建边 有向边 i->j表示i车站的等级高于j 
int in[MAXN], si; 
struct Node{// 拓扑排序的节点 
    int id, ord;
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    bitset<MAXN> ext; // 1表示这次出现过,0表示这次没出现过
    int st, ed, tmp;// 始发站、终点站
    for(int i = 1; i<=m; ++i){
        ext.reset();
        cin >> si >> st;
        ext[st] = 1;
        for(int i = 1; i<si-1; ++i){
            cin >> tmp;
            ext[tmp] = 1;
        }
        cin >> ed;
        ext[ed] = 1;
        // 建边
        for(int i = st; i<=ed; ++i){
            if(!ext[i]){// 出现过的比没出现过的大 
                continue;
            }
            for(int j = st; j<ed; ++j){
                if(ext[j] || g[i][j]){
                    continue;
                }
                g[i][j] = 1;
                in[j]++;
            }
        } 
    }

    queue<Node> q;
    for(int i = 1; i<=n; ++i){
        if(in[i]==0){
            q.push(Node{i, 1});
        }
    } 
    int maxOrd = 1;// 最大拓扑序 
    while(!q.empty()){
        Node u = q.front(); q.pop();
        for(int i = 1; i<=n; ++i){
            if(!g[u.id][i]) continue;
            in[i]--;
            if(in[i]==0){
                q.push(Node{i, u.ord+1});
                maxOrd = u.ord+1;// 晚入队的一定不比早入队的小 
            }
        } 
    }

    cout << maxOrd;
    return 0;
}
为什么我把si和queue定义的位置改变一下,运行速度能有这么大差别啊。但是改变tmp就不会 (´・ω・`)? si在全局 si在主函数里
queue在全局,tmp在全局 1.70s 1.82s
queue在全局,tmp在主函数 1.75s 1.82s
queue在主函数,tmp在全局 1.36s 1.78s
queue在主函数,tmp在主函数 1.35s 1.81s

我知道可能和编译器的优化有关,但是改变 si 位置对速度的影响这么大,而改变 tmp 位置却对速度几乎没有影响,我无法理解 (◎_◎)

有大佬能解释一下吗,非常感谢!


by Obijeb @ 2024-07-19 16:55:52

要不关掉O2再测一轮() @GalenoJiao


by YuzhenQin @ 2024-07-19 17:13:25

选择 C++14 提交都能通过,选择 C++14 (GCC9)si 在主函数内无法通过。

使用 Compiler Explorer 发现当 si 在全局时,存储在寄存器里,在主函数内时,存储在栈里。


by GalenoJiao @ 2024-07-19 17:19:41

关掉O2 si在全局 si在主函数里
queue在全局,tmp在全局 1.67s 1.80s
queue在全局,tmp在主函数 1.67s 1.88s
queue在主函数,tmp在全局 1.35s 1.78s
queue在主函数,tmp在主函数 1.35s 1.82s

|