How to Optimize Your Code in C++

How to Optimize Your Code in C++

怎麼優化你的程式(C++篇)

序

「人生って、優しくなるためにあるんだと思っています。

昨日の私よりも、今日の私がちょっとだけ優しい人間であればいいなと思いながら生きています。」

 — 牧之原翔子,《青春豬頭少年不會夢到兔女郎學姊》

不專業翻譯:

我覺得人生的意義就是要變得更好。

如果今天的我能比昨天的我更好，這樣就好了。

寫程式也是如此呢。

如果今天我寫出來的程式比昨天的我寫出來的程式更好，我也會覺得很開心。

希望這篇文章能幫助各位,讓自己的程式變得更好😊。

優化的方式

優化的方式有很多種，大概可分成：

1.I/O 優化

2.演算法優化

3.其他小技巧

I/O優化

這是最直接的一種優化方式，因為I/O是大多數程式語言中最費時的處理，所以選擇好的I/O方式是很重要的。

cin/cout

C++最基本的I/O是用cin/cout

但是它的速度真的很慢很慢，Zerojudge有很多題目是無法用cin/cout完成的。

再次放上這個給大家做參考：

 Analysis of Various I/O Methods for Large Datasets in C++

我們要怎麼優化cin/cout呢？

方法 1：

換成scanf()/printf()

這招應該大家都會吧，scanf()/printf()的彈性較cin/cout低，但速度也較快，雖說近來也有文章表示scanf()/printf()比cin/cout慢，但根據我的經驗，scanf()/printf()還是比較快的。

方法 2：

加入

ios::sync_with_stdio(0);

cin.tie(0);

這也是非常熱門的優化手法。

至於原理就不再贅述，已經有太多其他的文章做出很好的說明了，如：

C++的輸出入cin/cout和scanf/printf誰比較快？

經優化過的cin/cout，速度跟scanf()/printf()不相上下，有時甚至更快。

大部分的人就只優化到這裡而已。

但是Zerojudge還有少部分題目是用這個都無法通過的。

例如:b949(原本可以過的，大數運算解法被卡掉了), c223,c651(原本是可以過的，更新後就不行了),e273,e295等等......。

接下來，我們可以用<stdio.h>裡的I/O函式，把I/O優化的更快。

getchar()/putchar()

getchar()/putchar()是最基本的方式。

它們可以讀入/輸出一個字元。

但是，在Zerojudge中，幾乎所有讀入/輸出檔都是由字元組成的。

所以getchar()/putchar()是很好用的喔~

我就示範一個讀入/輸出 long long int 的函式吧。

code如下:

1. long long readint(){
2. long long a=0;
3. char c='0';
4. while(c>='0'&&c<='9'){
5. a=(a<<3)+(a<<1)+c-'0';
6. c=getchar();
7. }
8. return a;
9. }
10. void writeint(long long d){
11. if(d==0){
12. putchar(48);
13. return;
14. }
15. int len=0;
16. char n[20];
17. while(d>0){
18. n[len]=d%10+48;
19. len++;
20. d/=10;
21. }
22. for(int i=len-1;i>=0;i--) putchar(n[i]);
23. }

當然啦，getchar()/putchar()不是最快的I/O函式，上面的函式也還有不少可以優化的地方。

也許有耐心的看完這篇文章後，你也可以把上面的函式優化一次，相信速度會更快喔。

接下來就要進到黑科技的領域了。

意思是以下提供的I/O方式不一定完全安全，使用時請小心評估風險喔。

I/O黑科技

1.getchar_unlocked()/putchar_unlocked()

這兩個函式是getchar()/putchar()的進化版，速度完全是不同的等級。

但是不保證完全安全。

用法跟getchar()/putchar()完全一樣，只要把上面的getchar()/putchar()換成getchar_unlocked()/puchar_unlocked()就能用了。

2.fread()/fwrite()

這兩個函式比getchar_unlocked()/putchar_unlocked()更快。

例(e295)：
fread_unlocked()/putchar_unlocked()：26ms
getchar_unlocked()/putchar_unlocked()：34ms

它們也都有_unlocked()版本，只是速度差不大。

用法是寫出一個自己的getchar()/putchar()函式，接下來就可以把它們當成getchar()/putchar()用了。

code如下

1. static char buf1[100000],*p1=buf1,*p2=buf1;
2. char getc(){
3.     return p1==p2&&(p2=(p1=buf1)+fread(buf1,1,100000,stdin),p1==p2)?EOF:*p1++;
4. }
5. char buf2[100000],*pp=buf2;
6. void putc(const char c){
7.     if(pp-buf2==100000)fwrite(buf2,1,100000,stdout),pp=buf2;
8.     *pp++=c;
9. }

buf的大小可以視測資大小而自行調整

*Zerojudge禁止使用fwrite()，所以我都用fread()/putchar_unlocked()

*當然還有mmap()或是ifstream()、streambuf，不過那些用法都太難了，不建議使用，而且mmap()只能在Linux/Ubuntu作業系統上用，Windows不能用。

*想要知道關於更多mmap()的知識，可以參考以下連結：
https://stackoverflow.com/questions/5588605/mmap-vs-read

https://stackoverflow.com/questions/9817233/why-mmap-is-faster-than-sequential-io

https://lemire.me/blog/2012/06/26/which-is-fastest-read-fread-ifstream-or-mmap/

https://eklausmeier.wordpress.com/2016/02/03/performance-comparison-mmap-versus-read-versus-fread/

演算法優化

這個部分應該不用我講吧。

演算法是程式設計的基本功。

面對題目時，要選擇複雜度較合理的演算法。

各種小技巧

這個部分的分類有點多，我會盡量幫大家整理。
以下的技巧中，若
標題為藍色，代表這是對大部分編譯器/作業系統都有效的優化手法。
標題為綠色，代表雖然不是對大部分編譯器/作業系統都有效，但在 Zerojudge 的環境是有效的。
標題為黃色，代表這種手法只對特定作業系統或舊式編譯器有效，已被新式編譯器的功能取代。

1.#pragma

這是蠻常見的優化手法，透過前置處理器控制編譯的過程

用法：

1. #pragma GCC optimize("O0")//不優化(預設)
2. #pragma GCC optimize("O1")//優化一點
3. #pragma GCC optimize("O2")//優化更多
4. #pragma GCC optimize("O3")//O2優化再加上inline函式優化
5. #pragma GCC optimize("Os")//針對程式大小進行優化(程式最小)
6. #pragma GCC optimize("Ofast")//O3加上一些快速但不安全的數學運算

因為上面的說明有點簡略，我再詳細說明一次：

O0：關閉所有最佳化選項

O1/O：試著產生更小，更快的執行檔，但不要增加太多編譯時間。採用的技術包含合併完全相同的常數、基本迴圈最佳化，以及在連續的函示呼叫之後，將堆疊予以分組，沒有數字的O和O1是一樣的。

O2：幾乎採用所有不涉及程式大小和執行速度之間折衷的最佳化技巧，但是編譯時間會被拉得更長，除了O1的最佳化以外，編譯器還會執行公用子運算式消去法(common subexpression elimination，CSE)，這個過程需在程式裡偵測數學的對等運算式，並要為了估算它們一次重寫程式碼，再將估算結果存放在未具名的變數以便重複使用。此外，為了降低資料在記憶體和CPU暫存器之間移動所花費的等待時間，還會重新編排指令的順序。附帶一提，這個層級所進行的資料流分析，也允許編譯器針對為初始的變數發出額外的警告。

O3：產生inline函式，並且讓變數可以更彈性的配置到處理器的暫存器，他還包含了所有O2的優化

Os：針對檔案大小進行最佳化，它很像O2，但並沒有可能會增加程式碼大小的效能最佳化，此外，和其他在2次方位元組邊界跳躍目的地等，都會關閉。

Ofast：所有O3優化皆包含在內，再加上不安全的數學運算優化(-ffast-math)

效應分析如下：

圖源:https://www.quora.com/What-does-pragma-Ofast-do-in-C++

---------------------------------------------------------------------------------------
以下為Emilia大大補充

在Zerojudge解題時，我們通常會使用下列的#pragma優化：

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#pragma comment(linker, "/stack:200000000")

第一個除了不安全數學運算+O3優化，還加了迴圈展開、忽略堆疊溢出攻擊。

第二個是針對CPU的指令集擴充，有些只被intel支援，有些則是AMD有。

其中"tune=native"可以啟用運行電腦所支援的所有指令集，並在指令集下針對運行電腦優化。

第三個是加開堆疊，可以讓遞迴函式跑多一點，不過需要這樣的話，代表你寫出了假解。

跟第三個同樣功能的"asm("mov %0,%%esp"::"g"(stack+S));"，不過不一定每個judge都可以用這個。

---------------------------------------------------------------------------------------

2.位元運算(Bit Manipulation)

這也是一個常見的優化手法，不過較優良的編譯器已經可以取代其部份的功能。

為什麼位元運算會比較快呢？

請參考下面的表格

操作	相對的處理時間
檔案輸入/輸出	1000
new/delete	800
三角函數(sin,cos,tan…)	500
浮點運算	100
整數除法(/ , %)	30
整數乘法	20
函式呼叫	10
assert	8
簡單的陣列索引	6
位元平移(<<,>>)	5
整數加法/減法	5
取出指標的內容	2
位元AND,OR,XOR,NOT(& , | , ^ , ~ )	1
邏輯AND,OR,XOR,NOT(&& , || , ^ , ! )	1

可以看到，位元運算是最不耗時的操作之一。

當然，這裡的處理時間是相對的，實際的處理時間都可能短到必須用ns(奈秒)(10^-9

秒)來計算，不過積少成多，只要測資夠大，差距就會出現了。
*參考值：Zerojudge的主機大概1秒可以做10¹⁰次位元運算(使用C++時)。

那既然位元運算這麼厲害，有什麼可以應用的點呢

1.乘/除2的乘冪時：

我們可以看到，整數乘/除法是很慢的運算。
當乘數/除數是2的乘冪時，我們可以用位元平移來加速。
範例：

1. int x=1,y;
2. y=x<<3; //等同於y=x*8(也就是2^3)
3. cout<<y<<'\n';//輸出為8
4. y=y>>2;//等同於y=y/4(也就是2^2)
5. cout<<y<<'\n';//輸出為2

大部分優良的編譯器會幫你做到這點。
練習題：a414

2.判斷奇偶

模除(%)也是一個很慢的運算。

如果是判斷奇偶，或是是否能被2的乘冪整除。
我們可以用位元AND(&)來取代。

範例：

1. int a=1,b=2;
2. cout<<(a&1)<<'\n';//等同於(a%2)，輸出是1
3. cout<<(b&1)<<'\n';//等同於(b%2)，輸出是0

3.判斷是否為2的乘冪

若用naive的寫法，判斷是否為2的乘冪需要O(logn)的時間。

但是我們也可以用位元運算來加速。
範例：

1. int a=65536,b=65535;
2. cout<<(a&&(!(a&(a-1))))<<'\n';//輸出是1,為2的乘冪
3. cout<<(b&&(!(b&(b-1))))<<'\n';//輸出是0,不為2的乘冪

練習題：e284

3.inline函式

我們可以從上面的表格得知，呼叫函式也需要一定的時間。
要怎麼縮減這個時間呢？
我們可以用inline函式來加速此過程：
如果以下列程式碼為例：

1. int square(int x){
2. return (x*x);
3. }
4. int main(){
5. //...
6. x=square(x);
7. }
8. //V.S
9. inline int square(int x){
10. return (x*x);
11. }
12. int main(){
13. //...
14. x=square(x);
15. }

前者產生的組合語言程式長這樣：

1. lable "int square(int x)"
2.         link a6, #0
3.         movel a6@(8), d1
4.         mulsl a6@(8), d1
5.         move d1, d0
6.         unlk a6
7.         rts
9. lable "main"
10. //....
11. //      x=square(x)
12. //
13.         move a6@(-4),sp@-
14.         jbsr "void square(int x)"
15.         addqw #4, sp
16.         movel d0,a6@(-4)

後者則是：

1. lable "main"
2. //....
3. //      x=square(x)
4. //
5.         movel d1, a6@(-4)
6.         movel a6@(-4), d0
7.         muls d0,d0
8.         movel d0,a6@(-4)

就算看不懂組合語言，也至少看的出來後者較短，執行速度也較快。

4.register修飾子

register修飾子可以指定這個變數為常用的變數，須將它放在較快的暫存器(register)，而非較慢的主記憶體中，以獲得較快的運算速度。
暫存器的數目隨著電腦的種類不同而有所不同，有些PC只有2個，多數電腦擁有10幾個，超級電腦則有多達128個暫存器。
如果宣告多於此電腦所擁有的暫存器數量，則會忽略register修飾子，將此變數放在主記憶體中。
register在C++11之後就被棄用了，C++11之後的編譯器會忽略register修飾子並發出警告。

5.用指標取代陣列索引

我們可以注意到，指標的速度比陣列索引快了不少。
所以我們盡量把陣列索引換成指標。
範例：

1. inline void write(uint_fast16_t x) {
2. static int stk[9],top=0;
3. int *ptr;
4. ptr = &stk[0];
5. while(x){*ptr=x%10;x/=10;ptr++;}
6. ptr--;
7. while(ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');ptr--;}
8. }

*這是我在e273的輸出函式(題目沒有0，所以我沒有處理0的特殊狀況，建議不要拿來用)。
這可以應用在需要建表的題目，用指標查表會很快喔

6.使用內建函式

大部分的內建函式都有很好的效率，能用就多用吧。

7.少用浮點數運算

從上表可以看到浮點數運算很慢，可以用整數就用整數吧。
內建函式pow()和sqrt()都是浮點數運算，盡量少用。

8.安排迴圈的順序

較複雜的迴圈放在內部，簡單的迴圈在外部。
大部分優良編譯器會幫你自動安排。

9.運算小技巧

1. ++x 比 x++ 快。
2.x+=y 比 x=x+y 快。
3.int x=y 比 int x,x=y; 快。

這些小技巧編譯後會產生較短的組合語言。

10.do-while()比while()快

do-while()編譯後會產生較短的組合語言。

11.使用unsigned int

在某些系統中，unsigned int 會比 int 快。

12.int_fastXX_t

這是新的一種黑科技(C++11之後才出現的)。

這是處理速度最快的型別，使用的方式跟 int 一樣。
有以下幾種類型：
int_fast8_t      (範圍：-128~127)
int_fast16_t    (範圍：-32768~32767)
int_fast32_t    (範圍：-2147483648~2147483647)
int_fast64_t    (範圍：-2^63~(2^63)-1)
uint_fast8_t    (範圍：0~255)
uint_fast16_t  (範圍：0~65535)
uint_fast32_t  (範圍：0~(2^32)-1)
uint_fast64_t  (範圍：0~(2^64)-1)

不過他們好像會占用更多空間。
int_fast32_t 的範圍是32bits的整數，但是它用的記憶體大小不一定會是32bits，而是大於等於32bits。

另外，int_fast32_t 跟 double 相乘的時候，精度似乎會跑掉，還請大家注意一下。

關於它的速度，我幫大家測試了一下(因為網路上好像都沒有關於它的文章)
我用的是e284測資#2的測資，有5000000個int。
測試code：

1. #include<iostream>
2. #include<fstream>
3. #include<ctime>
4. #include<cstdlib>
5. using namespace std;
6. int main(){
7.     ofstream out("e284_02.out");
8.     freopen("e284_02.in","r",stdin);
9.     int n;//int_fast32_t
10.     while(cin>>n){
11.           out<<((((((n-1)+1)/2)*2)>>1)<<1)<<'\n';
12.     }
13. }

結果：

1.uint_fast64_t          ：6.790s
2.unsigned long long ：6.836s
3.uint_fast32_t         ：6.863s
4.int_fast64_t           ：6.968s
5.unsigned int            ：7.058s
6.long long                 ：7.114s
7.int_fast32_t           ：7.174s
8.register long long  ：7.201s (參考值)
9.register int              ：7.383s (參考值)
10.int                            ：7.863s

它其實表現沒有預期的好，但還是比原本的 int 快。


以上就是我的分享
請大家不吝賜教，多在討論區發言
希望這篇文章能幫助大家寫出更好的程式