泛谈OI中的那些卡常（测试版）

$\boxed{\begin{matrix}\textsf{team109博客管委会委员长令2020年第一号}\cr\footnotesize\textsf{\kern{15pt}由于team109即将中考，由team109博客管委会委员长提出的停更提案由team109博客管委会以无记名方式}\cr[-3pt]\footnotesize\textsf{以1票赞成、0票反对、0票弃权的绝对优势通过，本文停更，为期两月。特此告知。}\kern{90pt}\cr[-2pt]\kern{300pt}\small\rm{team109}\cr[-4pt]\kern{300pt}\scriptsize\textsf{2020年4月10日}\end{matrix}}$ 由于我的电脑不能代表所有电脑的表现（比如我的电脑cin比fread快）,所以部分内容需要大家帮忙验证。 ____ 同步在知乎。[链接](https://zhuanlan.zhihu.com/p/116428076) 知乎的TeX不好，而且没有Markdown，样式会略有区别。  我是定位ZJ的一名退役OIer，由于卡常而臭名昭著。下面分享一些技巧。主要为时间卡常。 本文共计[咕咕]字，阅读约需[咕咕]分钟。（由于还没完工所以不统计字数） 本文有些优化在开O2后还不如正常做法，会打上$\color{red}\xcancel\colorbox{orange}{\color{white}{\textsf{O2}}}$标志。 有些优化在不同机器下效果不同，可能还不如正常方法，会打上$\colorbox{#eecc55}{\color{white}\text{谨慎}}$标志。 有些优化我自己都没实现过，会打上$\color{grey}{\boxed{\text{野心}}}$标志。 有些优化兼容性不好，可能CE或有别的问题，会指出。 有些内容会大大降低代码可读性，请在保证答案正确后再深度优化。 因为我在役时也只有提高水平，可能有一些错误，而且不会那些高深的卡常，请大佬（或自称蒟蒻）指正。如果在某些机子上运行出问题或速度还不如正常方法或效率不稳定或可能被卡或不适用于特定场合或有任何其他的问题，请告知我。我目前初三，可能更新、处理反馈都很慢。 我太蒻了。部分较高深内容引自@[huanghaox1212](https://www.luogu.com.cn/user/75765) 的[博客](https://www.luogu.com.cn/blog/Howershine950644/)中的一些文章以及其他一些来源，会标注出。 **转载请注明出处。**(注为本文或知乎链接均可)**并请勿用于商业用途。** # 1.压行 ## 1.1 短路运算符和三目运算符 ## 1.2 利用返回值 ## 1.3 逗号表达式 ## 1.4 还没取好名字 # 2.内存与缓存 # 3.位运算 # 4.`inline`，`register`及其他 # 5.利用中间变量 # 6.其他 # 7.应用实例——I/O优化 我只会用getchar/putchar。用fread请移步前面那位大佬的博客。streambuf请看[这篇洛谷日报](https://www.luogu.com.cn/blog/encore/io-you-hua-nei-suo-shi)。更高深的mmap请自行找资源。 ## 7.1 整数 ### 7.1.0 关于cin的两个优化 (待更 ### 7.1.1 read（这部分内容目前仅在自家机器(少部分还有洛咕IDE)上试过。请各位走过路过帮忙[验证一下可靠性与效率](https://www.luogu.com.cn/blog/team109/publictest)） 先给出标配版，最兼容的版本，在任何时候不会炸。 ```cpp inline int read() { register char ch=getchar(); register int x=0; register bool b=0; while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); (ch=='-')&&(ch=getchar(),b=1); while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar(); if(b)return -x; return x; } ``` **以下网络流传版本已被初步鉴定为负优化，不管是否O2** - 看到有人说isalpha比ch>='0'&&ch<='9'快。经测试发现并没有。 - 将`if(b)return -x;`变为`b&&(x=-x);` - 将`(ch=='-')&&(ch=getchar(),b=1);`变成`(ch=='-')&&(b=1,ch=getchar());`或`(b=ch=='-')&&(ch=getchar());`。事实上，在(INT_MIN,INT_MAX)区间内随机数测试后，发现这个改动对效率影响不小。 - `x=(x<<1)+(x<<3)+ch-48`或`x=x+(x<<2)<<1+ch-48`。 **以下是可行的优化，但未经充分验证** - `x=x*10+(ch^48)` - (待更 但我们还不够。**常数优化的一个关键词就是用牺牲兼容性来换取对特定情境中的高效。** 于是就有了这些东西： （待续 ### 7.1.2 print 待更 ## 7.2 字符串 $\qquad$没有迹象表明用printf输出字符串比一个一个putchar快。甚至在字符串比较短时效率可以相差十倍。但在字符串长度超过1000时已经比putchar慢不了多少。开O2对二者的效率优化都不大。 $\qquad$然后我们发现puts的速度碾压这两者大约6倍。 $\qquad$据说洛谷曾经可以用puts输出然后把那个回车用putchar(8)(即退格)吃掉，但现在貌似不行了。至于puts效率为何这么优秀，我百度半天没结果，C++Reference也没写。 $\qquad$问题是怎么在不输出空格的前提下利用puts的高速的特点呢？C++Reference告诉了我们答案：用fputs。 `fputs("歪比巴卜歪比巴卜",stdout);` $\qquad$效率比puts还吓人。即使把那个\n补回来，`fputs("歪比巴卜歪比巴卜\n",stdout);`还是比puts快。 经过一系列测试，发现fputs在一次输出2个字符时跟putchar差不多快，输出的字符越多优势越碾压。于是又有了一条建议：如果要一次输出多个字符串的，请合并输出。因为调用fputs这个操作本身很费时。`fputs("abcdefghijklmnopqrstuvwxyz",stdout);`的耗时在我的电脑上只有`fputs("",stdout);`的两倍。这一点也适用于printf。 然后给出C++Reference给出的fputs的例子，不代表我的码风： ```cpp #include <stdio.h> int main () { FILE * pFile; char sentence [256]; printf ("Enter sentence to append: "); fgets (sentence,256,stdin); pFile = fopen ("mylog.txt","a"); fputs (sentence,pFile); fclose (pFile); return 0; } ``` ## 7.3 一个例子 。 未完工..... 你谷Markdown和KaTeX可能有更新，格式可能失常。 ### 鸣谢名单： ##### 帮助测试的朋友 （还没有 ##### 提供测试环境的 - 洛谷在线IDE及题目系统 - BloodShed DEV-C++