求问这两份代码时间差距为什么这么大

滑蒻稽 @ 2021-07-18 09:32:40

//慢
    for(; nowHead[u] && rest; nowHead[u] = nxt[nowHead[u]]) {
        const int &i = nowHead[u];

//快
    for(int i=nowHead[u];i && rest;i=nxt[i]) {
        nowHead[u]=i;

by _thiscall @ 2021-07-18 09:35:28

@滑蒻稽 nowHead[u]被多次读取，耗时间

by 滑蒻稽 @ 2021-07-18 09:44:07

@_thiscall 但如果 nowHead[u] 在后面的递归过程被更改，回到当前函数时，i 不能跟着变化。

by _thiscall @ 2021-07-18 09:46:11

@滑蒻稽 *(p+i)比p[i]速度快

我也不知道为什么，老师讲指针时讲的，好像跟底层实现（机器语言）有关

by 滑蒻稽 @ 2021-07-18 09:51:13

@_thiscall 这种东西不会在编译的时候被优化吗？

by _thiscall @ 2021-07-18 10:16:30

@滑蒻稽 你可以看看反汇编

by 滑蒻稽 @ 2021-07-18 10:23:52

@_thiscall

普通数组就是一样的，当然如果是 STL 的迭代器我就不知道了。

by _thiscall @ 2021-07-18 10:28:53

@滑蒻稽 你拿原来的代码看看反汇编

by 滑蒻稽 @ 2021-07-18 10:36:39

@_thiscall 我懂您的意思了，就是说如果 ; nowHead[u] && rest; nowHead[u] = nxt[nowHead[u]] 中的 nowHead[u] 是 i，会更快。但是对于当前弧优化来说，如果不用 nowHead[u] 复杂度是错的。

by 滑蒻稽 @ 2021-07-18 11:08:15

@滑蒻稽 收回我的话，由于是有向无环图，这样进行当前弧优化是对的。

by 滑蒻稽 @ 2021-07-18 18:49:25

我终于懂了，如果剩余流量 rest 不够了，是不能把 nowHead[u] 替换为 nxt[nowHead[u]] 的，否则复杂度无法证明。

此贴终结 QAQ。