這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

• 主要會貼一些github，但是會盡量寫上一些有用的評語（或是我容易想到的關鍵詞）幫助以後查詢

網路文章心得:

• 會寫些心得，強迫自己閱讀．

“程式週記”並且定期週期性更新．

大部分內容在我的twitter都會有，這邊只是將一些簡單的心得與感想註解一下．

本週摘要

本週主要在玩 Bot Framework 跟 wit.ai ．主要是想把它改寫成 Golang 版本的． 寫到一半發現由於 wit.ai 已經是兩三年前就發行了．（也沒啥在更新，這次F8 只是講說 Messenger 以後會支援) ．就改來寫 KMP．

既然要寫 KMP 當每週專案，當然要搞清楚他的原理跟他要解決的問題．當然也去想了一下應用． (好像也只有 strstr 跟 strchr ）．

我加入了碼天狗策展團隊，文章會在下一期（下週一出刊的版本）上．有興趣的可以看看．

Go

Golang 1.6.1 & 1.5.4 Security update

修復兩個主要的安全漏洞的更新版本: 1.5.4 與 1.6.1 將會在 04/13 02:00 UTC 更新，有需要的朋友記得更新． 安全漏洞如下: 點這裡

此外: json decoder 導致https的速度提升修改，將不會在這次的更新中．

Binary Sizes in Go

文章探討到如何縮小你的 Golang App Binary Size，裡面除了用到 -ldflags '-w' 之外，還有用到 unix strip ．

結果 Dave Chenney 不建議 strip．其他可以參考 reddit

An Enterprise-class Container Registry Server based on Docker Distribution

除了官方的 Docker Registry Server 之外，有人另外寫了一個具有以下的衍生功能:

• Role Based Access Control: Users and docker repositories are organized via “projects”, a user can have different permission for images under a namespace.
• Graphical user portal: User can easily browse, search docker repositories, manage projects/namespaces. AD/LDAP support: Harbor integrates with existing AD/LDAP of the enterprise for user authentication and management.
• Auditing: All the operations to the repositories are tracked and can be used for auditing purpose. Internationalization: Localized for English and Chinese languages. More languages can be added.
• RESTful API: RESTful APIs are provided for most administrative operations of Harbor. The integration with other management softwares becomes easy.

Parse RSS and Atom feeds in Go

算是支援度相當高的 RSS/ATOM feed parser

能讓你 Go 程式碼變得更好的工具集

除了常聽到的 Go Lint 之外，還有不少工具比如 Gocyclo , Depscheck 可以看看一些簡單介紹跟怎麼使用．

BGP implemented in the Go Programming Language

website: http://osrg.github.io/gobgp/

透過 Go 來實現的 BGP (Border Gateway Protocol) ，一種更複雜的 SDN ．

參考:

• Border Gateway Protocol as a hybrid SDN protocol

AthenaPDF

透過Electron, Docker 與 #‎Golang 讓網頁轉換成漂亮的PDF

Python

Android/JAVA/NODE.JS

[日文] FB Messenger 與 Line Bot API 比較

FB在前天的 F8 公開了 Messenger Platform ，剛好前幾天 Line 也公佈了他的 Line Bot API ． 這邊有日本工程師做了相當好的比較． 雖然我看不懂日文，但是有漢字跟英文的部分就加減看．挺好的．

A Multi-Paxos implementation in pure JavaScript.

找時間來研究一下，不過有可能花在 nodejs 會更多． ＠＿＠

Docker

iOS/Swift

網站文章

RESTful (Photo credit: Cait Stewart @flickr CC BY-SA 2.0)

RESTful 設計的要點

Yahoo 前亞洲區制定網站 API 協定的人分享RESTful 設計的要點．此外整理兩篇我覺得很值得不斷複習的好文章：

1. 關於 RESTful API 設計部分，這篇 Slide 很棒．
2. 關於 Web Error Code 部分，蠻建議搭配這一篇有許多流程圖來解釋 Error Code 該如何給，一看就不容易忘記．

算是打通一些基礎概念．

打造AWS的10年裡學到的10個經驗

簡單的心得就是： 要設計一個網路服務，你得當他隨時有可能都會壞掉（這邊指的是事故 accident 不是程式碼的錯誤) ．以下舉兩個例子:

1. Github 今年就因為有人不小心踢到插頭，復原後發現 server 重啟失敗．

2. Heroku 的 Dyno 如果免費的狀態下，一天會強制睡六個小時．

這兩個都是讓你去思考建構網路服務的重點． 順便來看看 “Site Reliability Engineering” 這本書會不會提到這個重點．

如海洋般的課程CS50

最近很紅的文章「程式自學十年心得：想吃這行飯，學好演算法與資料結構才能讓你站穩腳步」 裡面有提到這個 CS50 的介紹．看完相當吸引人． 推薦這篇文章給大家看看，不論是新手或是資深工程師可能都應該找時間修修看．

RECAP: F8 2016 Day 1

Facebook 技術日F8第一天總結 : Surround 360 相機 （開源，要價三萬美金) , live video and VR, 還有聊天機器人

網站收集

有聲書/影片心得

本週專案

這邊會寫一些我的Project 52的成果.

本週專案: KMP 與相關應用

其實 KMP 程式不難寫，倒是花比較多的時間去了解為何要使用 KMP 來做字串搜尋．還有為什麼原先的暴力解法與 MP 解法有可以改進的空間． 這個在前面已經有相關的文章了．

TL;DR

KMP(Knuth–Morris–Pratt algorithm) 是字串搜尋的最佳化演算法，是由 MP Algorithm 優化而成，並且 KMP Algorithm 主要也只能解決某些問題 (要搜尋字串連鎖過多造成過多移動) ．

暴力法 -> MP (提供比對與快速移動的方式) -> KMP (提供連鎖的減少移動方式)

相關程式

如果需要可以執行的相關 MP KMP 程式，可以去拿這個 Go 的版本．

https://github.com/kkdai/kmp

前言

紀錄一下關於 KMP 的學習紀錄，會講到 KMP(Knuth–Morris–Pratt algorithm) 主要就是因為一篇 DevOps 的求職文章．

所以決定去把它搞懂一下，順便寫一下相關程式．

注意 以下的部分由於我懶得畫圖，就沒有圖表介紹．如果要看圖表或是影片． 這一對教學影片很清楚． youtube: Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)

原理

KMP(Knuth–Morris–Pratt algorithm) 本身是用來做字串搜尋的演算法．也就是有點類似 C 語言本身會提供的 strstr 也就是在一個字串裡面搜尋一個字串．

當然 KMP 跟 strstr 有些許的不同由於回傳的資料不同． KMP 回傳所有符合的索引位置，而 strstr只回傳第一個．

字串搜尋:

方便以下講解，字串 target 為我們的目標字串， want 就是我們想要找出的字串． 其中:

• n = len(target)
• m = len(want)

暴力搜尋

解決問題:

講到在一個字串裡面要搜尋一個比較小的字串．比較直覺方式就是暴力法，也就是一個個比對．

方法論:

• 從字串 target 的第 i 個位置開始找 ( i 從 0, 1, … n )
• 如果 target[i] == want[0] 則繼續往下比對，一直比對到整串字串比對完畢．
• 如果不成功，將指標移到 target[i+1]

// 1
// Target [ 1 2 3 4 7 4 5 6 7]
// Want   [ 5 6 7

// 2
// Target [ 1 2 3 4 7 4 5 6 7]
// Want     [ 5 6 7 ]

// 3
// Target [ 1 2 3 4 7 4 5 6 7]
// Want       [ 5 6 7 ]

時間複雜度:

• 最差狀況: O(m * n)

MP 演算法 (Morris–Pratt Algorithm)

解決問題:

使用暴力解法最大的問題是最差狀況的時間複雜度代價太高，需要想一些辦法減少比對的次數． 所以有人想到是不是搜尋過的地方可以直接跳到後面？

// 1
// Target [ 1 2 3 4 7 4 5 6 7]
// Want   [ 5 6 7

// 2
// Target [ 1 2 3 4 7 4 5 6 7]
// Want         [ 5 6 7 ]

這樣問題來了，如果你要搜尋的字串其實有某種程度是具有重複性的．比如說 [ 1 2 3 1 2 4] 可以看出來 1 2 是重複有兩組在裡面． 那麼在搜尋的時候就無法一次跳掉所有的 target ． 所以 MP 演算法提供以下的方式．

方法論:

• 先分析要找尋的字串 want ，所有重複出現的字串列出一個列表．成為 failure index
  • want: [A B C A B B D] -> failure function: [0 0 0 1 2 2 0]
• 開始搜尋，如果遇到不符合的字串． 尋找 want 前一個字元去尋找他的相對應的 failure index． 要往後移動的數字為:
  • 已經比對的個數 - 前一個重複的位置
  • 假設比對到:

target: [ABCABCDDDD]
want:   [ABCABBD]
              ^ 比對到第6個
//時候要移動的會是 5-2=3

target: [ABCABCDDDD]
want:   [   ABCABBD]

留下的問題是，對於往後移動的計算方式．往往會因為後面一個跟移動後的第一個不搭配．要頻繁地移動．

時間複雜度:

• 最差狀況 O(m+n)

KMP 演算法 (Knuth–Morris-Pratt Algorithm)

原先MP演算法的問題

為了要解決移動後可能會遭遇的頻繁移動的問題，換句話說想要試著一次就把想要移動的部分到位． Knuth 在 failure function 上面增加了不少的判斷方式．

也就是試著在做 failed function 的時候，希望把之後可能會遇到的 failure function 移動兩次的狀態減少．

先來看看透過計算過後的 failure function 索引表．

           0  1 2 3  4 5 6
string    [A  B C D  A B D]
mpNext  = [-1 0 0 0  0 1 2]
kmpNext = [-1 0 0 0 -1 0 2]

透過這個範例可以看到，當有不相同的字串發生在 5 的時候． 由於前面是A，你也會發現 4 5 的 AB 跟 0 1 的 AB一樣是連鎖的．

以下透過上面的例子來推導一次(先透過 MP 來推倒，查看原先容易出現的問題):

           0  1 2 4 5 6
目標字串   [A  B C A B D]
mpNext  = [-1 0 0 0 1 2]


//1
搜尋字串   [A BCACCDDDAACABCDABD]
目標字串   [A BCABD]
           ^ 
//2
搜尋字串   [A B CDACCDDDAACABCDABD]
目標字串   [A B CDABD]
             ^  

//3
搜尋字串   [AB C DACCDDDAACABCDABD]
目標字串   [AB C DABD]
              ^  

//4
搜尋字串   [ABC D ACCDDDAACABCDABD]
目標字串   [ABC D ABD]
               ^  

//5
搜尋字串   [ABCD A CCDDDAACABCDABD]
目標字串   [ABCD A BD]
                ^   

//6
搜尋字串   [ABCDA C CDDDAACABCDABD]
目標字串   [ABCDA B D]
                 ^   

// 這時候發生不符合的狀態，根據 MP 的演算法
// 我們會移動到前面一個 A 的位址並且從 B 繼續開始比對

//7
搜尋字串   [ABCDA C CDDDAACABCDABD]
目標字串       [A B CDABD]
                 ^   

//由於 [0,1] AB 的連鎖跟 [4,5] AB 一樣，
//所以既然錯誤發生在[5] B，移動到前面的時候．
//接下來一定也會遇到 B ，就像現在．
//只好移動到最前面再比對一次

//8
搜尋字串   [ABCDA C CDDDAACABCDABD]
目標字串         [A BCDABD]
                 ^

這就是問題所在， KMP 主要就要解決這種問題． 所以如果你只單單的移到 A 接下來往後的一定是 B 一定又會發生不同，而必須要在移動一次．

方法論:

簡單的原理條列如下，主要是修改在 failure function 索引表的數字:

• 如果發現前面有同樣的，先查看下一個是否跟前面的下一個是同樣． 如果是就在往前面一個相同的找． 簡單的說： 遇到連鎖，就再往前找．
• 如果不是”連鎖”，就可以單純的把前面的位址記錄下來．

以下拿上面的例子來做一次 kmpNext

目標字串   [ABCAB]

依照MP演算法，計算數字如下


目標字串   [A  B C A B]
mpNex    [-1  0 0 0 1]

但是由於找到第二個A的時候，發現第二個A的後面是B，而第一個A的後面也是B．於是就必須往前找． （往前找的動作，在程式碼裡面就是直接把前一個的 kmpNext 數值直接給後面．


目標字串   [A  B C A  B]
mpNext   [-1  0 0 0  1]
kmpNex   [-1  0 0 -1 0]

時間複雜度:

• 最差狀況 O(m+n) 但是在某些狀況下，也就是你要尋找的字串如果具有相當多的連鎖． 比如說 ABCABCAB 或是 AAABCDBCDBCD 的狀態下就會變得比較快．

參考鏈結

• Knuth-Morris-Pratt algorithm
• 理解KMP算法
• String Matching: 各種演算法介紹
• youtube: Tutorial: The Knuth-Morris-Pratt (KMP) String Matching Algorithm
• youtube: Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)
• Regular Expression Matching with a Trigram Index

一般而言，因為你沒有Eclipse的專案檔案，你無法直接載入． 你需要安裝 nodeclipse ，整個簡單步驟如下:

You need install nodeclipse, first.

1. npm install -g nodeclipse
2. Go to your folder, nodeclipse -g to generate nodeclipse project setting.
3. Open it from Eclipse “import from exist projects”.

這樣在 Eclipse Import 就會找到有那個專案．

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

• 主要會貼一些github，但是會盡量寫上一些有用的評語（或是我容易想到的關鍵詞）幫助以後查詢

網路文章心得:

• 會寫些心得，強迫自己閱讀．

“程式週記”並且定期週期性更新．

大部分內容在我的twitter都會有，這邊只是將一些簡單的心得與感想註解一下．

本週摘要

本週只有三天，工作上再思考一些自動化處理的方式．並且也把微軟的 Bot Framework 又看了一次，也思考一下該如何做．

本週的重頭戲就是 Ubuntu on Windows Insider 測試版本 14316 有公佈．大家可以玩玩看．

最後，本週專案就是一個簡單的 Go Plurk Post Server，主要是讓 IFTTT 可以接 Twitter 資料進來，然後轉到這個伺服器上面貼文到Plurk． 主要都是因為我懶.. XD

Go

Golang 1.6.0 與 1.5.3 重大安全漏洞

一個安全報告指出，目前的 Golang 1.6.0 與 1.5.3 有重大安全漏洞，大家記得要更新 1.6.1 跟 1.5.4

Github: Big Data (Gigabytes) cache

It omits GC to handle it to save performance

Writing a very fast cache service with millions of entries in Go

這篇文章的出發點是想要幫團隊裡面架設高效與高吞吐的 cache service ，透過研究之後決定使用 Go 來開發，並且整理出出的一些小訣竅．

Fast HTTP package for Go. Tuned for high performance. Zero memory allocations in hot paths. Up to 10x faster than net/http

號稱比起原生的 net/http 還快上十倍的 HTTP package，可以看看．

Efficient cache for gigabytes of data written in Go.

有效存取大量資料的暫存，並且可以避免被 GC 拖累速度的工具．

Paranoid text spacing in Go (Golang)

Vinta 大大的作品，可以把英文字跟中文字中間加上一個空白．官方網站在這裡．

slack based chess client

可以在 Slack 上面下西洋棋的工具．

Echo is a fast and unfancy web framework for Go (Golang). Up to 10x faster than the rest.

一個號稱又快又具有彈性的 Web Framework ，由於底層使用 fasthttp (也就是稱為有比原生的 net/http 快十倍的 http 工具) ． 所以其實這個 Web Framework 相當令人期待．

Paper: Stream Control Transmission Protocol in Go

一篇講解如何在 Go 上面實作流量傳輸控制協定的論文．

Use Go, Dump Node

講解為何作者會決定離開 Node.JS 轉到 Go 的故事．

High-Performance Network Tuning for Go & NodeJS Apps

不論你寫 Go App 或是 Node.Js App ，先看看這篇把系統的一些參數做一些適當的調整． (每次看完就忘記，還是得重新打開來找）

Python

Android/JAVA/NODE.JS

Docker

Docker in Golang

當初有參加 Docker Meetup #2 看到的Slide，兩年後忽然想起來把Slide 找到來好好溫習一下，Docker 第一個commit 到底做了什麼事情

Drone is a Continuous Delivery platform built on Docker, written in Go

用 Go 寫的 CI 系統，雖然不錯但是要接其他部分還有點麻煩．

用 Docker 架設 GitLab CI、GitLab Runner

印象中這大概是看過第二次有類似的文章，其實整理的很好．

PTT: 自動化組態設定工具的經驗

相當好的分享文，可以了解自動化組態設定各種工具的應用範圍．並且有一些心得分享．

iOS/Swift

網站文章

Homebrew Changes

Homebrew 把套件管理(package manager)跟配方(fomula) 拆開變成 Homebrew/brew 跟 Homebrew/homebrew-core

Git 2.8 update

Git 2.8 的更新很確切的解決我的很多痛點:

• 提升 submodules 更新的效能
• 不用再填 git config user.email 跟 user.name
• 針對Windows 文字檔案，遇到 LF (Unix 斷行) 分隔的檔案，會自動認為是 CRLF (Windows 斷行)

更多請參考 Git 2.8 release note

Bash on Ubuntu on Windows begin on EEAP #14316

• 之前微軟 Build 最熱門的話題，不外乎就是 Ubuntu on Windows ，這一篇有 step by step 告訴你該怎麼啟動這個功能．

臉書 DevOps 社群: DevOps engineer 面試經驗分享

一個神人 MIS 面試 DevOps 的感想，不僅僅有白板寫出 KMP 還有講解第一個 Docker Commit． 真的很有深度．

星巴克教我們的軟體可擴充性

透過星巴克裡面從點咖啡直到咖啡交到你手上的流程，來看軟體產業的可擴充性該怎麼去思考． 挺值得一看的好文章．

網站收集

Oreilly generator

最近不少好笑的書頁都可以透過它來產生．

Line 全球一萬組BOT API Trial Account帳號開放申請了

限量申請而且不保證可以一直使用．有開起來用用看，發現需要SSL Endpoint 的伺服器，又得去找找看哪裡有免費的可以使用．

有聲書/影片心得

本週專案

這邊會寫一些我的Project 52的成果.

本週專案: https://github.com/kkdai/plurk-makerserver

主要是因為我在手機上都是使用 Twitter 如果還要轉發到 Plurk 其實還要多跑一個流程． 本來是想寫一個 iOS 的 App Extension ． 不過本週專案我又想不出來，只好拿出來解決一下．

問題又一樣，其實程式碼不難．還是 Deploy 那個按鈕讓我搞了好久． 真是有一點麻煩．

Plurk 一直是台灣人很愛的推文服務．不過因為只有台灣在使用，所以許多大的服務（比如說 IFTTT ) 就不太理他． 之前本來還可以很簡單的透過 Email 來發送噗，結果也不知道為何關閉 （聽說要收費？） ． 於是想了很多方式來弄，都還是有點麻煩． 最後還是自己寫一個 Server 來給 IFTTT 使用

如何讓你的 Twitter 轉發到 Plurk ?

首先申請一個 Plurk APP

1. 先到這個地方，申請你的 App．
   • 類別: 手機或應用程式
   • 其他相關資料填寫可以參考這篇文章
2. 點下測試工具
3. 取得以下四個數值
   • App key
   • App secret
   • Token
   • Token secret

在Plurk App就算是完成，接下來要到 IFTTT設定

再來架設你自己的Plurk Maker Server

到 https://github.com/kkdai/plurk-makerserver 按下下面的按鈕

記住你的 Server URL 等等要使用

在 IFTTT Maker 上的設定

1. 接下來到 IFTTT Maker 申請一個帳號．

2. 建立一個 IFTTT Receipt ， 前端用 Twitter 接起來，後面接到剛剛建立的 Maker ．

3. Maker 設定頁面上，資料依照以下的格式來填:

• URL : 你剛剛的 Server URL
• Method: POST
• Content Type: application/json
• Body: 依照以以下的修改，貼上去

// 記得將以下資料換成剛剛在 Plurk 拿到的資料
// [[App key]]      -> App key
// [[App secret]]   -> App secret
// [[Token]]        -> Token
// [[Token secret]] -> Token secret
// [[Text]]         -> 改成 twitter 內容 

{"ConsumerToken":"[[App key]]", "ConsumerSecret":"[[App secret]]", "AccessToken": "[[Token]]","AccessSecret":"[[Token secret]]", "Msg": "[[Text]]"}

這樣就可以了…. 有問題來討論…

這是什麼?

程式週記主要內容如下:

Gihub project 介紹:

• 主要會貼一些github，但是會盡量寫上一些有用的評語（或是我容易想到的關鍵詞）幫助以後查詢

網路文章心得:

• 會寫些心得，強迫自己閱讀．

“程式週記”並且定期週期性更新．

大部分內容在我的twitter都會有，這邊只是將一些簡單的心得與感想註解一下．

本週摘要

最近幾週越來越少有時間可以好好的把每週專案來寫, 主要是因為這一週都把時間拿去重新閱讀 Raft Paper. 只好這一週寫一個小工具 slack-console 來幫助自己管理伺服器上面發生的問題.

Go

Building Minimal Docker Containers for Go Applications

這一篇主要是討論如何編譯出一個最小的docker container給Go application使用．

以下的方式可以:

• CGO_ENABLED=0: 拔掉CGO (在Go裡面使用C的library， 如果你沒用到)
• GOOS=linux: 預設定好環境 linux
• -a: 連所有的使用到的package都重編譯(在這邊，一併會把cgo拿掉)
• -installsuffix cgo: 前面明明把cgo拔掉，為何後面還要把需要的部分加回去呢? 因為這是Go 1.4 的workaround

全部參數如下:

CGO_ENABLED=0 GOOS=linux go build -a -installsuffix cgo -o main .

另外一個可以參考的repo go-proxy: A simple proxy implementation

剛剛測試，以上的部分在Go 1.6 沒有看到太大差異．可能因為我還沒有用到太複雜的package.

LeftPad and Go: can tooling help?

從 Go 開發者角度來看 LeftPad 事件

Writing a Text Adventure Game in Go

透過 Go 來寫一個文字冒險遊戲

Paranoid text spacing in Go (Golang)

Vinta 大大寫的工具, 可以自動幫你把中文與英文中間加上空白. (Paranoid text spacing)

Python

Android/JAVA/NODE.JS

Docker

Docker image for thumbor. Detectors, optimizers, lazy detection and separate docker for remotecv.

透過 docker 架設一個具有自動縮圖與人臉辨識的伺服器, 從碼天狗看到的.

Docker Monitoring with the ELK Stack: A Step-by-Step Guide

透過Docker來架設ELK (Elasticsearch, Logstash, Kibana)的架構．

Docker Machine driver plugin for xhyve (native OSX hypervisor)

排不到 Docker for MacOSX Beta ? 先來看看裡面用的技術, 也就是原生的 MacOSX Hypervisor (xhyve) Driver.

iOS/Swift

網站文章

Ubuntu on Windows — The Ubuntu Userspace for Windows Developers

Microsoft Build第一天最大亮點: Windows 10 新的更新將不僅僅是bash shell 而是整個ubuntu user space，所以你還可以使用 gcc, vim, sed, find, sort… 所以應該可以跟cygwin說再見…

不是透過VM，而且你也會有 /usr 類似的目錄可以使用.. 我想.. Windows 真的越來不像Windows… 不知道大家喜不喜歡…

網站收集

Build 2016

每年又到了微軟最大的開發者聚會 Microsoft Build 今年亮點不少, 大家可以看看 :

• MSFT: Bot Framework
• Linux User Space include (Bash Shell for Windows)
• Xamarin integrated in Visual Studio and open source

MSFT: Bot Framework

微軟同時宣佈他們新的 Bot Framework 一個架設在網路的機器人架構, 可以透過這個在 slack, skype 甚至是 IM 上面建立機器人. 透過機器人可以幫助你查詢甚至是做更多的事情.

有聲書/影片心得

本週專案

這邊會寫一些我的Project 52的成果.

本週專案: https://github.com/kkdai/slack-console

一個可以快速幫你在 slack channel 發言的小工具，適合放在 server 上管理機器用.

本週專案比較小, 主要是寫小東西來避免每次打 curl 要落落長的 comment . 這個使用也很簡單, 比較複雜還是在取得 Slack IncomingWebHook.