[筆記] Design and Analysis of Approximation Algorithms - Introduction

標題其實是這本書：Design and Analysis of Approximation Algorithms，這本書簡單來說是在介紹 approximation algorithm (中文好像會翻成逼近演算法、近似演算法)。這類演算法著重的地方是那些現在沒有 "有效率" (也就是 polynomial time 的方法) 的方法解決的最佳化問題 (optimization problem，換言之答案是要找出極值，不論是最大值或最小值)，這類問題只要去找 NP-Complete、NP-hard 就有一大堆了。

當然學術上的方法是一回事，現實中當你遇到這類問題又一定要有一個解的時候，真正的問題就會變成你怎麼知道你找出來的解距離最佳解有多遠? 所以這本書的目的就是統整併分析目前有哪些方法可以有效率的解決找出一個近似解、同時告訴你這些近似解在理論上距離最佳解有多遠?

[C++] Mandatory Copy Elision in C++17

一言以蔽之：以前 compiler 幫你做的最佳化現在直接在標準裡規定一定要有。

[C++] inline Variable and thread_local in C++17

inline variable 最大的用意應該就是允許在 header 就把變數的宣告 + 定義一次搞定吧。在 C++17 前除了少數特例 (比方說 literal type)，基本上 header 只能放宣告，明確的定義是必須要放在單一的 translation unit 以遵守 ODR (one definition rule)。

[C++] Structure Binding in C++17

用一句最簡單的畫作結論的話就是語法糖

C++11 開始除了一些新觀念的引進 (比方說 move semantic) 之外，類似的語法糖也增加了不少，經典例子就是 lambda expression。而 structure binding 到底是啥呢? 舉個簡單例子：

std::pair<int, double> ms{1, 3.14};
auto [i, d] = ms;

一個很樸實無華但是稍微可以讓你的 code 更簡潔易懂的東西。

[生活] 工作日常 - 2019

上一篇的傳送門：工作日常 - 2018

這篇收錄 2019 年的工作日常，2019 年是個 hashtag 大爆發的一年 XD

[Python] Dangerous default value

最近跑 pylint 時偶然發現了一個 warning 叫 "Dangerous default value as argument"，細追之後才發現一個陷阱

[生活] 工作日常 - 2018

因為 FB 搜尋貼文不是很方便，這篇收錄了 2018 年原本發在 FB 的工作日常 (不過早期的貼文沒有 hashtag，有些非主角人物也不好確認是誰了)

[程式] codeforces 1321C: Remove Adjacent

[題意]

給一個由小寫字母組的字串 s (長度介於 1 ~ 100)，每次你可以從 s 中刪掉一個滿足特定條件的字母，問最多能刪掉幾個?

刪除字母的條件：令 s[idx] 為 s 的第 idx 的字母。若 s[idx - 1] 或 s[idx + 1] 的字母其字母順序 (令字母順序為 a -> b -> c -> ... -> x -> y -> z) 在 s[idx] 的字母順序的前一個，則我們可以刪掉 s[idx]

[C] XOR linked list

一言以蔽之，這是個用 single linked list 的架構去做到 double linked list 的效果的東西，主要目的就是為了節省記憶體使用量

[筆記] Automatic Log Parser

這其實是個很大的題目，作法百百種，但是核心概念就是要將原本需要人工設計、維護的 log parser 轉變為用程式自動地去找出隱藏在 log 中訊息架構。這樣說可能不太好理解，我們直接看圖：

來源：https://github.com/logpai/logparser

圖中最上面是 hadoop 印 log 訊息的程式片段，在執行過程中會在 log 檔產生中間的訊息，而最下面則是一般使用 log parser 通常會想得到的結果。通常 log parser 要產生出最下方的結果依賴於使用者知道 log 訊息的架構，比方說每個 log 訊息最一開始是時間資訊、然後是嚴重程度、從哪個元件印出來的、訊息內會有那些地方是固定或可變的...等等。然而這種方法最大的困擾點是目標程式改版、訊息架構有些許變化，log parser 也一定要跟著修改才能運作。所以近年來就有人開始研究是否有辦法讓程式自己找出那海量的 log 訊息中的架構，這樣就不用花大量的時間去維護 log parser 了。

"Tools and Benchmarks for Automated Log Parsing." 這篇發表在 2019 ICSE (International Conference on Software Engineering) 的論文簡單來說就是整理了至今發表的各種方法並且加以評比各自的精準度與效能。另外他們也把程式放上 github 了，有興趣的可以下載來使用看看，對於有這類需求的人我想是個滿適合拿來入門的。