<style> .reveal .slides { text-align: left; font-size:28px; } </style> # debug 技巧 ---- - linux 指令 - 對拍 - Debugging template --- ## 為什麼要學 linux 指令 ? ---- ## ICPC 國際大學生程式設計競賽 https://icpc2022.ntub.edu.tw/onsite/contest-environment/  ---- ## NCPC 全國大專電腦軟體設計競賽 https://ncpc.ntnu.edu.tw/environment/final.html  ---- - 對開發者較友善 - 更多好用的東西 - 等等對拍也會用到 ---- ## 如果我的電腦是 Windows ? - 雙系統 - Windows Subsystem of Linux (WSL) ---- ## Windows Subsystem of Linux (WSL) https://zhuanlan.zhihu.com/p/47541491 https://hackmd.io/@billsun/BJByCIUHf?type=view <div style="position: absolute; right: 90%;">  </div> <div style="position: absolute; right: 50%;">  </div> <div style="position: absolute; right: 10%;">  </div> ---- ## linux 基本指令 ```shell= cd .. 回到上一層資料夾 cd ../.. 回到上上層資料夾 cd test 到當前目錄的test資料夾 ls 顯示當前資料夾的檔案 cat a.cpp 印出當前檔案的內容 mkdir test 在當前目錄建立 test 的資料夾 rm a.cpp 刪除 a.cpp 的檔案 ``` ---- ## 編譯檔案 g++ solve.cpp -o main -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow ```shell= g++ solve.cpp 編譯solve.cpp的檔案成 a.out 檔 g++ solve.cpp -o ac.out 編譯solve.cpp的檔案成 ac.out 檔 g++ solve.cpp -std=c++14 編譯solve.cpp的檔案成 a.out 檔 並且編譯版本為 c++14 ./a.out 執行 a.out 檔 ``` ## 其他編譯參數 ```shell= -fsanitize=undefined 插入各種undefined behavior檢查，會在執行期輸出錯誤訊息 -Wall -Wextra 把warning都開起來，常能預防bug發生 -Wshadow 當有宣告了相同變數名稱的情形發生時予以警告 ``` ---- g++ solve.cpp -o main -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow ---- 難道每次都要打那麼長嗎 ? ---- ## Alias 可以使用 alias 把原本要打的那串 define 掉 ```bash alias [name]='[value]' ``` 等同於 c++ 內的 #define #define ll long long ```bash alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow` ``` ---- 使用 Alias 之後 ```bash g++ solve.cpp ``` 等價於 ```bash g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow solve.cpp ``` ---- ## 產生質因數 ```bash= factor 100 ``` --- ## debug 競賽中或者平常寫題目時，如果遇到 bug 不能及時找到 有以下方法 1. 團體賽中，可以把 code 印出來自己到旁邊 debug，給其他隊友上機寫其他題目 (前提為有其他題目可以開) 2. 團體賽中，可以把 code 印出來給隊友 debug， (前提為能有效跟隊友溝通並且看得懂你的code) 3. 好好寫對拍 ---- ## 對拍  ---- ## 步驟 1. **寫對拍的 script** 2. 寫一份暴力程式碼 ac.cpp 3. 寫一份產生隨機測資的程式碼 ```gen.py/gen.cpp``` ---- ## 對拍的 script 先將兩份程式碼分別編譯成 ac, wa 不斷用 ``gen.py`` 產生測資放到 input 檔案裡面 再把 input 檔案分別為給 ac, wa 兩份執行檔 用 for 迴圈一直跑到 output 內容不同為止 set -e 可以偵測程式 RE 時會停下來 ```shell= set -e g++ ac.cpp -o ac g++ wa.cpp -o wa for ((i=0;;i++)) do echo "$i" python3 gen.py > input ./ac < input > ac.out ./wa < input > wa.out diff ac.out wa.out || break done ``` ---- 跑到停下來後有兩種可能 1. RUNTIME ERROR  2. WRONG ANSWER  ---- ## 為甚麼要用對拍 - 找不到好的 case 能讓他自己跑 先寫其他題目 - 寫暴力程式碼的時間遠比多吃一次 20 penalty 還要來的划算 - 對拍可以重複驗證程式正確性，de 完原本的 bug 可以再跑一次對拍 因此當比賽時，如果對於錯誤毫無頭緒， 不應該只是盯著程式碼看，而是開始寫對拍才是最有效率的做法 ---- 而平時練習、作業找不到bug的情況也應該要先對拍 真的找不到問題 對拍也對不到 再去問其他電神錯在哪 ---- ## 步驟 1. 寫對拍的 script 2. **寫一份暴力程式碼 ac.cpp** 3. 寫一份產生隨機測資的程式碼 ```gen.py/gen.cpp``` ---- ## 寫一份暴力程式碼 ac.cpp 聽起來好麻煩，為了 debug 還要多寫一份 code 而且不一定寫得出來還有可能錯，怎麼辦? ---- 如果連暴力的程式碼都寫不出來 那你應該多練練你的實作能力... 如果不知道怎麼寫請參考早上 [brute force](https://hackmd.io/@LeeShoWhaodian/bruteforce) 講義 善用 next_permutation 以及好好熟悉遞迴 沒有暴力寫不了的程式碼 只有你不練不夠實作能力 ---- ## 步驟 1. 寫對拍的 script 2. 寫一份暴力程式碼 ac.cpp 3. **寫一份產生隨機測資的程式碼 ```gen.py/gen.cpp```** ---- ## 產生隨機測資 (python) ```python= from random import * n = randint(1, 100) # 隨機產生 1~100的整數 ch = chr(ord('a') + randint(0, 25)) # 隨機產生 'a'~'z' 其中一個字元 choiceSet = sample(s, 4) # 從集合 s 選出 4 個不同的元素 choiceSet = sample(range(1, n+1), 4) # 從整數 1~n 選出 4 個不同的元素 shuffle(arr) # 把序列 arr 順序打亂 ``` ---- ## 隨機產生一組 1~n 的 permutation ```python= from random import * n = randint(3, 6) arr = [i+1 for i in range(n)] shuffle(arr) print(n) print(*arr) #輸出 arr 的內容並且用空格隔開 ``` ---- ## 隨機產生一個長度為 n 的小寫字母字串 ```python= s = "" n = randint(1, 10) for i in range(n): s += chr(ord('a') + randint(0, 25)) print(s) ``` ---- ## 隨機產生一棵樹 每次從比自己小的節點選一個當連接自己的邊 ```python= from random import * n = randint(3, 6) print(n) for i in range(2, n+1): print(randint(1, i-1), i) ``` ---- ## 隨機產生無自環無重邊的一張連通圖 無自環 可以判斷兩個點不相同 無重邊 可以用 dict/map 紀錄哪些邊用過了 連通圖 = 樹 + 一些額外的邊 ---- ## 隨機產生無自環無重邊的一張連通圖 ```python= from random import * n = randint(5, 10) m = randint(n-1, n+3) print(n, m) edge = list() #construct tree for i in range(2, n+1): x = randint(1, i-1) y = i edge.append([min(x, y), max(x, y)]) print(x, y) #add extra edge for i in range(m-(n-1)): x = randint(1, n) y = randint(1, n) while x == y or [min(x, y), max(x, y)] in edge: x = randint(1, n) y = randint(1, n) print(x, y) edge.append([min(x, y), max(x, y)]) ``` ---- ## 產生隨機測資 (c++) [Don't use rand(): a guide to random number generators in C++](https://codeforces.com/blog/entry/61587) mt19937 是 c++ 的一種隨機產生器 ```cpp= mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); int randint(int lb, int ub) { return uniform_int_distribution<int>(lb, ub)(gen); } ``` ---- ## sample code(c++) ```cpp= mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); int randint(int lb, int ub) { return uniform_int_distribution<int>(lb, ub)(gen); } int main(){ int n = randint(1, 10); //產生 0~10 之間的任意整數 char ch = 'a'+randint(0, 25); //產生 a-z 之間的任意字母 vector<int> ord(n); iota(ord.begin(), ord.end(), 1); shuffle(ord.begin(), ord.end(), gen); cout << n << endl; for(int i : ord) cout << i << " "; cout << endl; } ``` ---- ## 練習產測資 隨便拿一場比賽練習每一題如何產測資 [2023 I2CP Pretraining Final Contest](https://codeforces.com/group/dnlUA4rsoS/contest/419656/problems) ---- ```shell= set -e g++ ac.cpp -o ac g++ wa.cpp -o wa for ((i=0;;i++)) do echo "$i" python3 gen.py > input ./ac < input > ac.out ./wa < input > wa.out diff ac.out wa.out || break done ``` --- ## How to Debug ? ---- ## Debug --- Print 大法 可能有問題的那段程式碼 把變數 print 出來 ```cpp= cout << "Before" << endl; for(int i = 0; i < n; i++){ cout << arr[i] << ' '; } cout << endl; . . . cout << "After" << endl; for(int i = 0; i < n; i++){ cout << arr[i] << ' '; } cout << endl; ``` ---- ## 這樣會有什麼問題 ? <span>1. debug 完 bug 忘記註解/刪掉<!-- .element: class="fragment" data-fragment-index="1" --><div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="1" --></span> <span> 2. debug 完把 printer 註解，但沒有註解乾淨<!-- .element: class="fragment" data-fragment-index="2" --><div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="2" --></span> <span> 3. 好麻煩喔 先把所有 cout 都註解la 再把要輸出的反註解<!-- .element: class="fragment" data-fragment-index="3" --> <div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="3" --></span> <span> 4. 喔 好像多註解到要輸出的答案了...<!-- .element: class="fragment" data-fragment-index="4" --><div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="4" --></span> ---- ## 這樣會有什麼問題 ? penalty += 80(20 * 4)  ---- ## cerr debug 時，很常會用cout輸出每個變數的值 在這邊建議輸出debug的值時使用cerr 他輸出的東西只會出現在 Standard error stream 不會輸出在 Standard output stream 答案比對是比對 Standard output stream 的內容 因此就算忘記刪也不會造成影響 ```cpp= // __LINE__ 會輸出呼叫的位置在程式碼第幾行 cerr << "This is debug message on " << __LINE__ << " line : " << x << endl; ``` ---- ## cerr 問題 如果沒有刪掉可能造成 TLE ```cpp for(int i = 0; i < n; i++){ x *= 2; arr[x] += v; for(int j = 0; j < n; j++){ cerr << arr[j] << " "; } cerr << endl; } ``` 原本可能 $O(N)$ 的程式碼變成 $O(N^2)$ 或者常數太大 (輸出數量變成原本的兩倍) ---- ## Debugging template 讓你更好 debug 的工具 ---- ```cpp= [|1-6|7-12|] #ifdef LOCAL // =========== Local =========== void dbg() { cerr << '\n'; } template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } #define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")")) #define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args)) #else // ======== OnlineJudge ======== #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define debug(...) ((void)0) #define orange(...) ((void)0) #endif ``` ---- ## #ifdef LOCAL 如果有 define LOCAL 那就會... ```cpp= #ifdef LOCAL // =========== Local =========== void dbg() { cerr << '\n'; } template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } #define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")")) #define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args)) ``` 否則就會... ```cpp= #else // ======== OnlineJudge ======== #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define debug(...) ((void)0) #define orange(...) ((void)0) #endif ``` ---- 在本機 define LOCAL ```cpp! g++ solve.cpp -D LOCAL ``` 則編譯時就會 define LOCAL 但每次都要打 -D LOCAL 很麻煩... ---- 還記得 alias ```bash alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow` ``` 改成 ```bash alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow -D LOCAL` ``` :happymention: ---- ## debug 變數 debug(x) ```cpp! string x = "abc"; debug(x); int y = 123; double z = 1.23; debug(y, z); ``` ---- ## debug 範圍 orange(begin, end) ```cpp= int arr[5]={2,1,4,3,5}; orange(arr, arr+5); vector<string> strVec = {"Alice", "Bob"}; orange(strVec.begin(), strVec.end()); ``` ---- ```cpp= ```cpp= #ifdef LOCAL // =========== Local =========== void dbg() { cerr << '\n'; } template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } #define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")")) #define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args)) #else // ======== OnlineJudge ======== #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define debug(...) ((void)0) #define orange(...) ((void)0) #endif ``` ---- ## assert 他用來判斷一個條件是否成立， 如果條件成立則不會發生任何事 如果條件不成立，則會造成程式RE(Runtime Error) 通常用於 debug 不確定會不會錯 或者想 submit 時 不確定有沒有問題用的 ```cpp= assert(x <= 5); ``` ----  ```cpp= [|10-11|1-7,12|13|] long long fpow(int x, int y){ long long ret = 1; for(;y;y>>=1, x*=x){ if(y&1) ret = ret * x; } return ret; } int main(){ cin >> n; auto [x, y] = solve(n); assert(fpow(x, y) * y + fpow(y, x) * x == n); cout << x << " " << y << endl; } ``` ---- 或者想猜測資，判斷是否大於某個值，就可以assert 再加上 TLE 一起用 ~~每次可以把測資分三半去猜測資 複雜度 $O(log_3N)$~~ ```cpp= cin >> n; if(n >= 10){ // RE assert(0); } else if(n > 5){ // TLE while(1){} } else{ // WA return 0; } ``` ---- [Benq's submission](https://codeforces.com/submissions/Benq) [Who is Benq?](https://www.youtube.com/watch?v=xiDEsX0_MGE)  - 溢位 - 陣列超出範圍 - 邊界測資 n=1 n=2 n=bound ---