5个提升你C++程序执行效率的技巧

zhangjinxuan

鱼油们应该刷过oj吧！刷oj时，自信满满的提交，却被一个WA狠狠打脸
有时他也是TLE,RE,分别是超时,运行时错误 的意思，说明你程序的执行效率有亿点点逊...
如何提高执行效率呢？就看以下5条你中招没！
1.memset是一个very good的函数,但他应该用到该用的地方，什么意思呢？看这个代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int a[100000];
   
4. int main()
   
5. {
   
6.     memset(a,0,sizeof(a));
   
7.     //...
   
8. }

复制代码

memset是一个O(n)的函数，那么程序的时间复杂度应是O(n)
但，可以优化吗？
当然可以！把memset这一行去掉即可！
为什么呢？因为本程序的memset的第二个参数是0,没有初始化为0的必要
因为 全局变量默认初始化为0！
但是如果你要初始化其他值的话，就加上吧，或者用别的方法...

2.看看哪个快？

1. //test1.cpp
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4. int main()
   
5. {
   
6.     for (int i=0;i<1e9;++i)
   
7.     {
   
8.          for (int j=0;j<5;++j)
   
9.              1+1==2;
   
10.      }
    
11. }
    
12. //test2.cpp
    
13. #include <bits/stdc++.h>
    
14. using namespace std;
    
15. int main()
    
16. {
    
17.     for (int i=0;i<1e9;++i)
    
18.     {
    
19.          1+1==2;
    
20.          1+1==2;
    
21.          1+1==2;
    
22.          1+1==2;
    
23.          1+1==2;
    
24.      }
    
25. }

复制代码

乍一看，2个代码都是执行5e9次1+1==2,应该都一样吧，但事实并非如此，我们写个测试程序试一试：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.         double st=clock();
   
5.         for (int i=0;i<1e9;++i)
   
6.         {
   
7.                 for (int j=0;j<5;++j)
   
8.                         1+1==2;
   
9.         }
   
10.         double en=clock();
    
11.         printf("test1:%.2f\n",en-st);
    
12.         st=clock();
    
13.         for (int i=0;i<1e9;++i)
    
14.         {
    
15.                 1+1==2;
    
16.                 1+1==2;
    
17.                 1+1==2;
    
18.                 1+1==2;
    
19.                 1+1==2;
    
20.         }
    
21.         en=clock();
    
22.         printf("test2:%.2f\n",en-st);
    
23. }

复制代码

结果竟然出乎意料的打印了不同的值(毫秒为单位)：
test1:4914.00     (4.914秒)
test2:1616.00     (1.616秒)
为什么同样的功能，差异为何如此之大？
因为一个for循环它有许多"多余"的操作，比如开始初始变量，循环一次判断条件，又更新计数器变量，那得多慢！
所以，当循环次数已知并且比较小，推荐使用类似程序2的写法

3.再来看看哪个快？

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. struct test{
   
4.         long double c[30],a;
   
5.         long long b[100];
   
6. }ar[300000];
   
7. bool cmp1(test a,test b){return a.a>b.a;}
   
8. bool cmp2(test &a,test &b){return a.a>b.a;}
   
9. int main(){
   
10.         int st=clock();
    
11.         sort(ar,ar+300000,cmp1); //这个快？
    
12.         int en=clock();
    
13.         printf("test1:%d\n",en-st);
    
14.         st=clock();
    
15.         sort(ar,ar+300000,cmp2); //还是这个快？
    
16.         en=clock();
    
17.         printf("test2:%d\n",en-st);
    
18. }

复制代码

输出：
test1:1184
test2:654
为什么？cmp2仅仅就是加了两个&,两个程序的差距竟这么大？？!
仔细看看，test结构体有一个long double的数组，一个long long的数组,外加一个long double的a，其大小可想而知（内存逊的鱼油们不要轻易尝试！)
其实学过引用函数的都知道，参数加上&,就变成了引用，传过去的是变量的地址，而地址的大小仅仅就是4字节或8字节，比test结构体少好多倍
那有的鱼油就问了：参数很大很小关执行效率有什么关系捏？
其实不然，如果一个函数的参数的大小很大，那么整个函数的开销就很大，所以当参数很大时，建议加上引用或者指针

4.cin vs scanf
学过C++的应该都用过cin
但cin的效率高不高呢？
答：很低，比你想象的还低。有一次做题，用scanf很nice的AC了，但改为cin就奇妙的TLE了
还是不信？那再写个测试程序！

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.         freopen("test1.out","r",stdin);
   
5.         int st=clock();
   
6.         char tmp[20];
   
7.         for (int i=0;i<1000000;++i)scanf("%s",tmp);
   
8.         int en=clock();
   
9.         fprintf(stderr,"test1:%d\n",en-st);
   
10.         st=clock();
    
11.         freopen("test2.out","r",stdin);
    
12.         for (int i=0;i<1000000;++i)
    
13.                 cin>>tmp;
    
14.         en=clock();
    
15.         fprintf(stderr,"test2:%d\n",en-st);
    
16. }

复制代码

程序输出：(假设test2和test1里面都是1000000行的IloveFichc.com)
test1:497
test2:719
所以:勤用scanf，少用cin
不过对于printf与cout的测试我这边竟然是cout比printf快十多倍，不知道是什么原因，所以不敢乱说，感兴趣的鱼油可以试一试或查一查

5.之前讲过函数的开销取决于参数，它也取决于函数体，什么意思呢？看代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.         int a[1000000];
   
5. }

复制代码

写过类似的都知道，他在linux中会提示 段错误（吐核）之类的，而在windows中返回错误码：3221225725 这种就是RE
其实这是栈溢出，一个函数，运行时会加入到系统分配的栈里面，如果一个函数的开销很大，那么栈的空间就不足了，从而产生栈溢出
有解决方法吗？依然写出来了，当然有！
方法一：static int a[MAXN];   使用静态数组，这样不会栈溢出(具体啥原因俺也不知道)
方法二：使用stl容器
方法三：定义全局数组

6.不是说只有5条吗？怎么还有第6条？
那就是一个大问题了，我觉得灰常多萌新会犯这个错误的...









如果有帮助那就 回帖！顶！加评分！嘻嘻~ 这就是第6条~

[本文为本萌新原创，为个人经验，仅供学习使用，若有错误希望大佬指正，指正有鱼币奖励!]

额外减小

大佬！建议加精

dolly_yos2

第一条是错的，如果去查询一下 C++ 的标准就能看到标准规定 std::string 的 size() 方法的复杂度是 O(1) ，不存在遍历变为 O(n^2) 的情况。退化仅对于 strlen 而言很可能是正确的，因为尽管标准并未规定这一函数的时间复杂度，通常的实现中其被实现为线性于字符串长度。

zhangjinxuan

dolly_yos2 发表于 2022-8-30 12:58
第一条是错的，如果去查询一下 C++ 的标准就能看到标准规定 std::string 的 size() 方法的复杂度是 O(1) ， ...

这个可能存在点争议，其实我一直认为string的size方法是O(n)的，有争议就换成vector吧！

dolly_yos2

dolly_yos2 发表于 2022-8-30 12:58
第一条是错的，如果去查询一下 C++ 的标准就能看到标准规定 std::string 的 size() 方法的复杂度是 O(1) ， ...

感谢您的快速改正。不过说实话我觉得很奇怪，您在编写更改后的内容的时候没有思考过“ std::string 的 size() 方法是常数时间复杂度，那 std::vector 的 size() 方法是不是真的线性于元素个数”之类的问题呢？
标准中同样规定了，对于标准容器（定义在 <array>, <deque>, <forward_list>, <list>, <vector>, <map>, <set>, <unordered_map>, <unordered_set>, <queue>, <stack> 和 <span> 中），它们的 size() 方法时间复杂度一律为常数即 O(1) ，都不存在您描述的循环中每次使用 size() 方法获取元素个数导致复杂度退化为 O(n^2) 的情况。

zhangjinxuan

dolly_yos2 发表于 2022-8-30 13:21
感谢您的快速改正。不过说实话我觉得很奇怪，您在编写更改后的内容的时候没有思考过“ std::string 的 si ...

我更迷糊了，我测试一下。。。

zhangjinxuan

我迷糊了，我看到一篇博客，上面说对于vector for(int i=0;i<a.size();++i)比int n=a.size();for (int i=0;i<a.size();++i);要慢，要不你看看？
https://blog.csdn.net/tjcwt2011/article/details/124860053

dolly_yos2

zhangjinxuan 发表于 2022-8-30 13:13
这个可能存在点争议，其实我一直认为string的size方法是O(n)的，有争议就换成vector吧！

这是标准中明确规定的内容，您可以查阅 C++ 标准中的 [string.capacity] 一节。如果实现中出现了 std::string 的 size() 方法实际上复杂度是 O(n) 的情况，只能说明这一实现并不符合标准，是错误的。当然可能我们有时碍于特定的原因不得不使用不完全符合标准的语言实现，但是为了讨论的通用性考虑，可能更适合基于标准而不是某个（尤其是缺陷的）实现讨论，除非将讨论范围严格限定。
另外，查看 GCC 的实现也能看到其 std::string 的 size() 方法实现的时间复杂度是常数的。

zhangjinxuan

哎~算了，既然有争议就把第一条删了吧

dolly_yos2

zhangjinxuan 发表于 2022-8-30 13:32
我迷糊了，我看到一篇博客，上面说对于vector for(int i=0;i

大概看了一下，实验现象我没尝试复现，但是文中描述的实验结果也是心理上能接受的，可能每次调用 size() 方法和提前缓存长度虽然时间复杂度形式相同，但实际执行的指令数后者更少，或者后者对缓存等加速机制更友好等等，这些都可能导致这种速度上的差异。讨论的关键不在这些常数的差异，而在于复杂度不会因为每次调用 size() 方法而从 O(n) 退化为 O(n^2) ：在真正对性能要求苛刻的环境即 n 很大的场景下，操作次数是 n 还是 5n 远不如是 5n 还是 n^2 的影响大。
为了尽可能的压榨性能，当然可以预先保存长度在循环中使用，只是这带来的速度改进可能并不显著。

zhangjinxuan

有可能因标准而异

zhangjinxuan

明白了，C++98以前，size是O(n)的，之后就是常数阶了

zhangjinxuan

因编译器和标准而异

zuinulidexing

kerln888

kerln888

脸黑啊。。。

kerln888

学习了，好技巧

沅源不嘤

好耶

zhangjinxuan

kerln888 发表于 2022-8-30 15:23

10%都能中，可以去买彩票了

aaron0919

其实初始化数组为没必要这么麻烦，
字符数组不用初始化，
数组可以直接

1. int a[100010] = {0};

复制代码