顯示具有 python 標籤的文章。 顯示所有文章
顯示具有 python 標籤的文章。 顯示所有文章

2019年2月12日 星期二

關於費式數列的那些事

最近費式數列實在有點紅,讓小弟忍不住也來玩一下。
費式數列給一個初學程式的人都能寫得出來,例如早年我忘了哪位大大在推坑我 python 的時候,就寫了個只要 4 行列出費氏數列的 python 程式,一方面展現 python 在大數運算上的實力,一方面展視了它的簡潔,像是 a , b = a+b, a 這種寫法。
a = b = 1
while b < 1000000000000:
  print(b)
  a, b = a+b, a
當然會寫是一回事,深入進去就沒那麼簡單了,詳細請參考這個網頁
最簡單、最直覺的遞迴寫法,但這其實是會噴射的,每次遞迴都會做重複的計算,於是計算以指數的方式成長,比如說我用 python 的 timeit 去測一個遞迴的費式數列函式,很快執行時間就會爆炸,大概到了 fib(30) 以上就會跑得很吃力了。
如果我們用單純的加法,從 1 開始往上加,其實只要進行 n 次的加法就能得到 fib(n) 了,執行複雜度為 O(n);如果再套用更快的 fast fibonacci,更可以把執行時間拉到 O(lg n) 的程度,只要 fib(94) 就超過 64 bits 的整數的情況下,用 O(lg n) 的演算法其實跟常數時間所差無幾。
不過呢,費式數列還有一個公式解呢,也就是:
$fib(n) = \frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n$
為什麼不用這個算式算呢?公式解不是常數時間嗎?

數學上來說:是的,但實際上會遇上一些問題,例如我們看看 64 bits 整數裡面最大的 fib(93) 為例,整數算的解為:
12200160415121876738
如果是 python 寫的公式解呢?
def fib(n):
    return (math.pow((1+math.sqrt(5))/2, n) - math.pow((1-math.sqrt(5))/2, n)) / math.sqrt(5)
print(int(fib(93)))
12200160415121913856
登登,問題大條了,答案不一樣。
何以致此,問題就來到浮點數的不精確問題,這時候就要先來一張經典的漫畫了:
我們在計算完 sqrt(5) 之後,只能用一個近似的值來表達結果,在 python 內預設是以雙精度浮點數在儲存,它跟真正的 sqrt(5) 還是有細微的差距,在隨後的 n 次方、除法上,這個細微的誤差都會被慢慢的放大,最終導致這個巨大的誤差。

幸好我們不是沒有解法的,參考了 C/C++ 版上,傳說中的 Schottky 大大曾經分享如何使用 gmp 或 mpfr 兩個函式庫,算出 e 到小數點下一億位pi 到小數點下一億位,這兩個 gnu 函式庫是所謂的<無限>位數的整數跟<無限>精確度的浮點數,當然他們不是真的無限,只是完全壓榨記憶體來記錄儘可能多的位數以求精確,理論上記憶體撐上去就能把精確度逼上去,只是有沒有那個必要就是,像是把一些無理數算到一億位(欸。
究竟這個函式庫有多麼的強大呢?我們可以來寫個簡單的,例如來算個黃金比例,只要這樣就結束了:
mpfr_t phi;
unsigned long int precision, x=5;
uint64_t digits = DIGITS;

precision = ceill((digits+1)*logl(10)/logl(2));
mpfr_init2(phi, precision);
mpfr_sqrt_ui(phi, x, MPFR_RNDN);
mpfr_add_ui(phi, phi, 1.0, MPFR_RNDN);
mpfr_div_ui(phi, phi, 2.0, MPFR_RNDN);
mpfr_printf("%.10000Rf\n", phi);
mpfr_clear(phi);
唯一要注意的是 mpfr 內部用的 precision 是以 2 進位為底,所以我們在十進位需要的精確度,要先換算為 2 進位的位數,再來就能直接算出 phi 啦,試著算過 50000 位數再對個網路上找的答案,數字是完全一樣的。
這個 library 算得非常快,一百萬位的 phi 也是閃一下就出來了,一億位在我的 64 bit Linux, 2 GHz AMD Ryzen 5 需時 37s,相比 e, pi 這類超越數,phi 只需要 sqrt(5) 真的是非常簡單的了。

扯遠了拉回來,如果我們要用 mpfr 這個函式庫,利用公式解來算 fib(93),要怎麼做呢?
fib(93) 到底有多少位數呢?我們可以用 2^n 作為 F(n) 的上界,最後所需的位數至少就是 ceill(n*log(2)),相對應的我們運算中的浮點數精確度的要求,2^n 這個上界有點可恥粗糙但有用,頂多會浪費點記憶體,最後除出來的小數點後面多幾個零而已,如果能套用更精確的上界當然更好。
mpfr 的函式庫設計精良,呼叫上非常直覺,這段程式碼其實就是寫公式解,應該滿好懂的,程式碼在此。有了這個就可以亂算一堆 fib 了,基本上要算費式數列第一億項 fib(100,000,000) 也是 OK 的(好啦我不保證答案是對的XD,至少 fib(10000) 是對的)。

But,人生最厲害的就是這個 But,公式解真的有比較快嗎?
我個人認為答案是否定的,我們同樣可以用 fast-fibonacci 搭配 gmp 函式庫來計算,因為都是整數的運算可以做到非常快,我的測試程式碼在此

同樣是計算 fib(100,000,000):
formulafib.c: 57.39s user 2.04s system 97% cpu 1:01.09 total
fastfib.c: 4.70s user 0.20s system 75% cpu 6.524 total
O(lg n) 的 fast-fibonacci 遠比<O(1)>的公式解來得快。
問題就在於,到了所謂的大數區域,本來我們假定 O(1) 的加法、乘法都不再是常數時間,而是與數字的長度 k (位元數)有關。而上面我們有提到,基本上可以用 2^n 作為費式數列的上界,也因此費式數列的數字長度 k ~= n,加法、乘法複雜度就會視實作方式上升到 O(n) 跟 O(n^2) 或 O(n lg n) 左右。
在 fast-fibonacci,我們需要做 lg n 次的 iteration,每次三個乘法兩個加減;公式解雖然沒有 iteration,但需要計算兩次次方運算,也等於是 lg n 次的乘法跟加法,然後還有除法,我們運算的又不是整數而是浮點數,這又需要更多的成本,一來一往之間就抵消了公式解直接算出答案的優勢了。

在通常的應用上以及現今電腦的實作,我們還是可以假設整數的加減乘都能在近乎常數時間內結束,這樣我們才能好好討論資料結構與演算法的複雜度,進而把複雜度學好。費氏數列的問題在於,在數字小不用考慮運算複雜度的時候,公式解和 O(lg n) 的 fast-fibonacci 看不出差異,等到 n 終於大到看得出 O(lg n) 跟 O(1) 的差異時,已經要把運算複雜度納入考量了。
理論上我們當然可以假設有個計算模型,無論有多少位的數字,無論浮點數有多少精確度要求,四則運算與次方都能在常數時間內結束,這時公式解就能來到 O(1),但這樣的假設不像停機問題假設的萬能機器,在學術討論上看來不太有意義。
利用 gmp, mpfr 這樣的函式庫,插滿記憶體甚至把硬碟當記憶體來用、把記憶體當 cache 用,浪費幾個星期跟一堆電力,我們可以把無理數算到小數點下一億位、十億位,這是前人們精心為我們建的巨塔,可是數字還是無窮無盡,站在巨塔上反而才看得出我們跟無限有多麼遙遠,誠然人腦可以透過思考一窺數學之奧妙,但不代表我們能超脫數學的嚴格限制浮空而起,妄想記錄無限,我認為是對數學的一種褻瀆。

看了這麼多碎碎念大家想必也累了,總而言之本文透過兩個實作,讓大家體會一下所謂 O(1) 公式解並不一定是 O(1),背後一定有對應的成本;還有就是把費式數列算到一億位真的有點爽,不過我想是沒什麼公司在實務上有在賣 fibonacci 相關的產品啦,除非你想像日本一樣出個寫滿 e, pi 到一百萬位的書讓人當亂數表來用。

2017年6月14日 星期三

國學常識大補帖

故事是這樣子的,大概在去年9月的時候,有一位非常喜歡批評人的教授批評大家都沒國際觀,還弄了一個<國際觀檢測網>,那時我把它們的題目都抓下來,寫了個國際觀大補帖,文章在此:
http://yodalee.blogspot.tw/2016/09/global.html

最近同一位非常喜歡生氣又總是對著那些沒有錯的人生氣的教授又生氣了,稍微瀏覽的一下相關的頁面之後,竟然發現除了<國際觀檢測網>之外,還有另外一個<國學常識檢測網>,網址在此:
http://doc.boyo.org.tw/sinology/

同樣進去有十題,看了看題目覺得哇塞這真是太狂阿!有文學有歷史有地理,把這些全部都學起來,競爭力肯定更加8.7 dB,這麼珍貴的題目不出個大補帖全部背下來怎麼可以!台灣年輕人都不學國學是國家重大危機呀!(雖然題目從簡答題變成2選1選擇題,難度大幅下降OAO)
受到傳說中在金門島上大殺四方的鍾誠教授的感召,我決定也來堅守<一個python政策>,也就是「世界上只有一個Python,Python 2 是Python 3 傳統不可分割的分枝,Python 3是目前 Python 唯一正統實作」。什麼你說 Python 3 比Python 2 晚發佈?哎呀晚成立都取代早成立的,這種事很正常啦。

從 python 2 轉換到 python 3不算太難,之前轉換時有個很大的障礙是,處理 html 的套件 lxml 還沒搬到 python 3上,這次發現 lxml 也轉換完成,剩下一些要調的就是 urllib,把 request 獨立就行了,同樣的 code 在 python 3 的實作大概像這樣:
import urllib.request

req = urllib.request.Request(TARGET)
req.add_header("Pragma", "no-cache")
response = urllib.request.build_opener().open(req)

另外就是一些 dict 介面上的變化,還有因為選擇題的關係,在取出的 tag 裡面還有 tag ,因此把 text 換成 text_content,小修一下就能動了。
同樣是開起來一直跑一直跑,出來的檔案有 1200 多行,560 題

原始碼:https://github.com/yodalee/globalizaion
大補帖:https://github.com/yodalee/globalizaion/blob/master/sinology

同樣的,我是不樂見有人真的把這個拿來背啦(同樣…應該不會有人這麼蠢吧…應該啦……)

發佈了這本國學常識大補帖之後,跟國際觀大補帖一樣,我同樣收到來自四面八方熱切的使用心得,以下僅節錄幾則:
* 去年學校的畢業典禮,禮堂不知道為什麼很熱,其他同學都忍不住出去乘涼,幸好我手邊有國學常識大補帖可以當扇子,於是只有我一個人聽到台上的演講,我現在覺得我超厲害足以打爆那些沒聽到的同學。
* 之前我的電腦中了 Wannacry,所有檔案都被加密,只有電腦裡的國學常識大補帖無法被加密,還自動幫我破解了RSA-2048,回復所有的檔案呢
* 自從讀了國學常識大補帖,我現在看到AES 256加密的一條明文跟一條密文,手指滑過就能直接把它的 key 寫出來,手指識字不算什麼什麼,靠著國學常識大補帖,我還練成了「手指識key」
* 之前我超級不喜歡吃香菜,自從讀了國學常識大補帖,就算是香菜蛋糕也能輕鬆下嚥,每位不喜歡吃香菜的人都該讀這本。
* 本來我迷上了<動物朋友>無法自拔,後來經過朋友轉介得知了國學常識大補帖,發現國學遠比動畫博大精深,終於戒了毒癮,たーのしー

算了我不嘴砲了,該工作了

2017年3月21日 星期二

用Python ctypes 建立與C的介面

故事是這樣子的,最近小弟接觸一項工作,主要是開發一套C 的API,實作大程式底層的介面,以前只有改過別人的介面,這次自己從頭到尾把介面建起來,git repository 提交100多個commit,說實在蠻有成就感的。
寫Project的過程中也發現自己對測試的經驗實在不夠,本來想說該把unit test set 建起來然後做個 regression test,結果unit test 寫一寫最後都變成behavior test 了,啊啊啊啊我根本不會寫測試啊,測試好難QQQQ

寫測試時也發現一個問題,用C 寫測試實在有點痛苦,陸續看了幾個例如 CMocka 的testing framework,實作起來還是挺麻煩的;有些要測試的功能,例如檔案parser,都需要另外找library來支援,而C 的library 卻未必合用,要放入project 的Makefile 系統也很麻煩;C 需要編譯也讓有彈性的測試較難達成。
這時我們的救星:Python 又出現了,是否能利用python上面豐富的模組跟套件,還有簡單易用的 testing framework,可以彈性修改的直譯執行來幫助測試呢?

一開始我看了一下Python C/C++ extension,這是將C的程式包成函式庫,並對它增加一層 Python 呼叫的介面,變成 Python 可以 import 的module。
但是這個方法有點太殺雞用牛刀了,這是要用在python 極需性能的部分,可以寫C 進行加速,而不是單純想 call C function 來測試。
比較好的解法是利用python 的ctypes,可以直接載入編譯好的 shared library,直接操作C 函式。引用參考資料<程式設計遇上小提琴>的話:與其做出pyd來給python使用這種多此一舉的事情,東西就在那裡,dll就在那裡,為何不能直接使用呢?
所以我們的救星:ctypes 登場了。

這篇先來談談 ctypes 的大致用法,下一篇我們來說明一下在 project 中利用到它們的地方。

首先是要引用的對象,使用ctypes 前要先把要引用的project 編成單一的動態函式庫,下面以 libcoffee.so 為例,如此一來,我們可以用下列的方式,將 .so 檔載入python 中:
filepath = os.path.dirname(os.path.abspath(__file__))
libname = "libcoffee.so"
libcoffee = ctypes.cdll.LoadLibrary(os.path.join(filepath, libname))
ctypes 有數種不同的載入方式,差別在於不同的 call convention,cdll 用的是cdecl,windll 跟oledll 則是 stdcall。載入之後就可以直接call 了,有沒有這麼猛(yay)

參數處理:

ctypes 中定義了幾乎所有 C 中出現的基本型別,請自行參考內容表格,None 則會直接對應 C 的NULL:
https://docs.python.org/2/library/ctypes.html#fundamental-data-types
所有產生出來的值都是可變的,可以透過 .value 去修改。
例外是利用Python string 來初始化 c_char_p(),再用 value 修改其值,原本的Python string 也不會被修改,這是因為Python string 本身就是不可修改的。
如果要初始化一塊記憶體,丟進C 函式中修改的話,上面的 c_char_p 就不能使用,要改用creat_string_buffer 來產生一塊記憶體,可以代入字串做初始化,並指定預留的大小,爾後可以用 .value 來取用NULL terminated string,.raw 來取用 memory block。
如果要傳入 reference ,除了 create_string_buffer 產生的資料型態本身就是 pointer 之外,可以用 byref() 函式將資料轉成 pointer。
使用 ctypes 呼叫C 函式,如果參數處理不好,會導致 Python 直接crash,所以這點上要格外小心。

我們可以為函式加一層 argtypes 的保護,任何不是正確參數的型態想進入都會被擋下,例如:
libcoffee.foo.argtypes = [c_int]
# 之前這樣會過,C function 也很高興的call 下去
libcoffee.foo(ctypes.c_float(0))
# 設定之後就會出現錯誤
ctypes.ArgumentError: argument 1: <type 'exceptions.TypeError'>: wrong type
這部分採 strict type check ,甚至比C 本身嚴格,如果設定argtypes 為:
POINTER(c_int)
那用 c_char_p 這種在C 中可以轉型過去的型態也無法被接受。

restype 則是定義 C 函式的 return type,因為我的函式都回傳預設的 c_int ,所以這部分不需要特別設定。比較令我驚豔的是,ctypes 另外有 errcheck 的屬性,這部分同restype 屬性,只是在檢查上比較建議使用errcheck。
errcheck 可以設定為 Python callable (可呼叫物件,無論class 或function ),這個callable 會接受以下參數:
callable(result, func, args)
result 會是從C 函式傳回來的結果;func 為 callable 函式本身;args 則是本來呼叫C 函式時代進去的參數,在這個callable 中我們就能進行進一步的檢查,在必要的時候發出例外事件。
def errcheck(result, func, args):
 if result != 0:
   raise Exception #最好自己定義 exception 別都用預設的
 return 0
libcoffee.errcheck = errcheck

衍生型別:

ctypes 另外提供四種衍生型別 Structure, Union, Array, Pointer 來對應C 的struct, union, array, pointer
每個繼承 Structure 跟Union 的 subclass 都要定義 _filed_,型態為 2-tuples 的 list,2-tuple 定義 field name 跟 field type,型態當然要是 ctypes 的基本型別或是衍生的 Structure, Union, Pointer 。
Struct 的align 跟byte order 請參考:
https://docs.python.org/2/library/ctypes.html#structure-union-alignment-and-byte-order

Array 就簡單多了,直接某個 ctypes 型態加上 * n 就是Array 型態,然後就能如class 般直接初始化:
TenInt = ctypes.c_int * 10
arr = TenInt()

Pointer 就如上面所說,利用 pointer() 將 ctypes 型別直接變成 pointer,它實際上是先呼叫 POINTER(c_int) 產生一個型別,然後代入參數值。
爾後可以用 .contents 來取用內容的副本(注意是副本,每次呼叫 .contents 的回傳值都不一樣)和 C 一樣,pointer 可以用 [n] slice,並且修改 [n] 的內容即會修改原本指向的內容,取用 slice 的時候也要注意out of range 的問題,任何會把C 炸掉的錯誤,通常也都會在執行時把 python 虛擬機炸了。
同樣惡名昭彰的Null pointer dereference:
null_ptr = POINTER(c_int)()
產生NULL pointer,對它 index 也會導致 Python crash。

Callback

ctypes 也可以產生一個 callback function,這裡一樣有兩個函式:CFUNCTYPE 跟 WINFUNCTYPE,分別對應 cdecl 跟 stdcall;以第一個參數為 callback 的return type,其餘參數為 callback 參數。
這部分我這裡沒有用到先跳過,不過下面的連結有示範怎麼用ctypes 寫一個可被 qsort 接受的 callback 函式,真的 sort 一個buffer 給你看:
https://docs.python.org/2/library/ctypes.html#callback-functions

實際案例

上面我們把ctypes 的文件整個看過了,現在我們來看看實際的使用案例。
這裡示範三個 C function,示範用ctypes 接上它們,前情提要一下project 的狀況,因為寫project 的時候消耗了太多咖啡了,所以project 的範例名稱就稱為 coffee,我們會實作下面這幾個函式的介面:
// 由int pointer回傳一個隨機的數字
int coffee_genNum(int *randnum, int numtype);
// 在buf 中填充API version string
int coffee_getAPIVersion (char *buf)
// 對src1, src2 作些處理之後,結果塞回到dest 裡面
int coffee_processBuf (char *src1, char *src2, char *dest, int len)
針對我要測試的 c header,就對它寫一個 class 把該包的函式都包進去,init 的部分先將 shared library 載入:
import ctypes
import os.path

class Coffee(object):
  """libcoffee function wrapper"""

  def __init__(self):
    filepath = os.path.dirname(os.path.abspath(__file__))
    libname = "libcoffeeapi.so"
    self.lib = ctypes.cdll.LoadLibrary(os.path.join(filepath, libname))
所有 header 檔裡面的自訂型別,都能很容易直接寫成 ctypes Structure,舉個例本來有個叫counter 的 Union,比對一下C 跟Python 版本:
C 版本:
typedef union Counter {
  unsigned char counter[16];
  unsigned int counter32[4];
} Counter;
Python ctypes 版本:
class Counter(Union):
  _fileds_ = [
    ("counter", c_uint8 * 16),
    ("counter32", c_uint32 * 4)]
針對 C 裡面的函式,我們把它們寫成各別的 Python 函式對應,同時為了保險起見,每個函式都設定 argstype,這樣在參數錯誤時就會直接丟出 exception;又因為函式都依照回傳非零為錯誤的規則,所以可以對它們設定 errcheck 函式,在return 非零時也會拋出例外事件。
這裡的作法是在class __init__ 裡面把該設定的都寫成一個dict,這樣有必要修改的時候只要改這裡就好了:
def errcheck(result, func, args):
    if result != 0:
        raise Exception
    return 0

# in __init__ function
argstable = [
  (self.lib.coffee_genNum,          [POINTER(c_int), c_int]),
  (self.lib.coffee_getAPIVersion,   [c_char_p]),
  (self.lib.coffee_processBuf,      [c_char_p, c_char_p, c_char_p, c_int])]

  for (foo, larg) in argstable:
    foo.argtypes = larg
    foo.errcheck = errcheck

然後就是實作各函式了,這部分就是苦力,想要測的函式都拉出來,介面的參數我就用Python 的物件,在內部轉成ctypes 的物件然後往下呼叫,所以如getNum 的轉化型式就會長這個樣子,pointer 的參數,可以使用 ctypes 的byref 。
# int coffee_genNum(int *randnum, int numtype);
def genNum(self, numtype):
  _arg = c_int(numtype)
  _ret = c_int(0)
  self.lib.coffee_genNum(byref(_ret), _arg)
  return _ret.value
getAPIVersion 是類似的,這次我們用 create_string_buffer 產生一個 char pointer,然後直接代入函式,就可以用value 取值了。
# int coffee_getAPIVersion (char *buf)
def getAPIVersion(self):
  buf = create_string_buffer(16)
  self.lib.coffee_getAPIVersion(buf)
  return buf.value
最後這個的概念其實是一樣的,我把它寫進來只是要火力展示XD,上面提到的processBuf,實際上可以把它們跟Python unittest 結合在一起,利用python os.urandom來產生完全隨機的string buffer,答案也可以從python 的函式中產生,再用unittest 的assertEqual 來比較buffer 內容:
l = 4096
src1 = create_string_buffer(os.urandom(l-1))
src2 = create_string_buffer(os.urandom(l-1))
dest = create_string_buffer(l)
ans  = generateAns(src1, src2)
self.lib.coffee_processBuf(src1, src2, dest, l)
self.assertEqual(dest.raw, ans)
一個本來在C 裡面要花一堆本事產生的測試函式就完成啦owo
如能將這個class 加以完善,等於要測哪些函式都能拉出來測試,搭配python unittest 更能顯得火力強大。

後記:
趁這個機會把ctype的文件整個看過一遍,覺得Python 的 ctypes 真的滿完整的,完全可以把 C 函式用 ctypes 開一個完整的 Python 介面,然後動態的用 Python 執行,真的是生命苦短,請用python。

參考資料:

https://docs.python.org/2/library/ctypes.html
http://blog.ez2learn.com/2009/03/21/python-evolution-ctypes/

2017年1月14日 星期六

使用bower安裝react 前端環境

最近寫message-viewer ,想在bottle.py 執行的server 上面跑React.js,於是就小找了一下,基本上排除了使用 bottle-react 這種懶人套件,我想要的就是能直接寫,同時react jsx 也能在我的管控之下的設定。
後來找到這篇文章,照著它的步驟、跟留言的回覆做就成功了,在這邊整理一下:
https://realpython.com/blog/python/the-ultimate-flask-front-end/

這裡就不介紹React.js 的運作原理了,筆者到目前也還在學,總之我們就跟裡面的一樣,先寫個 view.html,裡面沒什麼,就是用React 寫一個Hello World,直接使用cdnjs 提供的library:https://cdnjs.com/libraries/react/
<!DOCTYPE html>
<html>
  <head lang="en">
    <meta charset="UTF-8">
    <title>View Test</title>
  </head>
  <body>
    <div id="content"></div>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react.min.js"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react-dom.min.js"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/babel-core/5.8.38/browser.min.js"></script>

    <script type="text/babel">
var hello = React.createClass({
  render: function() {
    return (<h2>Hello World!</h2>);
  }
});

ReactDOM.render(
  React.createElement(hello, null),
  document.getElementById('content')
);
    </script>
  </body>
</html>

接著我們使用任何一種server 的template engine ,我這裡用的是Jinja2就能把網頁跑起來,因為script 來自CDN,所以不必特別設定就能直接使用,打開來應該會出現h1 的Hello World。
app.route('/view', 'GET', MessageViewHandler)
@route('/view')
def MessageViewHandler():
    template = JINJA_ENVIRONMENT.get_template('view.html')
    return template.render()

下一步我們要在自己的電腦上面裝上React,我們使用的是管理前端的管理程式bower,像是bootstrap, React 什麼的都可以裝,

因為我是用archlinux ,本身就提供了bower 套件,所以可以用 pacman 裝bower;非archlinux 的發行版就要用npm 裝bower:
$ npm install -g bower
使用-g 是設定global ,因為在其他project 中八成也會用到bower,但另外,為了服務載了你的project 卻沒有bower 的使用者,我們也需要設定一個npm 的文件:
$ npm init
$ npm install --save-dev bower

有了bower之後,在project 中初始一個bower:
$ bower init
設定直接接受預設設定即可,它會產生一個 bower.json 檔案,我們另外要指定bower 安裝檔案的路徑為static,這要編輯 .bowerrc 並加入下列內容:
{
  "directory": "./static/bower_components"
}
並使用bower 安裝套件,可以用 bower install <package_name> --save 或是在bower.json 中加入套件名之後,再呼叫 bower install;我們這裡用第二種方法,在bower.json 的dependency 下面加上:
"dependencies": {
  "bootstrap": "^3.3.6",
  "react": "^15.1.0",
  "babel": "^5.8.38"
}
並執行 bower install,就能安裝好所需的套件,這時project 中的檔案應該差不多是這樣:
.bowerrc
.gitignore
bower.json
package.json
static/bower_components
template/

現在可以把上面的cdnjs 換成本地資料夾的static link:
<script src="/static/bower_components/react/react.min.js"></script>
<script src="/static/bower_components/react/react-dom.min.js"></script>
<script src="/static/bower_components/babel/browser.min.js"></script>
同時在server 要加上static handler來處理所有對static 的連結:
@route('/static/<path:path>')
def callback(path):
    return static_file(path, root='static')

這樣應該就能在python server 上面寫react.js 的網頁前端了,把剛剛的view.html 打開來跑跑看吧。

2016年11月21日 星期一

利用lxml 實作高效率的parser

最近實作facebook message viewer 的時候,需要去處理相當大的html 檔案,原始檔案大小約50 MB,beautify 之後會加到近80 MB。
實作上我用lxml 來實作,用了最基本的寫法,最直覺而簡單的寫法:
from lxml import etree
parser = etree.HTMLParser(encoding='UTF-8')
root = etree.parse("largefile.htm", parser)
問題是什麼呢,這樣lxml 一開場就把整個htm 給載到記憶體裡面,消耗一堆記憶體。
我們執行一下,看到的結果是這樣:
group count 525
parse 280895 entries
./parser.py   25.80s  user 0.21s system 99% cpu 26.017 total
  avg shared (code):         0 KB
  avg unshared (data/stack): 0 KB
  total (sum):               0 KB
  max memory:                710 KB
  page faults from disk:     0
  other page faults:         181328
710KB!根本記憶體不用錢一樣在浪費…,我把這個丟到網路服務上,光記憶體就害自己被砍了。

要打造節省記憶體的 xml parser,相關的資訊都來自這篇:
http://www.ibm.com/developerworks/xml/library/x-hiperfparse/

文中提供了兩種方式,一種是在parse 中指定我們的target class,我們要實作一個class 包含下列四個method:
1. start(self, tag, attrib): 有tag open的時候會呼叫這個method,這時只有tag name跟attribute 是可用的
2. end(self, tag): tag close 時呼叫,此時這個elem 的child, text都可以取用了
3. data(self, data): 在parser 收到這個tag 中的text child的時候,會將text 變為作為參數呼叫這個method
4. close: 當parse 結束時呼叫,這個method 應該回傳parse 的結果:
之後取用
results = etree.parse(target=TargetClass)
results 就會是close method return 的結果,這個方法不會消耗大量記憶體,不過它的問題是每一個遇到的tag 都會觸發一次事件,如果大檔中之有少量elements 是想剖析的,這個方法就會比較花時間;我的案例比較沒這個問題,因為我要剖析的內容幾乎橫跨整份文件。

另一個方法是用lxml 本身提供的 iterparse,可是傳入指定events的tuple跟一個有興趣的tag name的list,它就只會關注這些tags 的events:
context = etree.iterparse(infile, events=('end',), tag='div')
for events, element in context:
  print(elem.text)
文中並有說,iterparse 雖然不會把整個檔案載入,為了加速整份檔案可能被多次讀取的狀況,它會保留過去element 的reference,因此剖析會愈跑愈慢;解決方法是在iterparse 中,取完element 的資料就把它給刪除,同時還有element已經剖析過的sibiling,在iteration 最後加上這段:
element.clear()
while element.getprevious() is not None:
  del element.getparent()[0]
要注意的一個是,使用iterparse 的時候,要避免使用如getnext() 方法,我用這個方法,有機會在剖析的時候遇到它回傳None,應該是iterparse 在處理的時候,next element 還沒有被載入,因此getnext 還拿不到結果;從上面的end 事件來說,每個iteration,就只能取用element 裡面的元素。

改寫過之後的parse 的執行結果:
group count 525
parse 280895 entries
./parser.py   22.59s  user 0.07s system 99% cpu 22.669 total 
  avg shared (code):         0 KB
  avg unshared (data/stack): 0 KB
  total (sum):               0 KB
  max memory:                68 KB
  page faults from disk:     0
  other page faults:         21457
跟文中不同,因為我有興趣的tag 比例較高,執行時間沒有下降太多,但記憶體用量大幅下降。

另外文中也有提到其他技巧,像是不要用find, findall,它們會用XPath-like expression language called ElementPath。
lxml 提供iterchildren/iterdescendents 跟XPath,前兩者相較 ElementPath速度會更快一些;對於複雜的模式,XPath可以經過事先compile,比起每次呼叫元素的xpath() method,經過precompile 的XPath在頻繁取用下會快很多,兩種寫法分別是:
# non-precompile:
xpathContent = "//div[@class='contents']"
content = root.xpath(xpathContent)
# precompile:
xpathContent = etree.XPath("//div[@class='contents']")
content = xpathContent(root)
下面是我實測的結果,在都是完全載入記憶體下,有無precompile 的速度差接近兩倍,不過這也表示我用了iterparse 其實速度是下降的,因為我iterparse 其實是有使用precompile 的:
./parser.py 14.99s user 0.35s system 99% cpu 15.344 total
./parser.py 25.82s user 0.40s system 99% cpu 26.232 total

以上大概是使用lxml 時,一些減少記憶體用量的技巧,記錄一下希望對大家有幫助。

題外話:
在寫這篇的過程中,我發現Shell script 的time 其實是一個相當強大的指令,除了時間之外它還能記錄其他有用的數值,像是 memory usage, I/O, IPC call 等等的資訊。
我的time 是用zsh 下的版本,我也不確定它是哪裡來的,用whereis 找不到,用time --version 也看不到相關資訊,但man time 有相關的說明,總之copy and paste from stack overflow,把我的TIMEFMT 變數設定為:
export TIMEFMT='%J   %U  user %S system %P cpu %*E total'$' \
  avg shared (code):         %X KB'$'\
  avg unshared (data/stack): %D KB'$'\
  total (sum):               %K KB'$'\
  max memory:                %M KB'$'\
  page faults from disk:     %F'$'\
  other page faults:         %R'
其他的變數選項可以在man time 的format string 一節找到,這裡就不細講了,算是寫code 的一個小小收穫吧。

2016年9月21日 星期三

國際觀大補帖

最近某位教授覺得大家竟然不知道希特勒是誰,覺得大家都沒國際觀,台灣未來一定超沒競爭力,大家都只能領22K。
他還提供了一個網站<國際觀檢測網>:「每次點進去都會出現10道題目,例如尼克森、翁山蘇姬是哪國人、做過什麼事,並提供詳解」,連結在此:
http://doc.boyo.org.tw/gp/

老實說我覺得這樣太沒效率了,一次只有10題不小心還會重複,豈不是浪費應考人的時間!?因此我就做了一份增進國際觀大補帖,把網站的題庫全部拉出來,讓大家題目可以一看再看,準備完了再上線考試,就像考駕照一樣。
相信有了這份大補帖,一定能幫大家有效的提升國際觀,讓台灣人才競爭力逆風高灰超英趕美。

概念其實不難,就跟之前做的東西一樣,我是用python2.7 來實作,著眼點是它的lxml 套件,不過python2.7 對utf-8 的支援沒那麼好,script 開始前要把default encoding 設定為utf-8,不然常會印出亂碼。
reload(sys)
sys.setdefaultencoding('utf-8')
首先用urllib2把網頁抓下來,因為這個網頁會cache 要求過的內容,因此要用這樣來開啟網頁,讓HTTP proxy server不要cache 回傳的資料。
request = urllib2.Request(TARGET)
request.add_header("Pragma", "no-cache")
response = urllib2.build_opener().open(request)
再來用lxml把裡面問題和答案的部分給挖出來,填到一個python dictionary 即可,每抓一次都會比對不要抓到重複的東西。
因為爬蟲有時候會遇到網頁錯誤,因此一定要把爬過的東西先存下來,不然跑一跑壞掉了,重跑又要重抓資料,會哭的;幸好在python 上面有pickle 的支援,serialize 資料算相當方便,只要在開始的時候,先用pickle 讀入一個字典檔,沒有的話就回一個空的:
def openPickle():
  try:
    return pickle.load(open("global", "rb"))
  except (EOFError, IOError):
    return {}
然後存檔也很簡單,一行就解決了:
pickle.dump(data, open("global", "wb"))
再來就是一直跑一直跑一直跑,題目就會如洪水般湧進來,老實說挖出來的東西比我想得還要多…好多,wc 一下有1500多行,估計大約就是750 題左右吧。
Well 至於我爬出來的東西,我就無償公開好了,反正這種東西你它的網站一直按F5 也可以抓全,我只是請機器人幫我抓,原始碼跟大補帖放在這裡:
原始碼:https://github.com/yodalee/globalizaion
大補帖:https://github.com/yodalee/globalizaion/blob/master/global
其實我對這個題…沒什麼意見啦,不過我還是不樂見有人真的把這個拿來背(是…應該不會有人這麼蠢吧…應該啦……),畢竟與其死背希特勒是哪國人,還不如去了解他崛起的背景,與其多看大補帖還不如念念「希特勒回來了」。

不過自從我把大補帖公平出來之後,受到各方熱烈的回應,在此僅節錄幾則:
使用者評價一:自從用了國際觀大補帖,頭腦就靈光了很多,考試都考87分呢!
使用者評價二:上學的時候我國際相關的東西都答不出來,自從用國際觀大補帖,成績突飛猛進,現在已經準備要考托福跟日檢N1了。
使用者評價三:原本人生一片黑暗,直到遇到國際觀大補帖,和家人關係變好不說,上周不但交到了女友,老闆還幫我加薪25元呢。
使用者評價四:看國際觀大補帖,平常和朋友聊天信手拈來就是一堆國際知識,朋友們都改用欽佩的眼光看我,覺得我人生從此都不一樣了。
使用者評價五:之前男朋友都看不起我,自從把國際觀大補帖印下來帶在身邊,除了平時閱讀增進國際知識,男朋友欺負我的時候還可以用厚重的大補帖打他的臉,被沉重的歷史感打到一定很痛!
使用者評價六:難得一見的好書,我把每一題都記得滾瓜爛熟,上周考汽車駕照一次就通過了,謝謝你,國際觀大補帖。

Ps. 其實這篇寫程式的時間遠不及寫上面那堆嘴砲文的時間lol

2016年8月2日 星期二

使用Facebook bot on GAE自動監控網頁更新

故事是這樣的,最近我有一位同學在申請日本留學試驗(EJU)的獎學金,最近會在網站上公佈複試的錄取名單,不過他八月又要去美洲大殺兩個星期,想託我幫他看一下複試結果什麼時候出來,出來的話跟他通知一下(說實話就算出來了在美洲是能幹嘛,還不如專心大殺四方)
不過you know,我這個人嘛,懶~~,每天上去看網頁多麻煩…要是哪天忘了看那可是賠不起呀,畢竟強者我同學成績猛高,成績都比平均高了兩個標準差,我去考大概只能考他的零頭出來QQ。
靈機一動,為啥我不找我的好友「葉闆大師」幫忙呢?心情不好的時候跟他聊聊天,他一字一句都是鼓勵的話,十足的激勵人心,檢查網頁這樣的小事能不能拜託他呢?決定就來試試看了。

概念其實很簡單,Google App Engine 本身就有cron 的設定,可以定時觸發一個function,最快每一分鐘觸發一次,到一個月一次都行;還有各種複雜的設定文件:
http://yhhuang1966.blogspot.tw/2013/03/gae-cron-job.html

首先我們先把向facebook 某user 發送訊息的函式獨立出來,再寫一個新的class 處理cron 的狀況,至於receiver 的ID (也就是我的ID) 是多少,那在之前寫bot 的時候,從log 裡面撈出來的:
CONSTANT_RECEIVER = "Fan ID Here"

class FBNotify(webapp2.RequestHandler):
    def get(self):
        logging.info("Fire periodically hello")
        send_fb_message(CONSTANT_RECEIVER, "Periodically Hello")

 app = webapp2.WSGIApplication([
     ('/webhook', FBwebhook),
     ('/fbnotify', FBNotify),
     ('/', MainPage),
 ], debug=True)

有了上面的設定,在project 中加上cron.yaml 先設定每分鐘觸發一次fbnotify get(注意雖然是 1分鐘可是要寫 minutes),時區在以分鐘為單位的狀況就不用設了,詳細請見參考資料:
cron:
- description: check eju website automatically
  url: /fbnotify
  schedule: every 1 minutes
  timezone: Asia/Taipei

用appcfg.py update之後葉闆大師就會熱情的每分鐘定期向你問好:

如果覺得它很煩,只要把cron.yaml 裡面的內容刪到剩下cron: 一行,再appcfg.py update_cron把cron 取消掉就行了。

當然這樣還不行,重點是要監看,EJU 的結果會公佈在這裡:
https://www.koryu.or.jp/taipei-tw/ez3_contents.nsf/14
方法就很正規了,把第一列的資料給拉出來,xpath 的部分先用chrome 的檢查看過,決定xpath 為:
//tr[@valign='top']/td/a[@title]/@title
受限於gae 的關係,我們只能用lxml (其實應該也可以裝 beautifulsoup 不過我有點懶),搭配urllib2把資料拉下來,取出第一列的資料若是和現在的資料不同就給我發送訊息,測試用時,就算沒變也會發一則:
URL = "https://www.koryu.or.jp/taipei-tw/ez3_contents.nsf/14"
FIRST_ROW = u"2016年度第二期日本交流協會獎學金(短期留學生)--合格發表"
res = urlfetch.fetch(self.URL)
s = res.content

root = lxml.html.fromstring(s)
firstTitle = root.xpath("//tr[@valign='top']/td/a[@title]/@title")[0]
isNew = (firstTitle != self.FIRST_ROW)
if isNew:
    send_fb_message(CONSTANT_RECEIVER, "Notification: There is new message")
else:
    send_fb_message(CONSTANT_RECEIVER, "Notification: There is no new message")
把它加到fbnotify 的get 裡面,先用cron 為1 minute 測試,確定真的會送出訊息;也可以直接開瀏覽器,造訪 xxxx.appspot.com/fbnotify 觸發檢查,看看有沒有發訊息給你:



接著就可以把cron 改為30 minutes了,安心去睡覺等葉闆大師的通知了……


才怪!

我還是超緊張的,還是會開網站檢查一下它有沒有更新,要是code 沒寫好怎麼辦,或者葉闆大師下線了呢?這個網站為啥不弄個RSS 之類的就好了Orz。老實說,寫這個花了一兩個小時,其實只要每天早上花 1 秒鐘開網頁看一下就好了,我覺得我這樣根本多此一舉。

參考文件:

GAE cron 相關文件,cron的佈署和 schedule format:
https://cloud.google.com/appengine/docs/python/config/cron
https://cloud.google.com/appengine/docs/python/config/cronref#schedule_format

其他相關文件,python built-in-libraries
https://cloud.google.com/appengine/docs/python/tools/built-in-libraries-27


ps :想靠北一下,GAE 用了兩年覺得網頁愈改愈亂,要找想要的東西都找不到,每每花一堆時間在找一些小東西。

----

按:剛剛在中午左右,已經收到葉闆大師的通知了,實驗成功,謝謝你葉闆大師XD


2016年5月22日 星期日

使用GAE python自幹Facebook Bot

話說最近各種Bot 的傳聞,又看到如<參考文件1>有人弄了一個建在Flask 上面的Facebook Bot,強者我同學qcl 也弄了傳說中的libGirlfriendFramework,就想來弄一個回應產生器,以下是大概的開發流程:

首先先在Facebook 頁面上申請一個粉絲專頁,可以先使用「未發佈專頁」大家就不會搜到這個專頁;另外要申請應用程式,其實Facebook 的說明文件已經寫得滿清楚了,申請的部分照著做就是了
https://developers.facebook.com/docs/messenger-platform/quickstart

進到應用程式主控板,選左列<+新增產品>並選擇<messenger>,使用Facebook messenger platform。
接著在messenger 裡,粉絲專頁選擇自己的粉絲專頁,拿到粉絲專頁的token,記起來下面會用;下方設定webhook-edit event,回呼網址是你伺服器的網址,必須透過https 連線,驗證權杖則隨你喜好設定一段字串。

如果有看下面<參考文件1>,因為它的server 看來是買自己網域建在自家主機上面,所以在https 的部分比較麻煩,要自己用Let's encrypt 去生一個CA出來,因為我們是用GAE,網域直接走Google 的CA,所以這步可以省下來;這步卡了我卡超久,Let's encrypt 跟GAE 不太合,怎麼裝都裝不上去;經強者我同學qcl 大神提醒才發現根本不用理這個,這時上午已經過去了,當下覺得蠢。

第一步就是把webhook 裝上去,首先連接webhook 的route:
app = webapp2.WSGIApplication([
  ('/webhook', FBwebhook),
], debug=True)

並實作 get handler,所謂verificaion token就是上面寫驗證權杖,寫到這裡可以如參考資料1用Postman去檢驗是否有問題:
class FBwebhook(webapp2.RequestHandler):
  def get(self):
    verification_code = "Verification Token Here"
    verify_token = self.request.get('hub.verify_token')
    verify_challenge = self.request.get('hub.challenge')
    if verification_code == verify_token:
      self.response.write(verify_challenge)

實作完成後連接webhook 的地方應該就能通過了,四個選項依自己的需要選擇:
  • messages:接收訊息的callback,最基本都有這個,這個都沒勾你連接messenger 幹嘛XD
  • message_deliveries:傳送訊息的callback
  • messaging_optins:連接Send-to-Messenger plugin
  • messaging_postbacks:連接postback button的事件
上面四個我只勾了messages 可是也可以正常接受、發送訊息,其他三個光看說明看不懂是要幹嘛,有人知道的話歡迎解惑。

連接了webhook 就能向Facebook 註冊你的應用程式了,依照getting started 的頁面指示發送要求,token請換成你粉絲專頁的token:
curl -ik -X POST "https://graph.facebook.com/v2.6/me/subscribed_apps?access_token=<token>

理應會收到
{“success”: true}
現在可以真的在facebook粉絲頁丟訊息了,它會向webhook設定的回呼網址發送Post,getting started 的頁面有介紹傳來的json 格式,可在webhook中建post handler然後 print(self.request.body),就能從google cloud platform 的紀錄中撈到:

以下是撈到的內容:
{
"object":"page",
"entry":[
  {
  "id":"page id",
  "time":1463907808653,
  "messaging":[
    {
    "sender":{"id":"sender id"},
    "recipient":{"id":"recipient id"},
    "timestamp":1463907808591,
    "message":{
      "mid":"mid.1463907808584:503df60b4ad4529365",
      "seq":7,
      "text":"XDDD"}
    }
  ]}
]}

處理訊息用python json 就行了:
message_entry = json.loads(self.request.body)['entry']
for entry in message_entry:
    messagings = entry['messaging']
    for message in messagings:
        sender = message['sender']['id']
        if message.get('message'):
            text = message['message']['text']
            print(u"{} says {}".format(sender, text))

到這裡應該可以在你的google cloud platform 紀錄中找到你發送訊息的內容,下一步就是回訊息,只要向粉絲專頁的網址,搭配token發送post 訊息即可,很容易…個頭:
def send_fb_message(self, to, message):
  post_url = "https://graph.facebook.com/v2.6/me/messages?access_token={token}"
    .format(token=FBtoken)
  response_message = json.dumps(
    {"recipient": {"id": to},
     "message": {"text": message}})
  result = urlfetch.fetch(
    url=post_url,
    headers={"Content-Type": "application/json"},
    payload=response_message,
    method=urlfetch.POST)

  print("[{}] reply to {}: {}".format(result, to.encode('utf-8'), message))

要注意的一個是,因為google appengin python 一直停留在python2.7 ,所以unicode handler不若python3 這麼完整,上面很多encode('utf-8')都是不斷錯誤後加上去的,也曾經發送訊息「太強啦」結果GAE 整個當掉,因為這三個字一直引發handler crash,handler沒有回音導致Facebook又發送一次「太強啦」過來,然後就無限loop 了,這時要用上面的curl 命令,把你註冊的程式refresh 一下,讓Facebook 不要再發訊息過來。

為了這堆unicode 又花掉一個下午,寫這個簡單的Bot 一天就用掉了…寫到這裡我突然想到那篇傳奇文章「軟體工程師的鄙視鏈」裡面那句:
用 Python 3 的工程師鄙視還在用 Python 2 的工程師,用 Python 2 的工程師鄙視遇到 UnicodeEncodeError 的工程師。
完了我要被鄙視了QAQ

總之最後結果像這樣:

我曾經很認真地想過這個功能到底有什麼用,後來我想到,例如中央氣象局的粉絲頁就能加入註冊跟發送訊息的功能,我們可以發送訊息給該粉絲頁:「註冊/台北」或「註冊/高雄」
後端的handler 在接受這樣的訊息時,將發送者的ID跟地點加入後端的資料庫中,如地震通報或是每日當地的氣象預報就能自動發訊息給每位註冊的使用者。

不過目前沒看到非常印象深刻的應用就是了。

Project 放在這裡,星星就…隨便啦,其實沒有很需要=_=
https://github.com/yodalee/IPban-bot

順帶一提,強者我同學qcl 也有一個類似的project,現在亟需開發者貢獻,據說已經辦了兩次全球開發者大會,各種生猛:
https://github.com/libGF/libGirlfriendFramework

參考文件:
1.使用Flask開發Facebook Message Bot:
http://enginebai.logdown.com/posts/733000/python-facebook-bot
2. Facebook message platform 文件:
https://developers.facebook.com/docs/messenger-platform

2016年5月4日 星期三

Python 參數產生unittest

最近在寫傳說中 jserv 大神的amacc,一個奉行「極致的簡」的C compiler
參與專案的第一步當然是先看issues,那時剛好看到這個:
https://github.com/jserv/amacc/issues/13
看起來不算太難,改一下code 執行流程就好了

不過首先,這個project 有點難以測試,的確make check 會嘗試編譯所有tests/*.c 檔,並且用jit 和產生elf 的方式去執行,可是卻不會通知結果是不是正確的,nested for loop 的結果也會和其他檔案混在一起,直接下指令去測又很麻煩(要用qemu,指令好長…)

覺得測試這麼麻煩,連帶著改issue 也好麻煩的感覺,因此決定不想改了先來幫這個project 加上一些便於測試的功能

想到test 就想到python unittest,設計概念是:利用python subprocess 去呼叫amacc跟arm-linux-gnueabihf-gcc 分別編譯執行檔,執行後,直接比較兩者的output,看結果是否相同,如此就能驗證amacc 的行為(這有個問題是gcc 未必遵照C standard,真正正確的答案應該要看C standard 才對,不過我們假定大多數狀況gcc會遵照C standard)

這裡遇到一個問題,在tests 裡面有許多的c files,因為對每個檔案要做的事情其實是一樣的,自己寫只會變成複製貼上,還可能貼錯內容;寫一個test 去跑所有檔案也不行,這樣等於是所有測試混在一起,test 沒過可能是任一個檔案有錯,根本看不出是誰錯了。

所幸這個解法也不困難,簡單google 就找到了:

概念是,本來的module 變成一個容器,裡面要自己寫的function 就不寫了:
class TestAmacc(unittest.TestCase):
  pass

另外寫一個共同的test generator,會傳回測試的function,我這個test function 裡面就是本來要對檔案做的事:amacc編譯、gcc 編譯、執行、比較結果,參數f為要執行的檔名:
def testGenerator(f):
  def test(self):
  # test function here
return test

最後是對每個檔案去呼叫這個generator,利用setattr 的方式,把這個function 督進先前宣告的容器當中,python 的彈性由此可見:
for dirpath, _, filenames in os.walk("tests"):
  for f in filter(lambda name: namePattern in name, filenames):
    testfile = os.path.abspath(os.path.join(dirpath, f))
    test_func = testGenerator(testfile)
    setattr(TestAmacc, 'test_%s' % (os.path.splitext(f)[0]), test_func)
unittest.main(argv=[sys.argv[0]])

如此就能自動產生test case 了,如上所示,還可以幫檔名加上filter,用參數來指定要跑什麼測試,極度方便;這裡遇到一點卡關是,unittest 預設會吃主程式的argv作為要跑的test module 名稱,argv 加上參數的話會讓unittest 炸開,必須要避免unittest.main 吃到不是給它的argv 參數以,免它找不到測試module 直接回報出錯。

2016年2月28日 星期日

無聊至極,分析不同鍵盤的效率

可能是最近無聊過頭,想到一個有趣的分析題目

稍微有點了解的人就知道,現在大家最常用的qwerty鍵盤當初的設計,是因為早期打字機打太快會卡住,這個排法就是為了讓大家打字不要這麼快,其「主要」的對手:Dvorak 鍵盤的wiki 條目條列了下面的幾個設計原理:https://en.wikipedia.org/wiki/Dvorak_Simplified_Keyboard
Many common letter combinations require awkward finger motions.
Many common letter combinations require a finger to jump over the home row.
Many common letter combinations are typed with one hand. (e.g. was, were)
Most typing is done with the left hand, which for most people is not the dominant hand.
About 16% of typing is done on the lower row, 52% on the top row and only 32% on the home row.

那麼我們是不是能數據化這些設計概念呢?

試找了一下English frequency ,找到這個網站
http://norvig.com/mayzner.html
它裡面有詳述它的方式,從google book raw data 中,把裡面的1-gram 全爬過,建出一張book 的單字表,大小約1.5 MB:
http://norvig.com/google-books-common-words.txt
從這裡我們可以得到相當完整的 1-gram count 跟bigram count

要有個數據化的比較,我們要提出我們的比較基礎,什麼樣的狀況會有速度的差異?例如我們可以假設,手指放在中行,不用上下移動可以打得比較快,所以常用字母放在中行的鍵盤會打得比較快:

首先我們要先算一下1-gram的頻率跟 bigram 的頻率,既然檔案都建好了(老實說它去parse 23 GB 的檔案才是大工程,我這都是小case 而已),用python 可以輕鬆 parse(告訴你有多簡單,我打這篇文章的時間還比我打code 的時間長):
上排:qwerty 0.516, dvorak 0.218
中排:qwerty 0.325, dvorak 0.704
下排:qwerty 0.160, dvorak 0.079
這個統計和上面說的About 16% of typing is done on the lower row, 52% on the top row and only 32% on the home row. 相符,Dvorak 鍵盤手不用動就能打完 70 % 的字,相對qwerty 只能打出 32%

再來是左右手,這個分別就比較沒那麼明顯了,大約都是6:4,而且左手雖然是非慣用手,打起字來似乎也不會慢上多少,不過假設確實有此事好了,一樣dvorak 勝:
qwerty 左手0.587, 右手0.433
dvorak 左手0.413, 右手0.567

影響更大可能是字跟字之間的移動,例如上面舉例的was, were,都是左手末指,打起來就會卡卡的,這個就需要bi-gram了,我們可以算出,在26*26=676 個bigram 中,對應到出現在qwerty鍵盤跟dvorak 鍵盤,是在左右手間打的頻率是多少:
qwerty: 0.529
dvorak: 0.712

另外像require a finger to jump over the home row,就算算bigram在兩個鍵盤,需要跳過home row 打字的狀況(好奇這樣真的會比較慢嗎=w=):
qwerty: 0.211
dvorak: 0.017
dvorak 頻率好低,qwerty 打字有1/5 的頻率需要跳過home row,一方面dvorak 70%的字母都在中排,要換到上下排兩個的頻率自然小得多。

當然這裡提的都是一些簡單的模型,例如上面第一點說的:awkward finger motion,基本上就是許焉不詳…,要先決定哪些手指移動是awkward (是說awkward 這個字在qwerty 鍵盤裡有夠難打的...),再用數據下去跑,我們可以簡化一點,像是:連續不同字母用同隻手指打就算awkward finger motion,當然這點跟每個人的打字習慣有關,大概就好:
qwerty: 0.069
dvorak: 0.025
好了反正就是dvorak 勝就對了

上面提的淨是些簡單的模型,其實提個適合的模型,大家都可以用python去建n-gram,比較兩者的差異
不過話又說回來,儘管dvorak 鍵盤可能真的比較優秀,連世界打字最快的記錄據傳都是dvorak 創的,我活到現在,看過用dvorak 鍵盤的也就只有傳說中的謝安大神而已,ptt 的programming 版上有句話說得好:「技術標準就是這麼一回事,不需要最好,只要最早且堪用」

2015年11月9日 星期一

使用python 爬蟲與pdf 函式庫產生網頁pdf 檔

之前聽傳說中的jserv大神演講,發現一個有趣的東西:
http://c.learncodethehardway.org/book/
簡而言之就是…呃…自虐…應該說用常人不會走的路來學C

不過呢這東西目前來說只有html file,如果要印成一本可以看的文件,畢竟還是pdf檔比較方便,該怎麼辦呢?這時候用python 就對了。
概念很簡單,用一隻爬蟲爬過網頁,然後轉成pdf檔:
爬蟲的部分我是選用強者我同學,現在在Google Taipei大殺四方的AZ大大所寫的Creepy (https://github.com/Aitjcize/creepy),雖然好像沒在維護,不過我們要爬的頁數很少,不需要太複雜的爬蟲程式。
Html轉pdf選用pdfkit (https://pypi.python.org/pypi/pdfkit),這需要ruby的wkhtmltopdf,可以用gem install wkhtmltopdf安裝;再用pypdf2 (https://pythonhosted.org/PyPDF2/)將文件全合併起來,兩個程式寫起來40行就了結了,輕鬆寫意,內容如下:

爬網頁:
from creepy import Crawler
import pdfkit

class C_Hard_Way_Crawler(Crawler):
  def process_document(self, doc):
    if doc.status == 200:
      filename = doc.url.split('/')[-1].replace('html', 'pdf')
      print("%d %s" % (doc.status, filename))
      pdfkit.from_string(doc.text, filename)
    else:
      pass

crawler = C_Hard_Way_Crawler()
crawler.set_follow_mode(Crawler.F_SAME_HOST)
crawler.crawl('http://c.learncodethehardway.org/book/')
合併檔案:
from PyPDF2 import PdfFileMerger

names = ['index', 'preface', 'introduction']
for i in range(53):
  names.append("ex%d" % (i))

merger = PdfFileMerger()
for name in names:
  f = open("%s.pdf" % (name), 'r')
  merger.append(f, name, None, False)
  f.close()

f = open("Learn_C_the_hard_way.pdf", 'w')
merger.write(f)
f.close()

我承認我code 沒寫得很好,各種可能噴射的點,不過至少會動啦,信Python 教得永生;轉出來的pdf檔超醜的,感覺跟之前一些在網路上找的pdf風格有點像,每頁的標頭有些重複的內容應該要去掉,連結也全壞了,就…有空檢討並改進XD
pdf檔放在dropbox(過一段時間應該會失效):
https://dl.dropboxusercontent.com/u/3192346/Learn_C_the_hard_way.pdf

2014年12月25日 星期四

用python讀入agilent (keysight) binary file

故事是這樣子的,最近拿到一些透過Agilent示波器(好啦你喜歡叫他Keysight也可以)讀到的資料,要對裡面的數字做分析,由於資料極大時他們會用自家的binary格式存檔案,要讀出資料分析就比較麻煩。
他們自家網站是有提供……程式來分析,可惜是用matlab寫的…
What The F.. Emmm, Ahhh, Ahhh, 沒事
總之我看到這個東西就不爽了,俗話說人活著好好的為什麼要用matlab。恁北想用python沒有怎麼辦,只好自幹啦。

其實整體來說滿簡單的,只是把matlab code 用python 寫一篇,python又比matlab 好寫很多。
比較值得提的只有一個,分析binary就不能不用python的struct,相關的內容可見:
http://yodalee.blogspot.tw/2014/03/python-structdex-file-parser.html

這次我再加上用namedtuple來處理,整體會變得很乾淨;例如它一個波型的header格式是這樣:
int32 headerSize
int16 bufferType
int16 bytesPerPoint
int32 bufferSize

那我就先定義好namedtuple跟struct的format string:
from collections import namedtuple
bufHeaderfmt = “ihhi”
bufHeaderSiz = struct.calcsize(bufHeaderfmt)
bufHeader = namedtuple(“bufHeader”, "headerSize bufferType bytesPerPoint bufferSize")

再來我們讀入檔案,直接寫到tuple裡,就可以用名字直接存取值,例如我們要跳過header:
bufHdr = bufHeader._make(struct.unpack(bufHeaderFmt, fd.read(bufHeaderSiz)))
fd.seek(bufHdr.bufferSize, 1)

是不是超簡潔的?一個晚上就寫完了=w=

人生苦短,請用python。

原matlab 網址
http://www.keysight.com/main/editorial.jspx?cc=TW&lc=cht&ckey=1185953&nid=-11143.0.00&id=1185953

原始碼在此,不過我覺得是沒什麼人會用啦orz
https://github.com/yodalee/agilentBin

2014年12月9日 星期二

Translate Qt translation file (.ts file) using Python and Google Translate

Pyliguist

A python script translates Qt ts file by google translate

Recently I'm working on project Qucs. This project only has a little group of developers.

The program got about 3000 entries need to be translated, which, however, no one wants to translate them. To translate them manually is a very hard, and time-consuming work. It makes me think of using Python to translate these text automatically.

Luckily, there do have an automatic tool: Python Goslate package.
It's very simple to use, just create a goslate object. Then you can call function translate to translate the text, like this:

>>>go="goslate.Goslate()
>>>go.translate(“worship”, “zh-tw”)
崇拜

I write a little script “PyLinguist” in Python, which use Python “xml” to parse Qt translation file. Then use Python package “Goslate” to translate the text.

It takes 30 seconds to translate 200 entries in test file, which is much faster than translate manually. Though there is some problem. For example it translate “Help” into “Save me” in Chinese, but generally it works.

The source code is here:
www.github.com/yodalee/PyLinguist

2014年12月1日 星期一

使用python 與Google Translate進行程式翻譯

最近Qucs Project有個德國佬加入,這個……一加入就做了不少苦力的工作,像換掉一些Qt3才支援的function,換個Qt4相對應的名字,他說他是用Xcode的取代功能寫的,老實說這個東西不是用sed就可以解決嗎(._.),不過算了,有人幫忙總是好事。

他後來又貢獻了一個PR,內容是把整個程式的德文翻譯加了一千多個翻譯,根本巨量苦力;同時他又開了一個issue,想要把德文的翻譯給補完,我覺得這樣一個一個翻譯有點太累了,雖然Qt 有linguist幫忙,可是其實還是很累,遇到沒翻過的,還是要自行輸入。

當下靈機一動,想到之前看過有人用Google Translate來自動進行Gnu Po檔的繁簡轉換,那一樣我能不能用Google Translate進行Qt 的翻譯呢?

為了這個我寫了一個PyLinguist的script,輔助工具選用的是Python的package goslate:
使用方法很簡單,產生一個goslate的物件後,叫個function 即可:
go=goslate.Goslate()
go.translate("worship", "zh_tw")
'崇拜'

同樣的,qt的翻譯檔就是一個xml 檔,python要對付xml也是小菜一碟,用xml.etree.Element即可,每個要翻譯的文字會以這樣的格式記錄:
<message>
  <source>Hu&amp;e:</source>
  <translation type="unfinished"></translation>
</message>
Source是原始文字,Translation則是翻譯文,如果還沒翻譯,就會在translation tag加上type=”unfinished”的屬性。

整體程式流程大概是這樣:

讀檔,把整個xml 讀到一個xml tree 物件裡:
self.tree = ET.parse(XXX.ts)
root = self.tree.getroot()

開始翻譯,這裡我設定self.maplist這個dict物件,記錄所有翻過的內容,這樣只要以後再次出現就取用之前的結果,省下網路回應的時間;之所以要在translate的外面加上try, except,是我發現goslate在翻譯OK這個字時,不知為何會出現錯誤,為了讓程式跑下去只好出此下策;如果找到翻譯文,就替代掉之前的文字並拿掉unfinished的屬性。
for msg in root.iter('message'):
  source = msg.find('source').text
  isTranslated = not (msg.find('translation').attrib.get('type') == "unfinished")
  if not isTranslated:
    if source in self.maplist:
      msg.find('translation').text = self.maplist[source]
      del msg.find('translation').attrib['type']
    else:
      try:
        text = self.gs.translate(source, target_lang)
        msg.find('translation').text = text
        self.maplist[source] = text
        del msg.find('translation').attrib['type']
      except Exception:
        pass

最後把程式寫出去即可,也是一行搞定:

self.tree.write(filename, xml_declaration=True, encoding="UTF-8", method="html")

結果:

目前除了輸出時如xml 的DOCTYPE宣告會消失,大致上的功能是可接受的,翻譯800行約100到200個翻譯文的檔案,大約30秒就翻完了,這之中可能還有一些是google translate回應的時間,這已經比人工還要快了不少。

結論:

感恩python,讚嘆python
老話一句:working hard, after you know you are working smart,翻譯這種事多無聊,丟給google做就好啦。

原始碼:

本程式(毫無反應,其實就只是個腳本XDD)為自由軟體,原始碼公布在:
https://github.com/yodalee/PyLinguist

參考資料:

1. Goslate:
http://pythonhosted.org/goslate/
2. python xml
https://docs.python.org/2/library/xml.etree.elementtree.html

2014年11月4日 星期二

用python 產生未引入檔的報表

故事是這樣子的,最近我無聊的時候玩玩的專案
qucs 理想上這個project是要達成類似ADS的模擬軟體,很不幸的在功能上遠遠不足;project 開始的年代是2003年左右,當初應該是qt3 寫的,因為qt 支援不足那時候他們還自己寫qt 物件vtabbar, vtabbeddockwidget什麼的。
現在還有一堆qt3support的東西沒有清除乾淨,這整團又黏得死死得要一口氣清光,原作者去年有設法把它拿掉,弄了50多個提交之後沒什麼結果,物件繼承又弄得一團糟,十年累積下來的修改可以氣死人。

從一開始參與的時候,我就覺得這個project 很怪,怪在哪呢?無論是把Qt3拿掉升去Qt4,幫它加上新功能等等,不管你怎麼改,改了多少Qt的object進去,它編譯通常都會過,就算你沒include,它還是過了……
後來我才檢視到,在它最上層,位階僅次於main.h的qucs.h(光看名字就知道這有多核心XDD)裡,竟然加上了一行
#include <QtGui>
這…這行也真是霸氣外露,這根本是幫project加了個金剛不壞之身,之後所有的header files應該把qt object 的include都投去太平洋才是;這實在不是好習慣,QtGui 包含了太多的標頭定義,一方面會影響到編譯時間(下面連結有人說40%),同時也讓你抓不到每個檔案到底需要哪些標頭。

後來我用grep 下去掃一下,總共有兩個重要標頭檔被加上QtGui include,五個子資料夾d 重要標頭檔被加上這行,另外還有113個原始碼檔案。
如果要手動慢慢移除,大概會花上不少時間;也可以用sed 一個氣全移光,再來慢慢修,不管怎麼樣,移掉它們一定會產生一堆沒include標頭檔產生的 undefined error,要慢慢把該include 的檔案加上去。
老話一句:「working hard, after you know you are working smart」

為了這個問題,寫一個python code來解決。
問題很簡單:一但移除include QtGui,編譯時會產生一堆undefined error,我們要把該引入的標頭檔加上去,我的策略很簡單,用一個python script去剖析編譯的錯誤訊息,找去哪個檔案缺什麼定義,自動寫入暫存檔裡,產生該加上的include code即可。

呼叫make的地方就用python 的subprocess 模組,用make -k儘量產生各種錯誤:
from subprocess import Popen, PIPE
cmd = ['make', '-k', '-j8']
p = Popen(cmd, stdout=PIPE, stderr=PIPE)
stdout, stderr = p.communicate()
errormsg = str(stderr)
這樣我們就取到錯誤訊息了,stdout其實可以不理它。

這個project用的是clang,它的message 形式是這樣:
檔名:行數:字元數: error: unknown type name '物件名'
該行的原始碼
可能的錯誤訊息有unknown type name跟implicit instantiation of undefined template。

要剖析也很簡單,連regular expression都不用,用split直接切下來就是了,最後我們用字典建立檔案跟缺少的物件列表:
files = {} filename = line.split(':')[0]
classname = line.split(“'”)[1]
if filename in files:
    if classname not in files[filename]:
        files[filename].append(classname)
    else:
        files[filename] = []
        files[filename].append(classname)
這樣我們有報表了,再來就是產生一下引入的原始碼,如果是標頭檔,會產生class forward declaration跟include引入,原始碼檔就比較簡單,全部產生引入即可,如此一來就能輕鬆產生引入的程式碼。最後我們還能用subprocess幫我們打開vim,把有錯的檔案跟我們寫入的報表一起打開,就能輕鬆修正所有的錯誤。

結果:
我花了大約30分鐘的時間,把120個檔案的QtGui 引入全部刪完了,單核心編譯時間從原本的344秒加速到245秒,真的大約提速29 % OAO

相關資料:
1. Qucs 專案:
https://github.com/Qucs/qucs
2. QtGui相關討論:
http://qt-project.org/forums/viewthread/18766

2014年3月17日 星期一

使用python struct實作Dex file parser

最近因為學校作業的關係,開始碰一些android的相關內容;有一個作業要我們寫一個程式去改android dex file的opCode,不過我實力不足,最後用smali/baksmali+shell來實作,一整個就不是熟練的程式人該作的事O_O。
不過,為了補一下實力不足,還是用python 寫了一個Dex file parser:

因為Dex file已經包成binary的形式,要去parse其中的內容,最方便的套件就是python struct了,在這裡以Dex為例,來介紹python struct的使用:

要使用python struct,首先要寫出format string,struct 會依照format string對資料進行處理。
基本的格式是“nX”,其中n為重複數字,X為格式化代碼,例如I代表unsigned int_32。 前面還有endian的符號,這部分請自行查閱參考資料。
有了format string就可以呼叫struct的function: pack, unpack,它們會照format string,把資料寫到binary或從binary讀成一個tuple。

 例如:我們可以看到dex 35的header為:
typedefstructDexHeader {
u1 magic[8]; /*includes version number */
u4 checksum; /*adler32 checksum */
u1 signature[kSHA1DigestLen]; /*SHA-1 hash */
u4 fileSize; /*length of entire file */
u4 headerSize; /*offset to start of next section */
u4 endianTag;
u4 linkSize;
u4 linkOff;
u4 mapOff;
u4 stringIdsSize;
u4 stringIdsOff;
u4 typeIdsSize;
u4 typeIdsOff;
u4 protoIdsSize;
u4 protoIdsOff;
u4 fieldIdsSize;
u4 fieldIdsOff;
u4 methodIdsSize;
u4 methodIdsOff;
u4 classDefsSize;
u4 classDefsOff;
u4 dataSize;
u4 dataOff;
}DexHeader;

對這個我們可以寫出v35 format string為:"8sI20s20I",就這麼簡單。 接著我們可以呼叫unpack來取得header的內容。
infile = self.open(“yay.dex”, “rb”)
header = struct.unpack(self.v35fmt, infile.read(struct.calcsize(self.v35fmt)))
比較麻煩的一點是,unpack的資料長度必須和format string會處理到的長度一樣,這裡struct提供了calcsize來處理這個問題,它會回傳format string代表的長度。
print(header) (b'dex\n035\x00', 3615126987, b'A\x89\xd9Y\xd8mm\xe4\xfe\x9d8\x0c\xc25\xbc\xcc\x9b\x86\xbd)', 912, 112, 305419896, 0, 0, 752, 16, 112, 8, 176, 4, 208, 1, 256, 5, 264, 1, 304, 576, 336)

可以看見資料已經寫入tuple中了,之後再進行轉出即可。

2013年12月25日 星期三

ADS_origin_converter v2

今天下午發佈ADS origin converter v2

新增下列功能:
一、原本是進入一個prompt讓使用者輸入檔名,使用者試用的經驗表示這實在是太弱了,在windows下最好的使用方式:把要轉換的檔案拖到exe檔上面。
測試之後發現,在windows上把檔案拖到exe檔上面,等同將被拖的檔案路徑當成argv參數傳入,因此程式改為輸入參數為要修改的檔名即可。

二、支援多變數檔案:
之前的版本只支援單變數的狀況,這次則加入多變數的狀況,ADS記錄多變數的狀況如下:
sweepvar1 ... sweepvar_n-1 sweepvarn ... data
var1_1 ... varn-1_1 varn_1 ... data_1_1
var1_1 ... varn-1_1 varn_2 ... data_1_2
var1_1 ... varn-1_1 varn_3 ... data_1_3
...
var1_1 ... varn-1_1 varn_m ... data_1_m

sweepvar1 ... sweepvar_n-1 sweepvarn ... data
var1_1 ... varn-1_2 varn_1 ... data_2_1
var1_1 ... varn-1_2 varn_2 ... data_2_2
var1_1 ... varn-1_2 varn_3 ... data_2_3
...
var1_1 ... varn-1_2 varn_m ... data_2_m
新版的會以前幾個變數產生tital name,例如在上述狀況,最主要的index是sweepvarn,不斷重複的則是data,上述的狀況會產生為:
sweepvarn tital1 tital2 …
varn_1 data_1_1 data_2_1 …
varn_2 data_1_2 data_2_2 …
varn_3 data_1_3 data_2_3 …
...
varn_m data_1_m data_2_m ...

產生的第一個tital會是:
sweepvarn 之後則是
sweepvar1=var1_1,sweepvar2=var2_1, …sweepvar_n-1=varn-1_1
好像不好看懂,總之就是tital會是第二-n個變數的數值。

目前有一個已知難防的bug是,顯示的變數名稱不能有空白在裡面,因為斷詞是以空白為基準(好像也沒有更好的斷詞方試),有空白的變數名稱會造成tital產生錯誤,目前無解。只能要使用者不用掃有空白的變數名稱,例如:
I_Proble[0, ::]

安裝方式: 在下方github頁面,選”Download As zip”,解壓後直接將檔案拖到ADSToOrigin.exe上面即可。

--

本程式公開所有程式源碼,請見github,請眾位大神鞭小力一點>_<
https://github.com/lc85301/ADSToOrigin

2013年10月8日 星期二

ADS Export to Origin converter

最近在準備一些學校報告用的投影片,在學長主持的小咪報告之後:
學長:「你這幾頁的圖,如果之後要放論文的話,就乾脆用Origin重畫」
好吧學長都這樣說了,就來畫畫Origin的圖wwww
不過秉持著用開源軟體的精神,還是找了一下,結果就在[1]的作敏學長的blog裡面找到qtiplot這個開源繪圖軟體,跟Origin的功能幾乎差不多。

1. 問題簡述:

這裡遇到一個有點機車的問題:
平常我們在ADS這套軟體畫好圖之後,如果用ADS再export成txt file,就會變成類似下面的格式:
 freq S(1,1)
1e9 -1E1
2e9 -1E1
3e9 -1E1
4e9 -1E1

freq S(2,1)
1e9 1E1
2e9 1E1
3e9 1E1
4e9 1E1
註:隨便選個數字表示一下。 但如果要用Origin匯入文字檔的話,理當是這個格式比較好:
freq S(1,1) S(2,1)
1e9 -1E1 1E1
2e9 -1E1 1E1
3e9 -1E1 1E1
4e9 -1E1 1E1
俗話說得好:科技始終始於惰性,與其用Excel打開檔案然後一欄一欄複製貼上,不如寫個script來解決 =b,另一方面還是要再次強調我的哲學:「work hard, after you know you are working smart」。

2. 解決方案:

最後還是用我們的老朋友python,實際譔寫時間約30分,超快der;會慢主要是在查zip的寫法;實際內容大概也只有zip比較有趣。
首先先把資料一行一行讀進來,寫入list裡面。讀檔結束就會有一堆list,分別存著freq裡所有的資料,然後是S(1,1), S(2,1),我在讀檔時就先把這些list存到一個大list裡。
假設我的大list為data,data 的長相大概像這樣:
data = [[S(1,1)],[S(2,1),....]]
於是我們可以先展開data list為所有list,然後透過python 強大的zip函式,直接iterate所有的list。
For line in zip(*data):
outfile.write(“%s\n” %(“\t”.join(line)))
很快速的就完成檔案格式化寫出的工作。

3. windows版本:

在改windows版本的部分,則是把本來要吃參數的script改成吃使用者輸入的內容。
照著[3]的幫助,首先先安裝python和py2exe,利用py2exe把python script轉成exe檔。
先寫一個setup.py:
from distutils.core import setup
import py2exe

setup(console=['ADSToOrigin.py'])
然後在cmd用
python setup.py py2exe
就會自動產生dist這個資料夾,裡面會包括ADSToOrigin.exe,打開就會開console,像linux一樣正常使用。

 4. 原始碼公開: 這個script已經公開在我的github上:
https://github.com/lc85301/ADSToOrigin
歡迎大家給feedback或來pull request。

 5. 參考資料:
1. http://zuomin.blogspot.tw/2010/05/linux-origin.html
作敏學長:qtiplot介紹。
2. ptt python 版3115篇:python list iterate介紹。
3. http://logix4u.net/component/content/article/27-tutorials/44-how-to-create-windows-executable-exe-from-python-script
py2exe tutorial
4. python official site: http://www.python.org/
5. py2exe official site: http://www.py2exe.org/

2013年9月24日 星期二

寫了一個管理帳號的script

差不多去年這個時候,小弟魯蛇剛接任所上的linux工作站網路管理員。
本來以為是個輕鬆的職位,畢竟先代某陳姓大網管超~級~強~,工作站維護得這麼好,佈線設備也都沒什麼問題,我們應該也只要做點基本維護就好,結果工作其實還頗多(OAO)。
要幫所上的人申請新帳號;幾台伺服器還裝著mandriva 2009,久未更新,很多套件可能都過期了,需要用主流的CentOS或Debian來取代;有的工作站連yum都沒有,只能抓rpm,那時候試著要裝yum,結果遇到瘋狂的相依關係,最後只好放棄;最後還有工作用的軟體跟license server需要維護。

最近為了減輕一些工作,就寫了一個自動加入帳號的script,理論上用bash script應該就做得到,不過考量到其中有許多文字處理,數字比對的部分,最後還是用python的譔寫,雖然說nis主機也是debian 5的老主機,必須用python2.5來譔寫有一點troll,不過還是比用shell快一點。

ps:其實linux工作站使用人數比較少,理論上用vim手動加搞不好比較快,不過當作python練習XDD。

一、帳號記錄文件:

伺服器使用的帳號記錄是nis,內容跟/etc/passwd沒什麼兩樣,類似這樣: account:passwd:uid:gid:comment:homedirectory:shell
這沒什麼好講的,大部分的內容都是預設,比較不一樣的是我們uid, gid設定:為了管理方便,我們的gid是以1k為單位分給一位教授,對應可使用的1000個uid,例如某葉教授(咦)的gid為10000,那uid就從10000-10999,下一位教授就從gid, uid為11000開始。
註:這樣每個教授可以收1000位學生,就算每學期收個20個,也要收50年才行,應該頗夠用吧XD

二、程式規劃:

規畫程式的功能如下。
功能一,加入使用者:
1. 詢問使用者帳號名稱(account)
2. 列出目前可用的gid列表,要求管理者選擇。
3. 查詢目前表列的uid,取得下一個uid值。
4. 請管理者輸入comment。
5. 列出homedirectory資料夾選項。
6. 詢問使用者密碼。
功能二,刪除使用者:
這個比較簡單,把account comment掉就是了。
第二部分,實際操作:
1. 備份檔案,複製一份檔案,儲存為原檔名.日期。
2. 將要加入的內容寫入passwd檔中。
3. 呼叫ypinit -m更新資料庫。
4. 呼叫ypasswd修改密碼檔,這部分用pexpect達成。
5. 產生一份需要建立新資料夾的資料夾位置,到nfs使用。

三、實作:

上述功能看來有點多,其實寫起來滿快的,幾個小時吧。主要是python功能過於OP,大部分慢下來的地方都是我腦殘忘記該怎麼寫,或是為了使用python 2.5以致需要去查語法。
程式大部分是使用python 的list來硬幹,儲存需要寫入的字串,將需要增加的或刪除的資料新增到list之中。

大概沒什麼好講的,唯一值得一提的就是發現python 整合了expect的功能:pexpect,原本呼叫yppasswd的部分想要用expect來寫,但發現用pexpect比較方便,也可以把改密碼的工作交給python去執行,比分出一個expect script還要方便。
跟上一篇的expect講的差不多,pexpect同樣支援spawn, expect, send等基本語法
例如程式中需要設定新加入使用者的密碼:
for key,val in passwddict.iteritems():
    print("change passwd of user %s" % key)
    rootpass = “rootpassword”
    child = pexpect.spawn("yppasswd %s" % key)
    child.expect('password:')
    child.sendline(rootpass)
    child.expect('password:')
    child.sendline(val)
    child.expect('password:')
    child.sendline(val)
    child.expect(pexpect.EOF, timeout=None)
從存好的dictionary裡面取出一對帳號跟密碼,然後去設定passwd,同樣的缺點也是root密碼會曝光,權限要小心設。

PS:剛剛發現暑假過太頹廢,從八月中到現在都沒寫新文,看到同學們都在當助教惹,自己也要努力點才行。

2013年7月8日 星期一

使用python執行EM模擬及寄信通知

runem這個小程式,主要是因為,通常我RF的電磁模擬要花上很多的時間,丟上工作站的話都要跑很久,如果是在windows下透過putty連結工作站,要是putty突然當掉,導致跑到一半的模擬中止掉就頭大了。

面對這個狀況有幾個解決方案,例如使用專面負責離線工作的程式,像是screen;但因為幾台工作站的作業系統太過老舊,上面甚至連screen都沒有;另一個解決方案是用atd,也就是linux內建的服務,在某個時間進行某個指令,這個解決方式很好,只是at 的語法比較麻煩,強迫每個使用者去記也沒什麼道理,身為網管要提供使用者方便,決定把at包成一個shell,使用者只要使用這個指令即可。

--

其實這個只要用shell script寫幾行即可,不過考量到一些特別的功能,還是用python來寫。 核心功能其實就一個,透過python 的subprocess把em 的指令透過atd送進去(ref 3):
cmd = "echo 'em -v {0}'".format(filename) 
cmd2 = "at now +0 minutes" 
p1 = subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE, stdin=subprocess.PIPE) 
p2 = subprocess.Popen(cmd2, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE, stdin=p1.stdout)

監控程序:

啟動atd之後,必須要監控該執行程序,看看它是不是結束了,這裡我使用強者我同學AZ的python 解決方案: pnotify(ref 2)
當然,這個監控的程式也要用atd的方式來執行。

第一步是先找出atd呼叫出來的em -v的process,再來的function就是抄襲AZ的,簡單來說是先檢查/proc,看看該pid是否開啟,然後每隔一段時間就用kill 0的方式檢查該程序存在與否。
找出pid的部分,用的方法就笨一點,直接叫外部的ps,抓出有em的部分、濾出該使用者的資訊、排除grep自身,再用pid排個序,抓最大(最新)的pid即可,這個方法在pid用完一圈後會出錯,不過將就用一下,之後再看看有沒有更好的解,有的話麻煩強者們提示一下m(_ _)m:
pid_list = [] 
cmd = "sleep 1; ps -elf" 
p = subprocess.Popen(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE, stdin=subprocess.PIPE) 
stdout = p.stdout.read().decode("utf-8").split('\n') 
for line in stdout: 
    if ("em -v" in line) and (username in line) and ("grep" not in line): 
        pid_list.append(line.split()[3])

就可以抓出pid了。 再來再用atd開啟一個pnotify的監控工作即可。

email:

為了方便使用者,使用的是python + SMTP module,這部分的程式碼只能用明碼寫出帳號密碼,不過這在權限上設定為只有我能看即可;主要code如下:
 # open smtp session 
session = smtplib.SMTP('smtp.gmail.com', 587) 
session.ehlo 
session.starttls() 
session.ehlo 
session.login(account, password) 

# prepare the send message 
msg = MIMEText("Your EM simulation: {0} is over".format(filename)) 
msg['Subject'] = "the test title" 
msg['From'] = sender 
msg['To'] = receiver 


# send the message 
session.sendmail(sender, [receiver], msg.as_string()) 
session.quit()

透過google的smtp進行文件的轉送,其實這沒什麼,大部分都是抄的lol(ref 1)

成果:

現在工作站可以透過 runem file1.son 的方式執行一個超大em模擬,em模擬結束時候,可以透過電子郵件,通知進行模擬的使用者。
本程式透過python譔寫,相當快速,總開發時間約3-4天。
原始碼已上傳到github上:
https://github.com/lc85301/runem

附章:

趁著這次佈署runem的時候,順便佈署了另一個小script: clearcdslck
其實沒什麼,只是一個shell包含一行指令:
find . -name *.cdslck -exec rm -fv {} \;

方便使用者清除因不當結束產生的.cdslck檔。

參考資料:

1. about python mail using google SMTP
http://segfault.in/2010/12/sending-gmail-from-python/
2. about pnotify.py
http://blog.azhuang.me/2011/07/script-for-notifying-process.html#more
3. about python subprocess
http://docs.python.org/2/library/subprocess.html

致謝:

本文感謝AZ Huang同學的pnotify.py以及在SMTP使用上的指導,另外感謝同實驗室的曾奕恩大師幫忙測試本程式。