[C++] What and How: error: request for member '...' in '...', which is of non-class type '...'

簡單來說，就是物件宣告跟函示宣告混在一起了看起來很像，所以有時候 compiler 會搞錯

[筆記] MySQL Config File Encryption and Decryption

上一篇提到 MySQL 在 5.6 版後提供 mysql_config_editor 這支 utility 讓使用者可以產生/修改加密後的 config file (或者叫做 option file)，但是很奇怪的是官方提供的 API 不管是 C 或 Python 都不吃加密後的 config file。後來經過多方查詢研究後發現 python 有一個 package 叫 myloginpath 可以把加密後的 config file 解成明文，基於 python 沒秘密，所以這邊就來整理一下這弱到爆的加密方式

[MYSQL] C/Python Connector API for MySQL

MySQL client 登入時可以藉由提供一個 option file (比方說 .mylogin.cnf) 並且在裡面寫好 user / password / host 等資訊後，登入時直接使用 option file 連上 MySQL server。不過 option file 因為必須是明文，自然會有風險。只是 MySQL 自 5.6 版以後提供了 mysql_config_editor 這支 utility 讓使用者可以把 option file 加密 (目前看到的資料好像是會用 AES 128bit 加密) 來避免這個問題。

想當然爾，MySQL 也必須提供 API 讓使用者可以藉由這些 API 直接使用這些加密後的 option file 連上 MySQL server。這邊介紹的是關於官方原生提供的 C/Python API 上的狀況。

[C++] A Simple Wrapper on A Non-Thread Safe Container for Thread Safety

大部分的 container 像是 STL 的所有 container 通常都不是 thread safe 的，因為如果要做到 thread safe 的設計多半都要犧牲一些效能，但是大多數情況其實我們不會需要這種設計，因此不考慮 thread safe 對於這類考量泛用類型的架構是合理的。當然如果一開始就有考慮做成 multi-thread 的架構，也有許多 thread-safe container 可以使用，像是 Boost 或是 Intel Thread Building Block (TBB)。

但是假設今天用了 STL 的 container 後一段時間才想要改用 multi-thread 架構的話要怎麼辦？方法大致上就 2 種：

1. 換掉 container：不過多半連既有程式的使用方式也要跟著做修改
2. 想辦法把原本的 container 改成 thread-safe

第 1 點當然會是比較保險的，但是換 library 是大事，特別是如果想用的 library 沒有對應的 API 可以對回去原本 library 的用法那就很麻煩了。所以這邊提供第二種方式：增加一個 wrapper，在盡量不改變 usage 的情況下提供 thread safety。

[C++] A thread-Safe Bounded Queue Based on STL Container and C++11 Threading Library

要寫一個平行化的程式通常多半免不了需要一個 thread-safe 的 container，很不巧的是 STL 並沒有提供一個 thread-safe 的 container。雖然通常純讀不修改多半是可以 thread-safe，但如果要允許同時可讀又可寫就需要自己想辦法了。

這篇就是自己想辦法用 STL 的 container 生了一個 thread-safe 的 bounded queue。用 STL container 當基底純粹是因為我懶得自己做記憶體管理 XD

[C++] Lazy Evaluation for Function Argument

C++ 的 function call 在傳參數進去時基於一些因素會把所有參數都拿到最後的結果後才進入 function 本體去執行。比方說，傳進去的參數是一串四則運算時，會先算出最後的結果；如果也是個 function call，那也會先把 function call 執行完畢拿到結果。

在某些情況下如果我們知道其實進入 function 後根本不會用到這些參數的內容時，做這些計算其實就會變成浪費時間了。因此，最容易想到的解法是，有沒有辦法把這些運算的過程延遲到我真的需要時才讓他執行？

[C++] Use std::condition_variable for Parallellism

C++11 開始 STL 就提供了 thread library以便寫平行化的程式，condition variable 簡單來說就是用來控制流程用的，他允許我們在過程中透過 condition variable 來決定是否要 block 某個 thread 等待另一個 thread 完成工作，也可以透過 notify 去讓一個 (或多個) 正在等待 thread 繼續往下執行他們的工作。

[C++] Compile-Time if in C++17 Can Have Code Not Able to Be Compiled with Regular Runtime if

Compile-time if 在 C++17 中也算是一個滿有趣的特色，其特點就在於能夠在 compile time 就幫你確認清楚 if statement 中會執行到哪一個判斷式對應到的區塊，從而把其他一定不會用到的區塊 "拔掉"。這點在現在電腦上算是個滿有用的特色，畢竟現在 CPU 的 branch prediction 一定錯誤通常都要承擔不小的後果 (註) 

原本我以為 compile-time if 只是針對一些能在 compile-time 就能推知結果的運算做優化 (特別是在 template 上)，結果今天看到一個例子才發現這玩意兒比想像中更猛，甚至能夠寫出一些原本 regular runtime if 做不到的功能。

[筆記] 狂歡西班牙 - 上課筆記

事情是這樣的，有一天在 Coucou穀穀你好 法式小食舖 上看到老闆娘為眾人著想(想不開)跟 Mia 老師 合作要開課，教的內容有包含前菜、主菜、甜點各一道。想說機會難得就找了一堂課去上了，所以下面就是上課的內容跟一些簡單筆記了。

[筆記] google perftools (gperftools) - 安裝與超簡易使用說明

google perftools 簡單來說就是一套用來做 memory 跟 CPU (也就是 runtime) 的 profiling tool，基本用途有三個：heap profile，單純每個看 component 的 memory 使用量；heap checker，用來檢查有沒有 memory leak；以及 CPU profile，用 sampling 的方式去探測 CPU 的使用量。這東西最大的優點就是幾乎沒有 overhead。所以比起直接用 valgrind 去跑，可以考慮先用 gperftools 先做簡單的 profiling 粗略掃描，有必要更深入檢測的話再丟給 valgrind/callgrind 去細部檢查。

[C++] prvalue sucks!

最近在看 YouTube 上的這部影片解釋 object, lifetime 還有 reference 相關的內容，裡面有個有個關於 prvalue 的範例讓我有點驚訝，驚訝地點在於 C++ standard 對於標準有定義的型態 (像是 primitive type) 跟未定義的型態 (像是 struct 或是 class) 有完全不一樣的行為，但為什麼會這樣定義卻想不通 = =

[C++] 利用 generic progamming 簡化存取 union 變數的介面

公司的程式 (特別是那種底層 API) 其實很常使用 union 來減少非必要的記憶體使用量，只是如果使用 union 的話就必須要能夠知道該用哪種型別來存取 union 中的變數，因此很常出現這種程式碼：

enum Type {Int, Double};

struct Data {
    Type type;
    union {
        int i;
        double d;
    };
};

int main()
{
    Data data;

    data.type = Int;
    data.i = 3;

    data.type = Double;
    data.d = 3.14;

    return ;
}

簡單來說就是設定好要存取的是哪種型態 (然後用個 enum 來表示)，接著 API 會根據設定的型態來對 union 中的變數做存取。以上面的範例來說，會根據 Data 中的 type 是被設定成 Int 還是 Double 來決定 是要存取 data.i 還是 data.d。

因為個人覺得這樣滿容易手殘的，特別是公司的 API 其實型別種類有點多 |||Orz，所以想要簡化 API 的使用方式，希望可以直接根據所設定的型別存取對應的變數就好，畢竟這種關聯性其實是固定的，利用 generic programming 應該是不難做到的。

[C++] static_cast & reinterpret_cast & C-style type cast

C 的型態轉換大家應該都很熟也很常用，不過在 C++ 中因為 C++ 的功能與語言特性複雜許多，C 語法的型態轉換一來不易辨識，二來其內部運作方式較為隱晦不清，因此 C++ 引入了四種型態轉換運算子，分別是

static_cast, dynamic_cast, const_cast 與 reinterpret_cast

大多數情況我們所使用的 C 型別轉換通常是對應到 static_cast；dynamic_cast 則是應用到繼承體系的型別上；const_cast 其作用只在於拔掉變數的常數性 (const) 與揮發性 (volatile)，其餘維持不變；其中最玄的該數 reinterpret_cast 了，有部分 C 的型態轉換的使用情形對應過來 C++ 這邊其實是要用 reinterpret_cast

[C++] fold expression

fold expression 是 C++17 中專為 variadic template (或者說 parameter pack) 設計的東西。

[C++] move semantic 的誤解

今天部門的讀書會上討論到 Effective Modern C++ 中介紹關於 C++11 開始引入的各項新特色與其相關問題，其中有個例子介紹到了 std::move 跟 std::forward 的使用時機。主講者也很有心的把其中某個例子自己嘗試寫了出來並加以變化來驗證，結果沒想到剛好可以變成一個說明何時不該使用 move semantic 的絕佳範例 XD 而且這也剛好說明了 C++11 引入了各項特色其實還...滿難懂的，也難怪會後會有人說其實乾脆不要用就沒這些煩惱。

[筆記] 線性時間內尋找中位數 (Median of Median)

要找一串未排序數字的中位數 (或者更廣泛一點，第 k 小的數字)，最簡單的方法自然就是先排序後再找出來，當然，這種方法就會受限於排序演算法的複雜度，一般情況而言，最糟情況下會是 O(n log n)。不過因為我們在意的其實只有第 k 小的數字，所以就有人想辦法弄出了線性時間的演算法，這方法好像沒有明確的名稱，大抵上是利用 divide & conquer 的概念來做的，再加上原先是設計用來找中位數的，所以 google 的話可以用 Median of Median 當關鍵字來找。另外其實也有許多不同的方法，各有優缺點，可以依照實際應用情況來決定怎麼設計。

[筆記] K-D Tree v.s. Quad Tree

在計算幾何中其實很常會出現需要找出在座標平面上的一堆點或線段中位於特定區塊中的點或線段。舉例來說，想找出二維座標平面上找出落在 (0, 0) ~ (10, 10) 這個矩形區域點的所有點，並且對這些點做處理。常用的資料結構有幾個：

• R-Tree (可以衍伸出 R+-Tree, R*-Tree)
• K-D Tree
• Quad Tree
• Bounding volume hierarchy (BVH)

根據要應用的情境各有優缺點，使用前要詳細閱讀說明書 (?

[筆記] MongoDB: Two Phase Commit - Multi-Document Transactions

這篇的內容主要是來自 MongoDB 官方網站上的 Manual 中的這篇。簡單總結：two phase commit 是為了模擬 Transaction 的特性。

[筆記] SGCheck: An Experimental Stack and Global Array Overrun Detector Table of Contents

SGCheck 是 valgrind 底下的 tool 之一，簡單來說這東西就是用來彌補  memcheck 的不足之處。memcheck 專攻的問題是 heap memory 中的 illegal access (invalid read & write) 以及 memory leak。相對的，SGCheck 則是對 stack memory 做檢測，特別是當使用 array 或 pointer 時確實無法完全避免不會有 illegal access。因此這兩者算是相輔相成的，只是比較常聽 & 用到的是 memcheck (也是memory bug 最常出現的地方)。

[筆記] RDBMS v.s. NoSQL

RDBMS v.s. NoSQL

現在主流的資料庫像是 MySQL 之類的是關聯式資料庫 (RDBMS)，不過隨著網路的發展，關聯式資料庫的特性在某些應用上其實沒有那麼適合。比方說，你對於資料間的關聯性沒那麼在意，你在意的是特定人、事或物的 "狀態" 變動，特別是這種狀態的變動非常大量且頻繁時，關聯式資料庫在處理這種需求就會變得力不從心，也因此後來有發展出了 NoSQL 這東西是專門針對這種應用設計的。而這次被主管要求要看的 MongoDB 正是一種 NoSQL DB。

[筆記] 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 節就有提到其實曾經有人提出了另一種方法，僅僅使用位元運算以及加減法來找最大公因數。

[程式] 最近共同祖先 (Lowest Common Ancestor - LCA)

LCA 算是 tree 滿容易用上的一項特性，原因在於找出任意兩點 u, v 的 LCA 後 (假設是 w)，通常問題可以拆解為：

• (u -> w) + (v -> w): 這樣的兩條路徑各自求解後合併

LCA 的找法可以參考演算法筆記中的 Jump Pointer Algorithm，他的基本概念就是對每個 node 的前 1、2、4、8 ... (2^n) 倍的祖先，如此一來，假設要知道一個 node 的前 5 代祖先是誰，只要知道他的前一代祖先的前四代祖先是誰就可以了。(簡單來說，看成用二進位表示法就知道這種儲存方式可以得知任意一個點的任意一代的祖先囉)

透過這種方法，對任意 2 點 u, v，我們可以知道最後的共同的祖先必然是 root，從上往下追蹤直到出現分歧為止，這就是最近的共同祖先拉。

[程式] Segment Tree (線段樹)

Segment Tree 是個用空間來交換時間的資料結構，特別適合用在搜尋次數極為龐大的時候。其所需的額外空間約為既有資料的兩倍 (空間複雜度是 O(N)!)，時間複雜度則為 O(log(N))。

[筆記] Codeforces 920E: Connected Components?

[題意] 給一個有 n 個點的 undirected simple graph，並且告訴你這個 graph 中有 m 條邊被拿掉了，問有幾個 connected components？並且把 connected component 的大小由小到大印出來。

[程式] 排容原理實作 (inclusion-exclusion principle implementation)

由於先前這一篇會用到排容原理，因此就花了點時間研究排容原理要怎麼實作比較好。不過這玩意兒因為只是個原則，實作方法會根據要處理的問題有些許差別，這邊的實作針對的是以下的問題：

給定兩個正整數 $n$ 跟 $x$，要找出有多少正整數 $y$ 使得 $y < n \ \& \ gcd(y, x) = 1$，其中 $gcd$ 代表最大公因數

[筆記] Codeforces 920G: List Of Integers

[題意] 給定任意正整數 p, 則 L 是一串與 p 互質的序列 L(p) = {y | gcd(y, p) = 1}，且 L 是由小到大排序的 (gcd 就是最大公因數)。再給任一正整數 x，求 L 中比 x 大的第 k 個數值。

[隨筆] 第一場博士論文口試 (校內口試)

歷經各種狀況後，原定計畫是去年 9 月就能口試，結果各種投稿不順利就一路的延到現在終於可以口試了，算一算差了大約快半年 Orz 在這期間還發現系上對於博士口試還非常囉嗦，各種資格審查 & 行政文件要跑...雖然正式的口試還沒開始，不過就先記錄一下今天的前哨戰：校內口試吧

[筆記] 頂級勃根地紅酒的敲門磚

如果要問我這次的品飲的心得，我認為可以用下面的問句做個總結：

當你拿到了前往山頂的敲門磚，你也從眾多文章中得知了山頂有著曼妙絕倫的風景，只是通往山頂的路途漫漫，考驗極多，代價高昂，要看到預期中的風景還得要運氣好，那麼...你是否還願意攻頂?