September 17th, 2015

[Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata

前言

主要是因為有大師推薦，然後發現這堂課的教授就是所謂的Compiler恐龍課本的作者Jeffrey Ullman(Compiler Design的聖經)．加上自動機本身不僅僅實作牽扯到regular expression之外，更在分散式系統中的狀態機(state machine)扮有相當重要的部分．所以需要來好好學習．

課程鏈結在這裡https://class.coursera.org/automata-004．

第一週課程

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，我們可以說 {ε, 0, 1,00,01,10,11} 是我們將要用到的language

(pic: from coursera automata course lecture)

以上的圖，代表一個簡單的DFA，其中:

輸入alphabet為{0, 1}
final state為 B
dead state為 C (dead node: 也就是只走到C後不論怎麼輸入都無法到達final note)
start state為 A
transition function可以表示以下方式: A -> δ(B, 1) -> δ(C, 1)

根據以上的圖形，其實可以表示成另外一種表格方式(Transition Table):

(pic: from coursera automata course lecture)

左邊為所在的狀態節點，右邊為透過輸入0或是1將要到的狀態節點．

Transition Table 簡單範例

在A狀態輸入0會回到A狀態，輸入1會到B狀態．
狀態A輸入1, 1 會到狀態C。

Transitio Function 運算範例:

δ(B, 011) -> δ(δ(B, 01), 1) -> δ(δ(δ(B, 0), 1), 1) -> δ(δ(A, 1), 1) -> δ(B, 1) -> C
δ(A, 0) -> A

NFA(Nondeterministic Finite Automata)基本定義

NFA跟DFA有些許的不同，這裡先列出幾個幾本定義

NFA中，可以同時存在多個狀態中，也就是說δ(Q1, A)有可能出現不僅僅一個狀態Q2，而是δ(Q1, A)-> {Q2, Q3}．這代表這裡有路可以從Q1透過路線A可以到達Q2跟Q3．
跟DFA一樣，NFA一樣開始在一個start state
跟DFA一樣，NFA一樣結束在一個以上的final state

(pic: from coursera automata course lecture)

    NFA 表現起來，比較像是棋盤式．每一個狀態(格子)同一個輸入有不僅僅一個可以走得下一步(狀態)

如何把NFA轉化成DFA

從基本定義可以看得出來，NFA跟DFA的差異最大的就是:

DFA: 每一次transition function會到唯一一個狀態，也就是: δ(Q1, A)-> Q2
NFA: 每一個transition function不一定只會指向一個狀態，所以: δ(Q1, A)-> {Q2, Q3, ...}

也就是說，我們可以說任何一個DFA也可以說是一個NFA，也就是說只要DFA收到同樣的語言(language)由於輸入會是一連串，也就是說輸出也會是不僅僅一個狀態．也可以說DFA透過同一個language input可以轉換成NFA．

    δD(Q1, A) -> P
    δN(Q1, A) -> {P} 可以視為 P 為 所有輸出集合的其中一個

那麼要如何反過來將NFA轉換成DFA呢?

先就定義上的轉換

其實某種角度來說，如果把NFA的結果當成一個language的話，其實就可以被視為是DFA．也就是說：

    δD(Q1, A) -> P     //一般習慣的DFA表示方式
    δN(Q1, A) -> {P}   //一般習慣的NFA表示方式

如果把{p}當成是一種state而非是一群state，這樣就可以把NFA表示式看成是另外一種DFA。只是那麼transition function與transition table要如何運算呢? 這時候就需要用到subset construction．

Subset construction

δD({q1, q2, q3, ... qk}, A) 為一個將NFA轉換成DFA的transition function，而結果就是將所有結果的聯集合(union) i = 1, 2, 3 … k是 δN(qi, A)

也就是

    δD({q1, q2, q3, ... qk}, A) = union(δN(qi, A))  其中 i = 1, 2, 3 ... k

Subset construction的範例

透過以下的方式，我們可以將NFA的transition table，轉換成DFA的．

以下將每個流程，用文字敘述：

首先走到state {1} 這時候會透過 r 跟 b 走到 2,4 跟5 ． 由於我們要取每個結果的聯集．所以 {2,4} {5} 會被當作是我們的一個State．
接下來先走到 {2,4}, 這時候要查看 {2} 與 {4}的結果，也就是將 {4,6}{2,8}做聯集{2,4,6,8}為r的結果，而將{1,3,5}跟{1,5,7}做聯集{1,3,5,7}．
並且將以上兩個結果當作新的state加入之後要走的路途
接下來走 {1,3,5,7} 於是又繼續看 {1} {3} {5} {7}的結果．以此類推….

會得到以下結果

ε-NFA 的基本定義

對於NFA，其實是可以允許不需要任何輸入的情況下狀態(state)自己改變．這時候我們可以說是輸入為ε (因為 ε為空字串，代表的是沒有輸入)．如此一來，所出現的NFA就稱為 ε-NFA．

(pic: from coursera automata course lecture)

最後我們會導出一個定義是

    每一個NFA都是ε-NFA

Closure of States : CL(q)

這裏同時會有一個新的函式 CL(q) : 其中CL(q)代表的就是 q 狀態的closure 也就是說透過q 所有不需要input能夠到達的state．（換句話說，也就是透過q 能夠透過輸入 ε 來到達的狀態．也就是說 CL(q) = δN(q, ε)．

Example of Closure Starte

以上圖來說，這裡有一些Closure of States的範例:

CL(A) = {A} 因為沒有任何ε 的輸入可以到達的狀態．
CL(B) = {B, D} ，這裡δN(B, ε) -> D
CL(E) = {B, C, D, E}

關於第一週作業

這次作業主要都是一些基本觀念跟圖形來推到transition function 的結果．主要是多看幾次就會找出來其中的規律性．（似乎也沒有方法論可以快速找到）．

參考網址

September 16th, 2015

[Docker] 再來玩玩Docker，在Windows上遇到的困難與筆記

##前言

其實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 參考這裡

September 4th, 2015

[MBA]砍掉XCode的iPhone debug symbol 來節省MacBook Air的小SSD

##前言:

當初錯誤的決定，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快爆的人來看看… 馬上又一條活龍…

September 3rd, 2015

[MOOCS][Golang]MIT6_824 Distributed Systems Week4- 關於Consensus協定 Raft 學習(一): 簡介，資料格式與領導者選舉

論文: Raft Paper

(這是Raft Consensus Algorithm 的展示工具Raft Scope)

MIT 6.824 分散式系統系列文章

6.824: Distributed Systems

前言

持續學習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

主要指令

Raft系統者要只有兩個RPC Call:

一個是負責選舉領導者的RequestVote():
- 主要是由候選人來發起．發送給所有的跟隨者來尋求大家的投票成為接下來的領導者．
另一個是負責傳遞資料的 AppendEntitries()
- 主要是由領導者來發起，主要是管理Log Replicate的工作．
HeartBeat()負責領導者與`之間確認是否有存在的協定．
Request() 也就是由狀態機發送過來的資料，裡面存放著狀態機指令的log．

這邊只大概講解一下，這兩個RPC Call是做什麼的，之後每一個章節會透過這兩個指令將Raft整個系統兜出來．

領導者選舉 (Leader Election):

主要內容:

Raft 的領導者選舉，主要就是講解如何在跟隨者中讓某些人成為候選人並且順利的成為領導者的過程．由於一開始全部的伺服器都是跟隨者，有可能同時產生許多組候選人．那麼如何要在這些候選人中挑選就是一件重要的事情．

啟動領導者選舉的時間點:

讓所有的Raft伺服器群組產生選舉的時間點，有以下幾個時機:

一開始的時候，這時候每個跟隨者權重(rank)都是相同的．只是看各個Server 何時送出訊息．
領導者的Hearbeat()指令間隔太久，這裡要提一下．根據論文，每個伺服器對於Heartbeat()的忍受時間間隔可以是不同的．這樣一來才不會造成一次有一堆跟隨者吵著要參加競選．

跟隨者參加Leader Election 流程:

根據這張示意圖，從跟隨者變成領導者的流程．我簡單地用條列式把該做的事情講一遍．

根據剛剛提過的當跟隨者發現太久沒有收到Heartbeat()的時候，就會增加自己手上的term．
將自己角色由跟隨者轉換成候選人
發送RequestVote()除了自己以外的跟隨者 (裡面會帶有候選人自身的term，LastLogIndex跟LastLogTerm)
等待每個跟隨者的回覆，如果同意的人超過大多數(就consensus algorithm裡面，”大多數”就剛好是 1/2m + 1其中m為總伺服器個數) 就將自己身份改成領導者
如果沒有成功，則等待這段的term時間過了，在來發送一次．

這樣的選舉機制會不會造成多人參選？無法選出領導者? 或是如何挑選出擁有最多commited log的候選人？以下的部分會更詳細的解釋:

安全性 (Safety):

選舉(election)的限制 (5.4.1)

RequestVote 的限制與安全性

所有與具有領導者角色的溝通演算法中，領導者最重要的角色就是必須具有所以已經交付(committed)的紀錄(log)．所以如何讓選舉出來的領導者能具有越多已經交付的紀錄越好，就變得是重要的方式．每個準備參與選舉的候選人必須要透過以下的方式來保證:

每一個候選人必須透過RequestVote來顯示目前自己擁有最新(update-to-date)的紀錄．
- 這邊使用的是RequestVote()裡面的lastLogIndex跟lastLogTerm來傳遞溝通．
- 資料的比對上主要以lastLogTerm為主要比對項目．如果相同的時候，就會比對資料的總個數lastLogIndex．
跟隨者在回覆投票結果的時候，除了要回覆’贊成’或是’否決’外，還必須要回覆自己最新交付的紀錄（如果否決的話）．

當候選人收到其他伺服器的要求

這裏有幾個例外可能性:

如果候選人在發送RequestVote()的時候，忽然收到其他成為領導者的人送來的AppendEntitries()．
- 如果候選人收到的term與logIndex比自己高，這時候候選人就會轉回跟隨者的身份．
- 反之，則候選人會繼續自己的選舉流程．
- 最後有一種可能是都沒有候選人能夠獲得大多數的同意，所以等到time out之後就必須要重選．
此外，如果候選人收到其他候選人的需求．這個時會有以下的狀態:
- 兩個候選人會相互的比較權重(rank)，這裡的權重就是前面有介紹過的LogIndex與LogTerm的比較．透過這兩個數字可以比較出來哪位候選人比較有多一點的資料，也就是說獲得比較高的權重．
- 比較低權重的候選人會轉換身份回跟隨者，而高權重的候選人會得到回應正確的投票(RequestVote())．

解決分散投票的問題

每個跟隨者的time out都不相同，事實上每一個伺服器在起來的時候都會隨機從一個範圍中挑選自己的time out時間(舉例 150~300 ms)．
這個機制幫助我們在選舉機制裡面，大多數的狀況下只會有一個跟隨者先跳出來變成候選人並且順利地贏得選舉．

接下來:

接下來，我打算開始整理關於Log Replica部分的心得．也順便會把一些pseudo code擺上來．

全部文章列表:

關於Consensus協定 Raft 學習(一): 簡介，資料格式與領導者選舉(本篇)

[iOS][XCode][AutoBuild]建立XCode Build Script 來自動產生連接好的多平台Libraries

主要問題:

在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也可以直接拿來編譯．

參考文章:

August 27th, 2015

[MOOCs][coursera]R-Programming 學習心得

前言:

主要是想了解一下，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 variables resolved to search when function were defined.
- dynamic scoping: free variables resolved to search when function were called.

關於作業

作業者要是寫一些function，難度都還算簡單．不過也能充分體會R在處理資料上面的強大支援．

lapply 的功能很強大，可以把要處理的function 丟進去

  #load_files <- number of file name
  # read csv files into tables vector
  tables <- lapply(load_files, read.csv)

  # get mean value of each table, and also remove NA
  lapply(total_tables, mean, na.rm = TRUE)

NROW(na.omit(one_data_frame)) 可以算出data frame裡面

針對data frame 的建立，可以用以下方式丟進for裡面來處理

  #data_length 為某個特定的size
  index <- numeric(data_length)
  numbers <- numeric(data_length)
  for (i in 1: data_length) {
      index[i] <- i
      numbers[i] <- i + 5 #任意資料
  }
  ret_data_frame = data.frame(index, numbers, stringsAsFactors=FALSE)

這裏有用到計算correlation的函式cor (細節參考)，使用上記得要加上 use = "complete.obs"避免使用到空白欄位．

第三週

課程內容

對於反覆要對每一個資料表執行的指令，可以透過lapply來執行．
- 底層loop用C，可能會比較快？
- 範例：
  - lapply(x_list, mean): 針對x_list的資料，做平均值．（所已lapply回傳也都為一個list)
apply不一定比for還快，但是打的字可以比較少 (? 講義裡面是這樣講的 XD)
- 範例:
  - apply(x, 1, sum) 對x資料中的第一個維度處理”加總”．
mapply可以一次將函式套用到多個資料表中，可以用於套用多個輸入參數的函式套用．
- 範例:
  - mapply(rep, 1:5, 5:1) 對於rep兩個輸入參數第一個循序加入1, 2…5，第二個參數 5,4 … 1．
tapply更可以指定index 與資料還有其套用的函數
- 範例:
  - tapply(x, f, mean)
split可以根據輸入的資料與索引來拆該原來的資料，通常會搭配lapply來找出資料．拆出資料會有點像Group By
- 範例:
  - lapply(split(x, x$f), mean)
  - split如果透過一個維度來分割就是group by，也可以依照兩個維度來切， split(x, list(a, b)) 這樣會切出 a=1, b=1; a=1, b=2 …
關於R Debugging
- traceback()可以列出發生最近錯誤的最後幾行，沒有錯誤就沒有資料回傳．
- debug(fx)可以試著去debug某些函式，方式有點像是gdb．可以一行一行跑(n) 然後查看資料．

關於作業

要拆解資料，很多時候不一定要用split，也可以透過 data.frame來操作．比如說找尋某些資料表中 $a == “Good”的第二個欄位的平均．可以是: mean(data_x[data_x$a == "Good", 2])

關於Peer Assignment

關於範例的理解

以下講解是根據範例而不是作業解答:

     #函式 makeVector 會將輸入的數列回傳一份向量list
     #這份list 就像是 class一樣有以下功能
     # $get() 取得這份向量的cache
     # $set() 重新設定這份向量
     # $getmean()  取得這份向量的均值，注意預設是不會幫你計算．需透過setmean()寫入
     # $setmean()  寫入均值
     makeVector <- function(x = numeric()) {         
                m <- NULL
                set <- function(y) {
                        x <<- y      # (1) This writes x in global?
                        m <<- NULL   # (2) This writes m in global?
                }
                get <- function() x  # (3) Redefines get() locally?
                                     # (4) What does x do here?
                setmean <- function(mean) m <<- mean
                getmean <- function() m
                list(set = set, get = get,
                     setmean = setmean,
                     getmean = getmean)
        }

另外一個函式cachemean，解釋如下:

    #主要是將makeVector傳回的資料加以套入，如果沒有均值就會算出後加入裡面．
    cachemean <- function(x, ...) {
            m <- x$getmean()
            if(!is.null(m)) {
                    message("getting cached data")
                    return(m)
            }
            data <- x$get()
            m <- mean(data, ...)
            x$setmean(m)
            m
    }

看完可能一頭霧水，先看看要如何使用好了．

    #建立一個數列，由1,2,....25
    x <- seq(from=1,to=25,by=1)
    #將向量做出，指向z
    z<- makeVector(x)
    
    #注意，這時候無法直接取用 z
    #不過可以透過 z$get() , z$set(xxx), z$getmean() 與 z$setmean(xxx) 來使用
    
    
    z$get()
    # [1]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
    
    #如果要正常取得mean，需要以照以下的指令:
    cachemean(z)
    #[1] 13

這樣應該就瞭解該怎麼寫peer program的作業了．剩下的只有矩陣的操作．

關於矩陣(matrix)的操作

建立一個矩陣:
- x <- stats::rnorm(16)
- dim(x) <- c(4,4)
關於Inverse Matrix: 使用 solve(matrix_x)
矩陣相乘: matrix_a %*% matrix_b

第四週

課程內容

關於str()顯示資料的結構，summary()可以顯示資料本身的總結(軍職，最大，最小…等等)．
- 但是str()對於複雜的結構顯示上更加的緊湊容易了解．比如說顯示data.frame或是function．建議對於不了解的資料形式都可以適用str()來查詢．
關於隨機產生數值的函式:
- rnorm():產生隨機數值，並且可以指定由多少的均值來產生．
- pnorm():根據某些給予的機率來產生隨機數值
- dnorm():根據給予的密度來產生隨機數值
- qnorm():根據分位數來產生隨機數值
關於set.seed():
- 可以設定亂數種子．注意，如果剛設定完亂數種子則拿到的亂數會與前一次剛設定好相同．建議每次取亂數前都要設定，方便以後使用（重複使用或是取出不重複)
```
  set.seed(1)
  rnorm(1)
  // 0.18..
  rnorm(1)
  // 0.44..
        
  //重新設定
  set.seed(1)
  rnorm(1)
  //0.18..
```

關於透過亂數帶入線性代數部分:

    //x 為100個常態分佈數值的亂數
    x <- rnorm(100)
    //設定y與x 的關係
    y <-3+5x
    //在圖形上畫點
    plot(x, y)

需要在某些數值中取樣 sample(來源, 個數):
- 需要20~50取五個亂數: sample(20:50, 5)
- 將1~10以亂數以不重複的順序，取出直到取完: sample(1:10)
- 抽十個會重複 sample(1:10, replace=TRUE)
- 需要小寫英文字母中取五個單字: sample(letters, 5)
R Profiler(分析那些部分耗時):
- 不需要在一開始考慮，先把事情做正確在做得快．
- system.time() 可以產生某些函式耗時多久
- 可以使用Rprof()來幫助你分析，不過一旦執行他會把每個含式都加以評估（會變更慢）
  - 透過 Rprof()開始，跑一些要測試的功能後，跑summaryRprof()看結果．

關於作業

一些需要注意的部分:

型態轉換:
- data.frame 讀進來可以都設定是character，但是資料得要好好的轉換才好判斷．
- as.numeric()可以把字串轉成數字來取最小值min()，相反的要比較的時候記得要用as.character()轉回字串．
data.frame資料的擷取:
- 想要做出select SQL語法的話，可能要經過以下的轉換…
- data.frame[data.frame[,rol]=="VALUE", ] 可以挑出欄位rol符合 VALUE的data.frame
- 如果只要挑選某些項目，可以透過data.frame[,rol] 來找出．
刪選資料(Transform your source):
- 一般而言，資料裡面可能會有NA的資料數值，但是這次的資料更奇怪．裡面有“Not Available”．這樣造成不論是轉換上或是判別上變得相當困難．因為 is.na(“Not Available”) == FALSE
- 轉換方式是建議先把不希望出現的資料清理掉．也就是一般人家說的Big Data ETL(Extract, Transform, Load) 中的Transform (也就是清理不需要的資料)．
資料型態轉換上的失真:
- 很多時候對於資料轉換上，要小心有可能造成的失真．比如說: as.numeric("6.0") == 6 所以當你要回頭找資料的時候，可以建議先做一些轉換sprintf("%1.1f", 6) == "6.0"
關於資料排序(order):
- 排序其實就還挺簡單的，主要就是使用order()來排序．唯一比較需要注意的是，由於order()提供字元與數字排序法，但是兩者的排序邏輯是不同的，記得要把數值先轉回數字(numeric)而不是拿到文字(character)來使用．
- 在排序的時候要注意，其實可以依照兩個欄位來排序．比如說透過欄位13來遞增找，又可以透過欄位2來遞減． dataf[order(dataf[,13], -dataf[,]), ]

關於 swirl

這其實是使用swiri的教學課程，裡面有15段R Programming的基本教學課程．有點多，不過依照指示可以有完整的了解．

不過總共有15段課程其實還真不少，大概也得花個一兩個小時不斷的看才看得完．要注意修業時間是否趕得上….

[Coursera][Automata] 自動機理論-Automata筆記-第一週Finite Automata

前言

相關文章

第一週課程

DFA(Deterministic Finite Automata)基本定義

Transition Table 簡單範例

Transitio Function 運算範例:

NFA(Nondeterministic Finite Automata)基本定義

如何把NFA轉化成DFA

Subset construction

Subset construction的範例

ε-NFA 的基本定義

Closure of States : CL(q)

Example of Closure Starte

更多在ε-NFA關於transition function 的運算

關於第一週作業

相關程式

參考網址

[Docker] 再來玩玩Docker，在Windows上遇到的困難與筆記

Docker Windows 可能遇到的困難與筆記

Docker Quickstart Terminal console 會遇到的 volume mount問題

建立Dockerfile

建立一些成果分享

Docker image for building OpenSSL for Android

[MBA]砍掉XCode的iPhone debug symbol 來節省MacBook Air的小SSD

查看每個程式佔多大空間

顯示隱藏資料夾

恢復隱藏資料夾

讓Finder裡面顯示資料夾空間

砍掉Xcode Debug Symbol

[MOOCS][Golang]MIT6_824 Distributed Systems Week4- 關於Consensus協定 Raft 學習(一): 簡介，資料格式與領導者選舉

MIT 6.824 分散式系統 系列文章

前言

Raft介紹

什麼是Raft Consensus

Raft機制用在哪裡

Raft主要關鍵:

主要角色:

關於資料結構(Log Structure) (ch. 5.3)

關於資料的比對

兩個伺服器如何比較自己所擁有資料比較齊全呢?

主要指令

領導者選舉 (Leader Election):

主要內容:

啟動領導者選舉的時間點:

跟隨者 參加Leader Election 流程:

安全性 (Safety):

選舉(election)的限制 (5.4.1)

RequestVote 的限制與安全性

當候選人收到其他伺服器的要求

解決分散投票的問題

接下來:

全部文章列表:

相關鏈結

[iOS][XCode][AutoBuild]建立XCode Build Script 來自動產生連接好的多平台Libraries

主要問題:

解決流程:

建立一個Aggregate

建立一個 Run Script

衍生應用

心得與應用:

參考文章:

[MOOCs][coursera]R-Programming 學習心得

前言:

心得:

課程筆記:

第一週

課程內容:

第二週

課程內容:

關於作業

第三週

課程內容

關於作業

關於Peer Assignment

關於範例的理解

關於矩陣(matrix)的操作

第四週

課程內容

關於作業

MIT 6.824 分散式系統系列文章

跟隨者參加Leader Election 流程: