[筆記] performance profiler: callgrind

Linux 上常聽到的 run time profiler 應該就是 gprof 了，不過進公司後才知道原來 valgrind 自己也有一套 profiler 叫 callgrind，精準度的話目前還不清楚跟 gprof 比起來誰比較高，但是大致用起來我覺得比 gprof 好上手，原因的話在於它有 GUI 可以直接看 call graph，方便很多。

[程式] codeforces 946B: Weird Subtraction Process

[題意] 給 2 個數字 n, m (1 <= n, m <= 10^18)，問經過下列操作後 n 跟 m 的值為何？

1. 若 n >= 2*m，則 n = n - 2*m，並回到步驟 1。
2. 若 m >= 2*n，則 m = m - 2*n，並回到步驟 1。
3. 若 n 或 m 其中一個為 0，或是上述二個條件均失敗時，結束。

[程式] codeforces 166C: Median

[題意] 給兩個正整數 n (n <= 500) 跟 x (x <= 100,000)，並且再給你一串含有 n 個數字的陣列 A，問如果要讓 A 經過排序後的中位數是 x 的話最少要往 A 裡面加入幾個數字？

[程式] Heavy Light Decomposition (重輕分解；樹鍊剖分)

Heavy Light Decomposition 台灣這邊的翻譯是直譯，所以是叫 "重輕分解"；而中國那邊是採意譯，所以叫 "樹鍊剖分"。這與其說是一種資料結構，倒不如說是一種概念，其基本概念是把一棵樹 (tree) 拆成數條一維陣列，如此一來在這棵樹上的所有查詢 (query)抑或是更新 (update) 都可以在對數時間內完成。詳細的概念可以參考這篇，演算法筆記上的這篇上有列出時間複雜度。

[隨筆] 這是一篇關於棋靈王誕生的故事

研替進成功嶺 12 天的時間裡，其實大多數時間都是在聽演講。演講這回事兒呢，主題跟講者的技巧只要一個稍差就會挺無聊的。想當然爾，這 12 天的時間裡其實絕大部份時間都是挺無聊要想辦法找事情打發時間這樣。說是這樣說，成功嶺裡手邊能拿到的材料也只有紙跟筆，能用這兩項材料做出甚麼事情打發時間就考驗創意 & 記憶力了。這次進成功嶺就在這樣的環境中親眼見證了同袍被長官封為棋靈王的瞬間。

是的，這是一篇關於棋靈王誕生的故事。

[程式] 不用除法的最大公因數 (GCD)

有不少數論 (Number Theory) 的計算中都會用到找兩個正整數的最大公因數 (greatest common divisor, GCD)，而最基本常用找最大公因數的方法中就是利用輾轉相除法 (Euclidean algorithm)，如下

$gcd(x, y) = gcd(y, x - q \times y)$

其中 q 為任意整數，下面的這段程式實作出輾轉相除法的概念：

int gcd(int x, int y)
{
 while ((x %= y) && (y %= x)) ;
 return (x + y);
}

然而，在現在處理器中求餘數的運算時間相較於基本的加減法以及位元運算 (bitwise operation) 是慢很多的，因此 Knuth 的 TAOCP (The Art of Computer Programming) 中的第 4.5.2 節就有提到其實曾經有人提出了另一種方法，僅僅使用位元運算以及加減法來找最大公因數。