前言 一直以來，我有在追蹤許多優秀工程師的github(RD的臉書)．其中尤其是dgryski． 因為他有許多有趣使用Golang來開發的演算法小專案，所以我也會一起學習一些演算法與特別的資料結構． 本週的課程是Trigram Indexing．一邊學習，一邊寫成小專案． 什麼是Trigram Indexing 直接打Trigram會找到一堆關於卦的資料．不過Trigram主要是由兩個字組合而成 Tri-gram 也就是三個字元（N-gram中的tri-gram)． 其實Trigram很簡單，主要就是把一串文字透過三個三個來分組: 將所有字元改成小寫 把每個空白處理．這裡有些不太相同，不少人將空白作為分隔符號．而Google Code Search把空白當作其中字元放進去． 把字元做成trigram 如何做把一個單字做 Trigram 拆解 舉例: Search 變小寫 “search” 開始拆解，三個三個為一組 sea ear arc rch 如何在程式裡實作拆解trigram 其實在程式裡面實作拆解很簡單，只是重要的是要如何比對．因為如果你真的把"sea"， "ear" …. 存成字串，比對又是相當的消耗時間．所以不論是Google還是一般人在做Trigram的時候都會這樣拆解． 講一個個字元換成ascii的uint32並且透過位移方式存放．舉例而言s := "abc"就變成 uint32(s[0]), uint32(s[1]), uint32(s[2])也就是 97, 98, 99．並且透過位移存放．97<<16 + 98<<8 + 99 = 6382179． 這樣比較的速度就會快的更多，也很適合儲存． var trigrams []uint32 //存放所有拆解好的trigram s := "abc" //要拆解的字 for i := 0; i <= len(s)-3; i++ { //透過將每個字元轉換成uint的方式，並且透過位移方式存放 t := uint(uint32(s[i])<<16 | uint32(s[i+1])<<8 | uint32(s[i+2])) trigrams = append(trigrams, t) } //最後結果 6382179 如何在Code Search中使用 這邊開始很建議打開Russ Cox關於Google Code Search的介紹文章，雖然主軸是Regex 不過是透過Trigram Indexing的方式． 如同前面提到的，由於這個是”Code Search” 所以空白本身相當的重要．也就必須要將空白當作一個字元來作為Trigram Indexing的來源． 請注意： 本文重點在於討論Trigram Indexing，所以原先在Google Code Search針對Regex處理的部分就不討論． 透過簡單例子來了解 比如說，我們現在要輸入搜尋的是以下三段文字: Google Code Search Google Code Project Hosting Google Web Search 處理空白與加上Trigram Indexing 接下來，讓我們真的來處理一些字串，這裡結果就會有點複雜，所以我們只拿第一段文字舉例： “Google Code Search”來做Trigram Indexing: "Goo", "oog", "ogl", "gle", "le_", "e_c", "_Co", "Cod", "ode", "e_S", "_Se", "Sea", "ear", "arc", "rch" 在每一個Trigram上加上Document ID Document ID就是你原本是第幾段文字(以這裡為例子），當然隨著文件變大，有可能是檔案或是磁碟代號． 這裡將以上的每個資料都加上 {1}． 將Trigram 文字轉成數字方便比對 就像之前提到，要一個個比對文字 “Goo”比對 “Goo” 其實在CPU上面是比較慢的．而且存放成文字也是比較佔空間．所以比較好的方式就是都轉成Ascii的方式: "Goo" = uint("G") uint("o") uint("o") =...

前言 在執行Android JNI的時候或多或少都需要在JNI中去呼叫Java的函式．（不論是只有Android才能拿到的資料，或是需要做callback) 這裡就介紹如何在 JNI thread (或是 callback)中去呼叫 Java Method． 基礎觀念 先了解基礎概念，大部分而言會有兩種狀況需要由JNI呼叫Java． Java -> Jni -> 更新另外一個Java Jni的Callback or Thread -> 更新 Java 會需要這種狀況，大部分都是(2)．當然也可能是(1)．由於在(2)的狀況下限制比較多而且比較麻煩，所以只講解(2)的部分． （當然，一樣的方式也可以適合給(1)使用． 先講解可能的限制 由於我們是從jni裡面的thread 或是 jni 去呼叫C/C++ module的callback． 所以.. 你拿不到JNI Environment JNIEnv 跟原先呼叫或是你想要呼叫的Activity的jobject． 所以這裡要先透過某個 JNI main thread的function．舉例而言，最基本的Hello World JNI 都會有個 stringFromJni() 透過那個main thread的JNI function． 相關流程 需要紀錄JVM (一般而言 JVM生命週期是每個App launch啟動） 也必須要記錄你要呼叫的 Activity 的 jobject 透過JVM取得目前的目前 JNIEnv (透過AttachCurrentThread) 依照一般流程呼叫CallVoidMethod ->GetMethodID -> CallVoidMethod(如果是呼叫void) 透過DetachCurrentThread回收相關資源 程式碼: 容易出錯的部分: 錯誤的jobject使用 這邊主要是提醒，由於JNI function 函式裡面的參數 jobject thiz的處理: JNIEXPORT jstring Java_com_example_hellojni_stringFromJNI( JNIEnv *env, jobject thiz ) 裡面的 JNIEnv *env 與 jobject thiz主要解釋如下: JNIEnv *env : 負責處理JNI的環境，千萬注意在thread裡面的JNIEnv會不同．所以要使用上面的AttachCurrentThread jobject thiz: 主要是處理該JNI library owner (Activity) 的Java Object． 這裡要主義的是這個jobject 主要是System.loadLibrary("hello-jni"); 的Java Activity，而不是呼叫JNI function 的Java Object． 所以如果你有一個Java Class (ex:JNIJava)專門處理JNI，另外一個Java Class (ex: MainActivity)去建立 JNIJava然後去呼叫他，如果你需要呼叫回去MainActivity的函式，記得要把該Activity 傳進來． (不然就是要用FindClass找到正確的) 沒有使用AttachCurrentThread，造成CALL_TYPE crash 如果在JNI native debugger 發現有CALL_TYPE error 在 jni.h．代表你再不是JNI main thread去使用main thread的JNIEnv．所以要注意． 相關鏈結 C++ callbacks into Java via JNI made easy(ier) Java Invocation

前言 其實一直以來有寫iOS的code，不過由於習慣上的因素．一直沒有使用Cocoapods． 不過最近想說弄個小iPhone App搭著Golang的專案． 所以開始玩，不過Cocoapods其實一開始沒有那麼容易入手，所以又看了些plugin希望能讓使用上更簡單． 原本CocoaPods使用方式: 原本使用方式，需要如下表: 安裝CocoaPods sudo gem install cocoapods 撰寫 Podfile (相關細節) 打上 pod install來建立相關必要檔案 打開產生的workspace 這其實還挺繁瑣的，所以去找了plugin 安裝XCode Plugin ###先安裝 Plugin Package Manager - Alcatraz 這個Package Manager在安裝的時候，會跳出一個plugin 沒有經過授權的警告，不過就跳過去吧． 安裝Alcatraz: curl -fsSL https://raw.githubusercontent.com/supermarin/Alcatraz/deploy/Scripts/install.sh | sh 重新開啟XCode就可以． ###安裝CocoaPods Plugin for Xcode 安裝好Alcatraz重開之後，打開XCode [Windows] -> [Package Manager] 裡面選取，CocoaPods Plugin 就可以． 安裝好之後，要設定一下GEM_PATH，先確認一下你安裝Pod的位置，在Console打上: dirname `which pod` 把結果填入 XCode -> [Product] -> [CocoaPods] -> [GEM_PATH] 就可以直接在XCode上面更新與修改Podfile． 如果還有出現相關問題，可以看這裡The command path could not be resolved 相關鏈結: Cocoapods XCode Package Manager: Alcatraz CocoaPods Plugin

前言: 主要是紀錄一下一些在命令列(console mode)下的快捷鍵，希望以後有需要用到可以給自己紀錄一下． Console的快捷鍵列表 參考這裡來的． 以下兩個主要是一次移動一個字 alt ⌥+F to jump Forward by a word alt ⌥+B to jump Backward by a word 這邊有其他的部分，移動字元，或是移動到一開始． ctrl+A to jump to start of the line ctrl+E to jump to end of the line ctrl+K to kill the line starting from the cursor position ctrl+Y to paste text from the kill buffer ctrl+R to reverse search for commands you typed in the past from your history ctrl+S to forward search (works in zsh for me but not bash) ctrl+F to move forward by a char ctrl+B to move backward by a char 在iTerm2 裡面編輯快捷鍵來使用一次跳一個字 參考這裡 按下 cmd + , 選取 Profile -> Keys 加入以下: 使用 Alt+ <-來向左跳一個字 Keyboard Shortcut: ⌥← Action: Send Escape Sequence Esc+: b 加入以下: 使用 Alt+ ->來向右跳一個字 - Keyboard Shortcut: ⌥→ Action: Send Escape Sequence Esc+: f

前言 主要是因為Twitter上面有人提出來想寫一個小遊戲 idea: fetch twitter timeline，隨便抽幾個tweet出來然後叫user猜這個tweet是誰發的遊戲— bちゃん (@b123400) October 28, 2015 當然，這時候就給了正在愁不知道要怎麼讓自己Project52新的專案的我有了想法來寫． 所以我的目標是寫一個Golang的Package可以去做server-side oauth，並且讀取一些Twitter上面的資訊． 關於Twitter的Three-legged Authentication 上面這張圖清楚的顯示該如何做Twitter的OAuth Login，這裡講的主要都是Server-side的部分．簡單來說步驟主要分為以下數個: 透過你在Twittter Dev App申請的App Consumer Key 跟 Consumer Secret連線到oauth/request_token 開始認證 Twitter Server會給你另外一個 token URL 會連線到另外一個網址(該網址為Twitter擁有)去輸入帳號密碼或是同意該App使用你的帳戶資料． Twitter確認完畢後，會自動轉移到當初App設定好的Callback URL 你所架設Callback URL會收到Twitter Server呼叫，並且給你以下三個資料確認你登入的狀況． oauth_token oauth_token_secret oauth_callback_confirmed 只要oauth_callback_confirmed是正確的，你就可以透過oauth_token與oauth_token_secret去連接到該使用者的一些資訊． 設定正確的App資訊 只要到Twitter的Dev App 申請頁面，就會看到以下的幾個欄位． 不過最重要的欄位還是 Callback URL Callback URL Callback URL 很重要要講三次，因為很容易讓你卡很久就是這裡． 如果你要寫server-side的oauth的話，你必須要填入可以被接受的網址． 這裡定義可以被接受網址如下: 必須不是 localhost 必須有 https:// 如果你沒有填入資料到Callback URL的話，你就會被當成是Desktop App而無法進行Three-legged Authentication． 填好這一切的資訊，就可以拿到consumer key跟consumer secret來繼續以下的部分． 開始架設本地端測試流程 等等！ 你剛剛不是說不能把Callback URL寫成 localhost嗎？ 這邊就是要教導各位，如何在本地端測試與撰寫關於Server-side OAuth的流程． 修改你的hosts，並且將localhost改成比較有意義的． (ex: 個人改成 testgoserver.com) 記得testgoserver.com 填入Callback URL 這邊建議各位，直接參考這一段Twitter Server Go． 跑起來後，記得在瀏覽器打上 http://testgoserver.com就可以了． 常見的錯誤 Desktop applications only support the oauth_callback value ‘oob’ 詳細討論看這裡 表示App被認為是Desktop App，這時候需要去 https://apps.twitter.com/app/YOUAPPID/settings 設定Callback URL 此外，這邊的網址還不能使用localhost．所以你可能得寫成某個真正的網址． 不過建議不要lock，不然會出現以下錯誤 This client application's callback url has been locked 小專案 最後，我還是整理整個架構與將幾個我馬上會用到的API成一個packagey．放在https://github.com/kkdai/twitter 參考鏈結 Twitter API authentication in Go https://github.com/mrjones/oauth Twitter:sign-in Doc Twitter: Browser sign in flow Overview

前言與心得整理 我把第六週的部分拆成上跟下，上半部主要解釋P與NP之間的定義與關係．下半部就是要介紹一些證明P=NP的一些理論與方法． 課堂到了最後，其實課堂裡面有許多有用的理論與推導想法，尤其是NP Complete推導的思路，真的能改變解決問題的思考脈絡與方法．相信也可以在以後解決問題的時候，更快可以判別問題的難度． 相關文章 [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 第六週後半部分的課程內容: 問題難度的排序 根據前一個章節的整理，我們可以把問題依照困難度排列(難->簡單)如下: (假設 P不等於NP) 無解的問題 需要Exponatial Time才能解決的問題 多項式時間，還不能決定的問題 (所謂的 NP類問題) 裡面可以再分成 NP Complete(較難) -> NP (較簡單) 多項式時間，可以決定的問題 (所謂的 P類問題) 先回過頭看 Polynomial Reduction 在繼續看Cook’s Theorem定義之前，根據NPTEL的影片，其實有很多詳細的介紹．不過針對許多名詞有不同的定義: 首先先回過頭來看polynomial time reducibility定義如下: 假設一個可判定圖靈機(DTM)，從輸入為x處理並且輸出y的處理時間為Polynomial time-bond．如果x屬於L2，我們可以寫L2從L1polynomial time reducible過來的如果滿足以下條件: L2 屬於NP類問題，如果L原本是NP類問題 L2 屬於P類問題，如果原本L是屬於P類問題 這邊也就是解釋，我們可以透過reduction把不同的問題經過歸約(reduction)後到可以處理(或是判斷)為哪一類問題． 就可以回過頭來判斷轉換錢的問題是屬於那一類的問題． 再來，根據原有的plynomial time reducibility，我們會引入另外一個名詞定義polynomially transformable如下: A language L1 is polynomially transformable to L2, if there is a deterministic polynomial-time-bounded Turing machine M which will convert each string w1 in the alphabet of L1 into a string w2 in the alphabet of L2, such that w1 is in L1 if and only if w2 is in L2 L1 is NP-Complete and L1 polynomially transformable L2. To prove NP...