前言 主要是因為有大師推薦，然後發現這堂課的教授就是所謂的Compiler恐龍課本的作者Jeffrey Ullman(Compiler Design的聖經)． 加上自動機本身不僅僅實作牽扯到regular expression之外，更在分散式系統中的狀態機(state machine)扮有相當重要的部分． 所以需要來好好學習． 課程鏈結在這裡https://class.coursera.org/automata-004． 相關文章 [Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata(本篇) [Coursera][Automata] 自動機理論-Automata筆記-第二週: Regular Expression [Coursera][Automata] 自動機理論-Automata筆記-第三週: Context-Free Grammars and Pushdown Automata [Coursera][Automata] 自動機理論-Automata筆記-第四週: Pushdown Automata and Properties of Context-Free Languages [Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability [Coursera][Automata] 自動機理論-Automata筆記-第六週(上): Intractable Problems and NP-completeness [Coursera][Automata] 自動機理論-Automata筆記-第六週(下): Intractable Problems and NP-completeness 第一週課程 DFA(Deterministic Finite Automata)基本定義 alphabet: 任何有限的符號集合． (可以是ASCII也可以是Unicode) ex: {0,1} (binary alphabet), {a,b} {s,p} 都是alphabet string: 透過alphabet產生的list，其中每一個元素都要是該alphabet其中一個元素． length代表的是該string有的個數． ex alphabet {0, 1} 其 string {01} length=2 ε 代表是empty string其中他的length=0 language: 為alphabedt產生出所有string的subset． DFA: Deterministic Finite Automata: A formalism for defining languages．由以下組成: 有限的狀態(states) 表示為 Q 固定的input alphabet 表示為 Σ 一個起始狀態 (start state) 表示為q0 至少一個結束狀態 (final state) (這裏指的final state也是指可接受的狀態) 表示為 F 一個transition function 表示為 δ(Q, A)其中 A 代表是一個輸入的 alphabet transition function代表的是，一個輸入所要進入的一個狀態． δ(Q, A) 代表是從狀態Q透過輸入A來計算下一個狀態會是哪裡． 範例: {0, 1} 是一個alphabet {0, 1}* = {ε, 0, 1, 00, 01, 10, 11, 010, …} 是alphabet {0,1}為可能出現的string組合，其中 {e} length=0 {0} length=1 {00} {01} {10} {11} length=2 如果要討論language，我們可以說 {ε,...

##前言 其實Docker一直是我一個很想玩但是玩不起的技術．主要是因為我的MBA空間太小，隨便一個docker image 就有3~5G．小小128G MBA實在無法來順利成行． 最近有要跨平台跑東西的需求，決定弄幾個docker image可以幫助我處理一些令人討厭的設定． 這次主要是用到Windows桌機，裡面至少有足夠的硬碟空間可以讓我做這件事情． Docker Windows 可能遇到的困難與筆記 ####Docker Quickstart Terminal的console 顯示實在令人搖頭 Windows 上的Docker Quicktstart Terminal 使用MingW Console本來也是還好，但是在我電腦實在就有console顯示的問題． 建議使用ssh login來跑． 方法如下: 跑”Docker Quickstart Terminal” 來將docker VM 跑起來 你會看到 "default" machine with IP 192.168.99.100 (每個人IP不同) 使用putty來登入SSH putty.exe -ssh [email protected]:2376 -pw tcuser 帳號跟密碼都是docker預設，沒有改過應該就可以正常跑． 把以上的指令弄成捷徑在桌面，就可以登入數個docker console Docker Quickstart Terminal console 會遇到的 volume mount問題 Docker -v提供一個很好的方式可以讓本地端的檔案跟docker container去對應與操作．但是在Windows上面會遇到永遠找不到的路徑問題．（詳細可以參考這裡 還有這個) ##這樣在Windows boot2docker 跟 docker quickstart terminal 都會失敗 docker run -v /c/Users/USER/TEST:/OUTPUT --rm=true DOCKER_IMAGE_NAME ##必須使用以下的指令 注意是"//c" 而非 "/c" docker run -v //c/Users/USER/TEST:/OUTPUT --rm=true DOCKER_IMAGE_NAME 這個問題在我剛剛提到使用SSH console是不會有這樣的問題的，所以我強烈建議各位使用docker SSH console． 建立Dockerfile 想要建立一個Docker Hub可以讓人家可以下載的Image或是 Dockerfile，其實不難．步驟以下: 先建立一個github repository裡面只需要有Dockerfile (當然有README.md 更好 :) ) Docker Hub (記得要先註冊帳號) 的 Dashboard 選取 [Create] -> [Create Automated Build] 輸入Github帳號去鏈結，選取剛剛建立的github repository 他就會抓取Dockerfile自動跑 建立一些成果分享 Docker image for building OpenSSL for Android 其實會使用這些前提，如果你跟我一樣是: 在Windows 上寫Android App 極度討厭 Cygwin跟MinGW 對於build module一向講求，build完就不需要那些環境 之前做法當然笨笨的使用VM建了一個超肥的VM裡面也裝了一堆不知道有什麼東西．來build一些需要的module． opencv ffmpeg都是如此． 這次我改成自己Dockerfile 參考這裡

##前言: 當初錯誤的決定，MBA 128GB 造就我很愛花時間找有沒有東西可以清， 分享一下我使用Mac Book Air 128G 尋找空間的心得． 查看每個程式佔多大空間 顯示隱藏資料夾 這邊需要console指令，方法為以下: 開啟一個showHiddenFiles.sh vi showHiddenFiles.sh 輸入以下指令: defaults write com.apple.finder AppleShowAllFiles TRUE killall Finder 存擋，並且記得把權限打開chmod 660 showHiddenFiles.sh 執行這個會把所有finder都關閉，但是可以之後可以顯示所有隱藏檔案 ( .git 也會出現) 恢復隱藏資料夾 反之，如果要把隱藏資料再次的隱藏起來，可以輸入以下的指令: defaults write com.apple.finder AppleShowAllFiles FALSE killall Finder 讓Finder裡面顯示資料夾空間 (圖片來自: http://www.iclarified.com/14356/how-to-display-folder-size-in-mac-os-x-finder) 主要的方式是到[Finder Menu]->[顯示方式: View]->[打開顯示方式選項: Show View Options]->[計算所有大小] 砍掉Xcode Debug Symbol 主要是參考這篇文章 提到的第四項可以清掉一些xcode debug symbol．每個OS版本也接近1G. 這樣清下去也有20~30G 空間 就算多砍也沒差，反正你手機接起來要debug又會把他都複製到電腦裡面了． 到~/Library/Developer/Xcode/iOS DeviceSupport/ 裡面會顯示許多版本的iPhone Debug Symbol (ex: 8.3 (12F70)… ) 移除掉比較舊的版本Debug Symbol 跟我一樣MBA SSD快爆的人來看看… 馬上又一條活龍…

論文: Raft Paper (這是Raft Consensus Algorithm 的展示工具Raft Scope) MIT 6.824 分散式系統 系列文章 6.824: Distributed Systems [MOOCS][Golang]MIT6_824 Distributed Systems Week2(Lec2/Lab2A) [MOOCS][Golang]MIT6_824 Distributed Systems Week2(Lec2/Lab2A) [MOOCS][Golang]MIT6_824 Distributed Systems Week2(Lec2/Lab2B) [MOOCS][Golang]MIT6_824 Distributed Systems Week3- About Paxos Algorithm [MOOCS][Golang]MIT6_824 Distributed Systems Week4- 關於Consensus協定 Raft 學習(一): 簡介，資料格式與領導者選舉 前言 持續學習MIT分散式系統課程的時候．學完了Paxos，接下來就要學習很多系統都有使用到的Raft系統． 這次一樣直接看Paper後，試著把整個邏輯實現出來．這裡先把演算法根據我瞭解的部分在記錄一下學習心得． Raft介紹 這裏整理出一些關於Raft的介紹． 什麼是Raft Consensus Raft跟Paxos一樣，都是為了讓多個log伺服器的備份機制所產生出來的溝通演算法． 不過，根據RaftPaper裡面提到的，為什麼會提出一個新的演算法．就是因為Paxos真的太難理解了(這裏引用的已經是簡化過的演算法，但是還是相當難理解)．所以他們提出Raft演算法，並且針對兩個主要的目標: 可理解性: 務必讓Raft的理論容易了解． 容易實現: 必須讓整套系統是容易被實現並且是容易建置的．並且能達到所保證的效能． Raft機制用在哪裡 如同前面說的，由於Paxos本身太過於困難了．所以Raft演算法在2014發布後迅速地成為許多分散式伺服器對於資料的同步協調最佳的應用． 以下列出幾個最近比較知名的伺服器架構: etcd: 相當知名的分散式key/value的資料庫 cockroachdb被稱為是小強資料庫，不論有沒有連到Server都可以保證你可以使用．並且在連線後自動同步與協調相關資料． 這邊只挑出兩個最近比較紅的，其實還有相當的多． 基本上分散式資料庫近幾年都會採用Raft架構． Raft主要關鍵: 在Raft系統裡面，主要分成三個關鍵的功能： Leader Election (領導者選舉): 這裏講的是關於領導者的選舉過程，還有其他角色(候選人, 跟隨者)如何轉換角色的過程． Log Replication (資料複製): 這裏提到對於log的相關記錄與處理方式，主要是要確保每一台伺服器的資料能夠精確同步而達到資料最少的遺失率． Safty(安全性): 透過Raft可以達到資料的準確性與資料可恢復性． 主要角色: (圖片來自: Raft Paper，本圖主要講解三個角色關係切換示意圖) 再來要提到提到主要的角色: Follower (追隨者): 基本上一開始每一台機器都被設定成為追隨者的角色．但是有一台收到來自狀態機的指令後，就會開始競選成領導者． Leader (領導者): 主要接受來自於狀態機(在Raft中，狀態機就是我們的client，由狀態機發送每一個指令的log．透過Raft來達成多台同步的效果） Candidate (候選人): 領導者不一定永遠都是完好的狀態等待狀態機的發送，某些狀況下如果領導者發生斷線或是系統出問題的時候．就會有一個跟隨者跳出來要競選成領導者． 相關的細項之後會提到． 關於資料結構(Log Structure) (ch. 5.3) 這裏先解釋一下，這一張圖主要表示的就是在多台Raft伺服器中，主要資料Log的儲存方式: log index: 是一個流水號碼，代表你處理的的資料個數． 產生的人：每個Server自己保留一份log index term: 也就是在每個小方格上面的號碼，代表的是處理的第幾個指令集（複數個指令）． term的產生是由狀態機(state machine: 在這裏也可以說是client)產生出來的． 也就是說term是由 領導者收到後傳給每個跟隨者，而不是跟隨者自己產生的． 這裏要注意的是一個指令集可能會有兩三個指令． 比如說 領導者的 Term 1: 就有 x <- 3, y <- 1, y <- 9． 但是他們代表的資料Index (Log Index各不相同) operation: 也就是主要的log資料，代表的是Client傳過來的指令(單一個)． 比如說是 x <- 3 產生的人: 也是由狀態機(client)產生． 回過頭來解釋，這一張圖想要代表的意思: 每個橫向代表著一台伺服器儲存資料的內容． 第一個為領導者，其餘都是跟隨者 正常而言: 每一個伺服器的資料之間，如果term的數值是相同的，並且log index也相同就會認為兩個伺服器是相同的資料． 舉例而言， 領導者跟 跟隨者(2) (第三橫列)是相同的 關於資料的比對 兩個伺服器如何比較自己所擁有資料比較齊全呢? 這裏是先提到，基於這樣的資料結構，我們要怎麼說伺服器A所有的資料比伺服器B還要多，還要新呢? 以下這邊有一些原則: LogIndex與LogTerm組成伺服器本身的權重代表，擁有最多的LogIndex與最多的LogTerm就代表擁有教多的權重． 比較上，會先比較LogTerm再去比較LogIndex...

主要問題: 在iOS上面要編譯 C/C++ Static Library，除了有必要的轉換之外．最麻煩的大概就是先把多個平台iphoneos跟iphonesimulator的產出library透過lipo 結合成一個所謂的 fat library之後，在複製到某個地方． 但是在Windows VC開發已經習慣使用Post Build Process的我，當然在XCode開發上面也要找出一套自動的方式來幫我完成這件很蠢的事情． 解決流程: 建立一個Aggregate 透過編輯器 [Editor] -> [Add Target] 來建立一個Aggregate (記得之後要build就要選擇這個target)． 至於選擇Mac 或是 iOS的沒有差異． 這邊只需要輸入一個target 名稱後就可以了． 建立一個 Run Script (圖片來自 Apple Developer) 如同上圖所示，在Target 選擇設定，選擇剛剛建立的Aggregate，然後到 [Build Phase]裡面去 點擊+ 來新增 “Run Script” 以下為範例的Build Script，主要是把專案”ABC”的Debug-iphoneos 跟 Debug-iphonesimulator 的輸出結合到另外一個目錄． xcodebuild -project abc.xcodeproj -scheme ABC -sdk iphonesimulator -configuration Debug xcodebuild -project abc.xcodeproj -scheme ABC -sdk iphoneos -configuration Debug # make a new output folder mkdir -p ${TARGET_BUILD_DIR}/../outputABC # combine lib files for various platforms into one lipo -create "${TARGET_BUILD_DIR}/../Debug-iphoneos/libABC.a" "${TARGET_BUILD_DIR}/../Debug-iphonesimulator/libABC.a" -output "${TARGET_BUILD_DIR}/../outputCCS/libABC.a" 當然，你也可以把檔案輸出到專案目錄下面，方便你以後管理． 衍生應用 你可以每次build的時候增加版本號碼，這是其他人比較喜歡用的． 可以參考這篇 心得與應用: 這一篇文章，主要就是讓Engineer可以簡單地透過Cmd + b來編譯一個特殊的Aggregate target來執行一堆本來是透過CI來跑的 Script． 這樣一來，Engineer可以邊修改，邊把相關檔案編譯出來． 而最後要導入CI的時候，該Aggregate target也可以直接拿來編譯． 參考文章: Automatic build of static library for iOS and many architectures Apple Developer:Running a Script While Building a Product 更複雜的iOS build tool: Thoughts on iOS build tools

前言: 主要是想了解一下，R-Programming 有什麼樣在大型資料處理上的優點．以及為何許多Data Science 都會選擇使用R作為資料處理的主要程式語言． 這一篇是一個月來的修課心得，主要整理一些自己的筆記． 心得: 學習玩 R Programming 會覺得其實R是蠻值得花時間學習的．個人提供一些心得如下: R的資料型態很特別，很”資料導向”． 詳細可以參考這篇R資料格式教學 R對於資料的操作也很特別，尤其是對於data frame的操作思維是其他語言不容易見到的． 透過 row 跟 col 直接來尋找，取出並且操作． 許多函數都相當的直覺，很適合初學者學習．比如說想找有幾筆資料就打nrow()想知道欄位名稱就打colnames()，要算平均就打 mean()．也難怪聽說R都是一些數學很好但是可能是程式設計的初學者． 課程筆記: 第一週 課程內容: 本週課程內容主要是教導基礎的R-Programming，R的資料格式提供了不錯的資料處理能力．舉幾個例子來說: vector 產生指令: c( ... ) 產生出的vector會變成同一個class，不同元素會採取比較寬鬆的class來包括 如果你打 x <- c(1, 'a') 則會把全部元素轉成 character (包括 1) list 產生指令: list( ... ) 跟vector不同，每個元素可以是不同class 操作方式: 給值: x <- list('a', 2, TRUE) 取用: x[[1]] # 'a' matrix 產生指令: matrix( ... ) 每一個元素都是integer 可以直接給值 x <- matrx(1:6, nrow=2, ncol=3) 也可以透過 cbind() (column bind) 或是 rbind() (row bind) 來組合出matrix 資料處理上，R 其實還挺方便的: x <- list(10, 5, 7, 20, 1, 3) // 找出 所有 x > 10 x[x > 10] [[1]] [1] 20 // 找出 x>10的index which(x>10) 第二週 課程內容: 主要講解control flow (if, for, while …) 跟Function and scope． 主要提提scope: Function中可以define function: #cube 裡面還有一個 function n*n cube<-function(n){ sq<-function() n*n n*sq() } Free variables #指的是並沒有被清楚assign 的變數 cube<-function(n){ sq<-function() n*n n*sq()+y } # 這個例子裡面 y就是 free variables Lexical scoping v.s. dynamic scoping lexical scoping: free...