[隨筆] 研究的實驗結果這回事

最近看了許多跟系統架構相關的文章，讓我想到剛升碩一時不知天高地厚的跑去修了虛擬機器這門課，然後因為各種聽不懂大受打擊的事情 XD 當時這門課的期末專題是要想辦法找出 QEMU 中可以改善的地方，然後做實驗說明改善的結果跟幅度，現在想想當初能順利做完這個專題還拿到高分實在是運氣破表 XD

[筆記] 最佳化演算法 (Optimization Algorithm) 的使用與誤用

(這篇的數學式有用到 javascript 來顯示，請不要檔掉 JS，不然顯示上會很奇怪 XD)

最佳化演算法簡單來說就是個搜尋演算法，這類演算法的再做的事情是給定一個問題，定義合法的解集合 (或是空間，英文是 solution space)，再給一個函數用以判別一個解的好壞 (objective function)，這類最佳化演算法就會在解集合中找出符合要求的一個解。

有點難懂？舉個例子：假設我想要再一個 2D 的平面座標中找到一個點使得 $f(x, y) = (x - 5)^2 + (y + 3)^2$ 得值最小，求 (x, y) 為？在這個例子中，solution space 就是 2D 平面上所有可能的點座標，而 objective function 就是 $f(x, y) = (x - 5)^2 + (y + 3)^2$。而最佳化演算法就是針對 "任何" 這樣的問題，找出一個盡可能滿足 objective function 也合法的解給你。沒錯，就是任何這類需要在一個 solution space 中找解的問題都行。所以這類演算法很萬用，但也因此容易被誤用。

[EDA] Steiner Tree v.s. Spanning Tree

一般演算法講到 greedy method 時都會用 spanning tree (生成樹) 當範例，因為 spanning tree 有 O(n log n) 的 greedy method 可以找到最佳解。相對於 spanning tree，某些情況人們會更偏好 Steiner tree (中文好像是翻成史坦納樹)，兩者雖然都是要找一個方法把給定的點連成一顆樹，並且一般都會要求 cost 要最低，但是一個很大的差別在於 steiner tree 允許連線時增加多餘的點，但 spanning tree 不行。有多餘的點可連差異會很大嗎？我想可以參考 wikipedia 這篇的圖例就會知道這差異有多大。簡單的一個結論是 minimum steiner tree 的 cost 是小於、最多等於 minimum spanning tree。

[隨筆] 簡潔而精準 與 冗長但易懂 都幾?

在 FB 上看到朱家安 (哲學哲學雞蛋糕的作者，最近有上去臺灣吧介紹哲學的那位) 的這篇詢問文時，想到了剛開始寫論文的一些事情，當時也被老闆告誡過跟這篇文章想問的事情有關的原則。

我相信其實不只哲學論文，一般學界的論文都會為了要求精準而簡潔而使用了大量的符號去避免冗餘的文字還有錯誤的解讀，因為自然語言很常出現同樣的一個句子可以有 2 種以上的解讀方式。像那篇文章中的 A1、B1 就用了一些代號去代表一個特定的事件、情境等等的現像。相較於 A2、B2 來說，因為可以大量減少文字中所需要的代名詞，而且因為符號所代表的事情是固定的，因此可以減少讀者在解讀上的困擾。比方說，如果文章的某個段落提到 "該事件"、"此方法" ... 等等之類的用詞時，讀者通常必須要能緊緊的跟住文章的脈絡才能正確的理解這些名詞在指涉哪些內容；相對的，姪皆使用代號的話就沒有這個問題，比方說我上面的 A1、A2 只要有看到原文的都會知道我在指甚麼。

當然，依照情境優點也是會變成缺點的：當今天代號過多時，一般人會難以將大量的代號與其所代表的意義迅速的連結，因此下場就會變成讀者會需要常常翻閱每個代號的意義，反而增添閱讀上的困擾與意願。我想應該沒有人喜歡閱讀文章時還需要常常往回翻每個代號的用意吧？就我自己的想法，適量的使用代號有助於理解文章的內容，當然何謂適量就是另一個問題了。我的看法是當作者自己本身都必須往回翻翻看有多少代號然後哪些是甚麼含義時就是個警訊了。另一個可以著力的點是使用代號時也盡量都使用默認常用的符號，別自創新符號。

備註：

有看到推文有人提到數學式子，但我覺得數學式子跟代號又有一點微妙的不同，因為複雜的數學式子會有理解困難的問題，但代號應該沒有複雜的代號這回事 XD

[閒聊] 人際關係

最近因為發生了點事情，所以比較常跟人聊到人際關係這回事，一個可以簡單可以複雜的問題

[隨筆] 性格

最近覺得要想了解一個人，除了從平時的互動可以略知一二外，最好的方法其實是觀察他的負面情緒

 一個人在身處負面情緒的狀況下因為多少失去理性了 (當然，憂鬱症這種已經屬於精神疾病的不在這邊的討論範圍，我沒那麼厲害)，此時展現出來的就有很高的機率是他的原始面貌。比方說，容易有肢體衝突、容易有語言上的暴力、酸言酸語、孤僻、高傲、自尊心強烈 ... 等等，在人身處負面情緒時很容易展露無疑。當然，也有些人即便身處負面情緒下還是有著關懷、體貼、包容 ... 等等的正面情緒，所以觀察一個人身處負面情緒時會有何反應大概就可以簡單的窺探一個人的本性。

不過，我果然還是不習慣跟刺蝟類型的人相處太深入，因為當這類人身處負面情緒時，張開的刺保護了自己，卻也阻隔了所有試圖 - 不論是好意或惡意 - 靠近的人，而且往往越接近的人被傷的反而是最深的。或許是我自己的偏執，往往很希望可以在別人低潮時試圖陪伴，因為我覺得這或許可以給別人一種安心感，現在覺得這種自做多情的事情還是別幹了，往往自己被弄得滿身傷還不被諒解。

[EDA] Design Challenge in Rouoting Algorithm - 繞線演算法的設計困難處

在 IC 設計中，Routing (中譯：繞線) 的用意就是把需要連接的地方用金屬線連起來，概念很簡單。要判別一個 routing 結果的好與壞也很容易：計算總線長就好。因為總線長越長也就意謂著需要越多的金屬線以及空間，所以如果有許多種不同的 routing 結果，我們會選擇總線長最少的那個當成最後結果。

隨著製程的演進，現在 routing 要考慮的因素越來越多，因此在演算法的設計上也就越趨複雜，而且通常難以有個通盤考量的好結果。這一篇要來簡單的總結現在 routing 上最重要的設計考量 - 繞線資源的規劃與使用 (routing resource estimation & management, 以下簡寫 RREM)

[隨筆] 程式能力該如何檢定?

最近這幾年推廣寫程式的風潮越演越烈，比方說科技界的大老的推廣、人人都該寫程式、甚至也有教授開始推廣國中小的學生開始學習寫程式。究竟為什麼推廣寫程式，我想已經有很多文章在闡述這點了，今天想談的是從這點往下延伸的問題：

究竟如何判斷一個人的程式能力?

[閒聊] 我都可以，你們決定吧 -- 群體沉默的開場白

我相信大家應該有這種經驗：

那些時間 / 地點 / 方法 (... 請自行帶入其他可能的名詞) 我都可以，給你們決定

然後每個人都這麼說完一輪後，如果又是在聊天是用打字的對談，接下來肯定會有很長一段時間沒有任何人發言，看最後是誰耐不住尷尬、或是受不了一直沒結論，願意跳出來隨便提一個方案。

[C++] Recursion Using Lambda Expression

C++ 的 lambda expression 搭配 std::function 就可以做到 recursion 的功能

[EDA] Design Chanllenges of Standard Cells

Standard cell (中譯：標準元件) 是數位 IC 設計的基本單元，指的就是諸如 AND 閘、OR 閘 ... 等等的邏輯閘或是 Flip-flop、latch 等記憶單元。因為數位 IC 有絕大部分都是這些基本邏輯閘，因此設計良好的 standard cell 絕對會對最後的 IC 成品有舉足輕重的影響。這篇只是簡單聊聊現在 standard cell 及其相關設計會遇到的問題，不會深入去談技術細節 (人懶就說)

[隨筆] 失落

因為事情的不順遂，所以失落
因為有所期待卻一再落空，所以失落
因為不如預期卻又不知原因，於是不停的鑽牛角尖還爆發了各種小劇場
也許一切都只是過度的妄想的猜測，但無法排除的可能令人憂心
也許時間過去會恢復原樣，但看不到終點的不確定感令人焦躁

只能等了，等著期望中的未來來到，期待一切的一切終究是過度的猜想

[品茶] 大吉嶺 - 凱瑟頓 夜光白玉 春摘

大吉嶺，印度靠近喜馬拉雅山那一塊，海拔相當高，因此植物的生長也較為緩慢，也較多水氣，故大吉嶺的茶葉相較於其他種類的紅茶通常具有較多芳香物質，因此大吉嶺的一大特色就在於他那相當迷人多變且細膩的香氣。這次嘗試的目標是凱瑟頓莊園的春摘，等級是夜光白玉。

[演算法] A Progressive Network-Flow-Based Heuristic for Finding Minimum Cost Clique Partition

 minimum clique partition (MCP) 探討的是如何將一個無向圖 (undirected graph) 分成最少數量的 clique。若是無向圖上的邊具有權重的話，並且最少數量的 clique partition 有好幾組的話，則此問題要找的是所有 clique 上的所有邊的權重總和要是最小的那一組。因為這是個 NP-hard 的問題，因此若非一定要找出最佳解 (optimum solution)，一般將採用 heuristic 的方式找出一組次佳解 (optimal solution)。這邊要介紹的是基於 progressive network-flow 的方法找出一組解

[C++] The Previous Element of vector::begin() Is Not vector::end()

在使用 STL 的 container 時，相信類似以下這段 code 的片段不是什麼很希奇的事情

std::vector<int> vec;
// blah blah blah
if (--iter != vec.end()) { /* blah blah blah */ }

很顯而易見的邊緣判斷，當 iterator 已經是指向最一開頭的元素時，想要再往前存取前一個元素時就該停止了

不過這段 code 在一個特定的情況下會失效，就是當 iter == vec.begin() 時！沒記錯的話這問題發生在把 container 從 list 換成 vector

原因其實也不難懂，vector 底層的實作是 array，換言之 vector iterator 一般來說在其底層就會是個 array pointer。所以只要用 array pointer 的觀點來想就會知道為什麼那段 code 會有問題囉。

而 vector 因為底層是 array，但又需要能夠動態增減其大小，因此還會有 iterator validity 的問題 (確切一點的說法是所有的 STL container，但是 vector 最容易遇到)，類似這類的問題第一次遇到大概得要花上個數小時找問題吧...

[EDA] SubHunter: A High-Performance and Scalable Sub-Circuit Recognition Method with Prüfer-Encoding

識別子電路 (sub-circuit recognition, 以下簡稱 SR) 問題是給定一個大電路 (MC) 與一個小電路 (SC) ，希望能在 MC 中找出所有跟 SC 相同的部分。

此問題的應用在於可將原始較大的電路中特定功能的電路予以取代，如此可將原始電路的大小縮小，有利於降低後續電路的分析與驗證的複雜度與所需時間。

因此在 SR 問題中效能是非常重要的考量，同時必須確保演算法的擴展性足以應付電路的複雜度與大小皆有爆炸性成長的趨勢。

[C++] 強制 STL container 釋放資源

一般來說 STL 的 container 都會提供一個 member function clear() 清除 container 內部的資料，不過我想大家也很常遇到一種情形是這樣的：

1. 先配制足夠的空間給 container
2. 開始存取運用 container 內的資料
3. 呼叫 clear 清空 container 的資料以便下次再度利用這個 container

一般我們可能會假設一呼叫 clear() 後 container 就會釋放所配置的資源，但在這種情境下就很容易出現頻繁記憶體配置與釋放。但這實際上是可以避免得，我們其實只要把儲存在 container 中的資料解構使其所利用的資源變成 raw memory，下次要再度使用時只要重新建構即可，如此一來我們即可省去記憶體是放與配置的冗長時間。基於這個理由，呼叫 STL container 的 clear() 其實不一定會釋放所持有的資源，可能僅僅將所儲存的資料解構而已，因此如果今天想要確保 container 必定會釋放所持有的資源的話可以這樣做 (以下用 vector 做範例說明)：

std::vector<int> vec;
// some operations
vec.swap(std::vector<int>());

當然更好的做法就是讓變數的 scope & 生命週期盡可能的小使其直接呼叫 destructor 來釋放資源囉。

[C++] The Use of priority_queue And decltype

在 C++ 中要使用 heap structure，最直覺的方法就是使用 STL 的 priority_queue。priority_queue 預設會假定你在 template parameter 所指定的 data type 會支援 operator<，並且利用 operator< 去對資料做排序。其預設的排序行為會行程 max heap，若需要使用的是 min heap，則必須在 template parameter 指定 compare function 或 compare object 的 type，並在 constructor 指定 compare functor 的行為。

在 C++11 推出前，為了提供自定義行為的 functor，會讓 code 變得稍稍難看了點 (請參閱 cplusplus 上的範例)，然而，運用 C++11 的 lambda expression 或是 decltype 即可讓程式碼變得更為簡潔易懂。

[遊記] 情人節來走情人谷步道 (南坪古道)

其實原本是看到健行筆記的這篇文章要去走南坪古道，後來對照地圖後發現網路上看到的資料其實是叫做 "情人谷步道"，或許以前是叫南坪古道，但現在的南坪古道不是指那條步道了 (google map 上有標示南坪古道，但沒有情人谷步道的地圖，要地圖的話請參考這份地圖，上面虛線部分就是情人谷步道，也就是健行筆記所講的南坪古道)

由於 google map 上標記的那條南坪古道不知道有啥東西，所以我們後來還是去走健行筆記上講的南坪古道，接下來的南坪古道也都是指我們實際走的路線。

[EDA] Mordern IC Design in Advanced Technology Nodes

我猜可能標題不用看完，跟 IC design 無關的人就直接關掉了 XD

雖然等等要講的東西沒有很深入，但確實也不是對這領域沒興趣的人會想知道的東西就是了~

這篇其實只是簡單整理一下從碩班做到現在，做過的東西 & 看過的論文的一些整理與心得，不過因為我很懶，所以不用期待會看到完整詳實的數據或圖表 XD

[隨筆] 程式碼的可讀性與時間的關係

其實這篇只是想要講一下最近 coding 時發現的自己的一些習慣 XD
想講的話自己的程式碼的可讀性隨著時間的過去會呈現什麼樣的關係

[C++] static const Member in a struct/class

C/C++ 的 struct/class (為方便解說，接下來統一用 struct　) 可以將其成員變數的型態附加上 static const 修飾詞，如此一來該成員變數即為所有該 structure 產生出來的 object 共享的成員變數，並且也無須透過特定的 object 來存取，可以直接用 structure name 去存取該成員變數，例如：

struct A
{
    static const int val = 1;
};
int x = A::val + 1; // direct access

一般來說雖然不允許 structure 的成員變數直接在宣告時給予初始化，但是有 static const 修飾的成員變數是唯一的例外，允許直接在宣告時就給予初始值。不過這次這種使用方法卻讓我遇上不明究理的 link error，簡述如下：

[閒聊] 煮奶茶

之前有次跟茶友泡茶聊天時，聊到了煮奶茶這回事。煮奶茶之所以特別，在於它是純粹只用奶去煮茶葉，過程中沒有任何一滴水，所以跟一般奶茶的滋味也特別不同。