[筆記] 線性時間內尋找中位數 (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 天的時間裡其實絕大部份時間都是挺無聊要想辦法找事情打發時間這樣。說是這樣說，成功嶺裡手邊能拿到的材料也只有紙跟筆，能用這兩項材料做出甚麼事情打發時間就考驗創意 & 記憶力了。這次進成功嶺就在這樣的環境中親眼見證了同袍被長官封為棋靈王的瞬間。

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