AWS 初試

因綠際會讓我有機會去研究 Amazon Web Service 。那是個與 GAE 功能相同，但操作模式不盡相同的雲端服務。

閱讀更多…

Python: 淺談 lambda 函式

lambda是用來定義一個小小函式用的，與一般使用的 def 有些許不同， Lisp 語言也有這個功能。因為這個 lambda 函式，讓 Python 語言可以更靈活地使用。

閱讀更多…

「作弊的文化」讀後感

---- 聲明開始 ----


要檢討別人前，先自我檢討。

過去我曾在工作上，利用公司列表機印了幾本 PDF 書籍(大概幾千頁吧!)，想當然耳，那些 PDF 檔還是違反著作權抓來的。印了近 10 本後就不這麼作了，因為浪費我的時間，印出來後還得整理裝訂，有時候列表機卡紙，也得自己處理，這根本就是打自己巴掌。於是，我直接花錢請印刷店處理，雖然書錢是自己出的，但一樣不脫「違反著作權」這條法令。等到會上 amazon 買書後，就不印了。買原版的書又精美，又對得起作者，何必跟自己良心過不去。當時自己印得不精美的書，後來也是全丟了，真對不起那些樹木。


另外在軟體使用(N 年前)上，也盜了不少的軟體： Matlab, MS Office, Windows 2000, Windows XP, 嘸蝦米輸入法, Dreamweaver, VisualBasic 6...。後來接觸 Open Source 後，一個一個戒掉了，因為要花錢的軟體，沒有比較好用。現在我用 Ubuntu Linux, Python, Netbeans 來工作，偶爾要用 MS office 時，就把裝在 VirtualBox 裡的學校授權 windows xp 打開，然後使用學校授權的 MS office 來看文件。是的，沒錯，中興大學花了一筆微軟授權費讓我可以在受到他人強迫時，不致於違法。


現在算來，我只有「嘸蝦米輸入法」是自己花錢買一套的，至今未買過其他軟體，當然這不含強迫中獎的微軟隨機版 OS ，還好後來的廠商自己也知道這不合理，所以我才買得到無 OS 的 Notebook 。


最後是音樂、電影，過去會用 emule, bittorrent 等作違法下載，但自從有了中華電信 MOD, 網樂通, Youtube 後，就不這麼作了。以前抓電影，還得自己找字幕、種子。用 mod, 網樂通方便多了，不過花個幾十塊而已。而音樂多半就聽我以前 CD 轉來的 OGG ，要不然就是在 youtube 上找 MV 來聽。


用 mod, 網樂通看電影很不錯，但還是有個缺點，電影類型不夠豐富，違法下載已有一堆網址了，但至今我還看不到「全境擴散(Contagion)」有在上映。只能繼續等，要不就是去買它的 DVD ，不過，現在好像也沒得買合法的。別叫我買 amazon 的 DVD ，我自認英聽還不夠好，沒字幕我是看不懂地。


我大學時是很少考試作弊或是抄別人報告的，要不然就不會被當了三十幾個必修學分，像我的結構學考試向來都是拿 6 分的，因為抄一題題目，老師會給 1 分，我乖乖地抄了 6 題。印象中，只有一堂經濟學考試是幫同學作弊，給他看答案，其他應該沒了吧! 如果還有，那就是我記性不好想不起來了。而研究所以後，我開始認真讀書了，不但成績比大學好很多，也不蹺課了。


以上，大概就是我過去作弊的事。


---- 聲明結束 ----


某日幫老婆在中教大圖書館找書時，不小心看到的一本 2006 年出版的書：「作弊的文化」。

以前很喜歡逛書局、圖書館，有興趣的題材當然會翻，但更有趣的是因為工作人員排列習慣不同，常常會發現一些原本我沒機會瞄到，但事後卻發現很令人驚喜的書。雜食是件好事，這在我接觸「指數投資|被動投資」後體會更深。也在塑化劑事件後，對入口食品改採混亂原則。以前我中餐吃飯時可以連吃同一家的陽春麵半年，也不會受不了，當時的想法很簡單，這世界就那麼多家店讓我吃，如果累計起來，這碗陽春麵總共吃了 180 次，那我就連續吃完 180 次後再去煩惱要改吃什麼，省得我每天花心思在思考吃什麼。但現在不這麼作了，我怕連吃某樣食物半年，體內單一毒素太高，一次就畢業了。混著吃，不同毒物的累計量會平均一點。

這本書題材很特別，主要介紹美國氾濫的作弊文化： 學生考試作弊、購買或抄襲他人報告、入學及畢業資格花錢買來、假造學經歷、律師浮報鐘點、會計師協助作假帳、逃漏稅、侵佔公司資產(包含小物件，像是筆、紙)、使用禁藥、以商逼官或是商人去當官人…等現象。

作者提了一些改正措施，不過，我不相信他講得是對的。因為就算他講得對，也無法施行改正來證明措施正確。那當然他也歸納了一些想法來論述為什麼美國人會作弊，這作弊現象是由來已久，還是最近才興起的。同樣地，我也不相信他的歸納，因為我看過「黑天鵝效應」，歸納不見得是有意義的。

那這本書到底對我有沒有價值? 有! 當然有，看這本書，能夠讓我了解美國人作弊的手段有那些，只要作者是誠實以對，是科學訪談來的資料，就能讓我對美國生活有進一步的體會，這就是對我的價值。

學生考試作弊、購買或抄襲他人報告、入學及畢業資格花錢買來、假造學經歷這幾樣也可在臺灣社會體會到，這應該不難想像吧! 而且美國是更氾濫的。因為美國有很多"""高級"""私立學校是可以被「錢」操控的，建議各位可以去看看「女人香」這部電影。

而律師浮報鐘點，可以去看看「黑色豪門企業」這部電影來一窺全貌。

會計師協助作假帳，可以去看看「世界通訊」、「安隆」的倒閉新聞。

在逃漏稅部份幾乎是全民運動。在「蘋果橘子經濟學」中，也提到某一年全美國少了幾百萬個小孩，因為國稅局全面電腦化，可以比對大家的扶養子女是否有重複。

侵佔公司資產(包含小物件，像是筆、紙)，我印象中好像有部電影提到職員拿到公司的信用卡後，結果大刷特刷的，忘了是那一部了。

使用禁藥部份請看艾拉、馬奎爾、麥可強森的故事。

以上作弊的事就請各位自行搜尋資料或是去看本書來深入了解。我想要討論的是「以商逼官或是商人去當官人」這種事。而且想從美國的現象來討論臺灣在這一部份的問題。

商人當官人，在臺灣政壇上，好像只有發生在「縣市首長」及「立委、議員」上，內閣部份就我印象以來，大概都是國營的金融相關事業董事長後來會當到財經首長，像是彭淮南先當中國商銀董事長後轉任中央銀行總裁，陳裕章從第一金董事長作到金管會主委，好像只有陳沖有當過合庫銀、中信證(民營)、永豐金(民營)董事長後再來作金管會主委及行政院副院長，其他的首長多半是先當官人，後才去當商人的，像是顏慶章、邱正雄、林全。就商人來當官人這件事，我覺得中華民國的防火牆作得還不錯。不像美國，一堆財政部長都是從華爾街跑去的，這一點可去看「高盛陰謀」來略知一二。

商人當官人有什麼不對? 如果是靠選舉選上的，那我沒話說，民主時代，選民接受商人當首長，也了解他會有利益衝突但還是讓他選上，這我沒話說，選後是大家一起承擔的。

但如果是指派的，那就大有問題了。因為無法直接監督，卻又得面臨他瓜田李下，所以可以看到 2008 美國次貸後，高盛活得比貝爾斯登、雷曼兄弟、美林、摩根史坦利還好。要不然，你們也可以想像一下，公共工程委員會主委曾任職於某家營造廠，那他監督的了舊公司所承攬的公共工程嗎? 搞不好，有些還是他經手的呢! 所以幸運的是這種事在中華民國不常發生。這值得慶祝。

而「以商逼官」這件事，我覺得臺灣就很嚴重了。當然，還沒有比美國嚴重啦。

上面這部影片，提到「公司」撥出大量的行銷支出去為候選人宣傳，這無非是希望將「有利於公司」的候選人送進政府體制中，在行政、立法方面協助公司經營。

除了送「合宜候選人」進政府體制，另外還有「形塑輿論」以迫使公務員執行政策轉向，因為公務員『買廣告』去宣傳政策是件不容易的事。要『買廣告』去宣傳，通常只能用在『拍馬屁』上。

有幾件類似『形塑輿論』的事，我分享給各位，但也有可能是我錯了，畢竟『形不形塑』都應該是檯面下的事：

1. 別讓彭淮南總裁變成下一個袁崇煥!
2. 證券交易所得稅會讓政府抽很多錢，導致沒有利潤。
3. 立委名額太多是導致國會亂象的主因，所以我們要刪減立委名額。

第一項，中央銀行的作為是不容外界質疑的，它也不受其他首長的管理，那新聞、報紙講新台幣該不該升值、貶值，幹麼? 削總裁威信，看能不能讓高層換個人，如果不能，或許也能逼總裁心死離職。總之，一個獨立性機關建立了，也找了個正確人選進去，那再指三道四都是不對的。

第二項，很多股民在郭宛容事件後，堅信課徵證所稅是件可怕的事，他們不管租稅正義，只在乎股票表面價值。於是，永遠都是在分皮毛，然後讓大戶吃香喝辣。

第三項，刪減立委名額後，可以看見國會的政黨種類急速減少，從2004年及2008年的結果看來，2004年泛藍 128 名，泛綠 147 名，其他有 148 名，小黨比例佔有 35 %，而 2008 年泛藍有 114 名，泛綠有 101 名，其他有 16 名，小黨比例佔有 7 %。小黨比例急速萎縮下，失去了政策多樣性。企業要買通立委，也可以花比較少的人力、金錢。這對弱勢團體來說，只有更失去支持聲音，看不來有什麼其他好處。

另外，還有一種是我覺得「大有問題」的「輿論」：「公務員領得錢比人多，事作得比人少」。

醜化公務員後，要幹麼呢? 首先大家都認為他們爛，所以就不介意立委們削他們預算，甚至讓機關合併但員額減少。事變多了，人卻少了，那他們就不能管那麼多事了。他們不能管那麼多事後，則「黑心企業」就爽啦! 沒人力來稽查業務，甚至要打通關節時，需賄賂的人沒那麼多，這對「黑心企業」都是成本下降的好機會。如果我開的是「黑心企業」，「醜化公務員」絕對是一條好策略。

在「作弊的文化」中，它也提到 IRS 被削弱資源，使得他們無法向逃漏稅的有錢人提出訴訟，因為有錢人有能力與 IRS 乾耗。使得他們只好把目標對向一般平凡百姓，這一類人往往無法找到高級稅務律師反辯。諷刺的是 IRS 資源正是被廣大的美國百姓要求刪減的，因為他們極度討厭稅務員。

簡單講，老鼠去說貓的壞話，結果主人相信了，還把貓趕走，那接下來是誰的天下?

但是話說回來，我們如何能分辯什麼是正確的「輿論」。

首先，別相信「廣告」：

這個廣告聽說效果很好。讓很多人下定決心投給那個團隊，不過，仔細想想，這「準備好了」四個字，講也只花了 5 秒鐘。但一個政策執行要花多少時間，像蘇花高從環島路網決策成形、選址、測量、工法決定…也花了幾十年了。你聽到「準備好了」也是花 5 秒鐘，但你該相信嗎? 另一個有「魔力的廣告詞」是「馬上好」，很多人聽到這句話後，就莫明奇妙地把票奉上了。我覺得很可笑。

第二個，要分得清那個是「廣告」：

看雜誌時，出版商常常把廣告作成報導本文，如果你沒能力分得出來，那如何知道那個是忠實報導，那個是自吹自擂。不過，像這類會把「廣告」及「本文」混合的出版商，最好把它們的讀物當作資源回收物，看過即忘。

第三個，少看新聞及雜誌，多看點書(也就是第一手資料，像是候選人政策白皮書)：

了解政治或是選擇正確人選，從新聞、雜誌上獲得的幫助不大。多看點書來了解你想要的理想世界是什麼，這樣你才有學識去要求候選人作到。然後要看候選人政策白皮書，這樣你才知道，這個候選人到底想要作什麼，你也才有得選擇，別去聽新聞記者的轉述，二手資料常常是錯的。

最後我的結論是「了解作弊的手段是有助不作弊的人贏得比賽的法門」，所以不管你想不想、愛不愛，都得了解「作弊的方法」。

另一種解鋼筋切割組合問題(無界背包問題)的方法(改自 thinker 所提觀念)

#!/usr/bin/env python
# -*- coding: utf8 -*-
""" cut(10, [7, 5, 3, 2]) = cut(3, [7, 5, 3, 2]) + cut(10, [5, 3, 2])
"""
def _plus1(a):
    a[0] += 1
    return a


def _cache(my_function):
    CACHE = {}
    def inner_function(*args):
        key = str(args[:])
        if not CACHE.get(key, None):
            CACHE[key] = my_function(*args)
        return CACHE[key]

    return inner_function


@_cache
def cut(total, sizes):
    propers = tuple([sz for sz in sizes if sz <= total])
    if len(propers) == 1:
        return [[0,]*(len(sizes)-len(propers))+[total/propers[0],],]
    elif not propers:
        if total < 0:
            return []
        else:
            return [[0,]*len(sizes),]

    result1 = [_plus1(a) for a in cut(total-sizes[0], sizes)]
    result2 = [[0, ]+a for a in cut(total, sizes[1:])]
    return result1 + result2


if __name__ == '__main__':
    from time import time

    bar = 10
    sizes = [7, 5, 3, 2]

    t0 = time()
    answer = cut(bar, sizes)
    print time() - t0

    print 'count: %s'%len(answer)
    #for a in answer:
    #    print a, sum([j*sizes[i] for i, j in enumerate(a)])

其計算邏輯是 cut(10, [7, 5, 3, 2]) = cut(3, [7, 5, 3, 2]) + cut(10, [5, 3, 2]) ，這觀念從 Thinker 那邊學來的，它用在計算 cut(10, [7, 5, 3, 2]) 的組合數有多少時，非常非常快，不過，我在擴充至求組合數有那些時，這方法的速度就比不上 cut(10, [7, 5, 3, 2]) = (cut(10, [5, 3, 2]) 的結果，其元素 0 插入 0) + (cut(3, [5, 3, 2]) 的結果，其元素 0 插入 1) 了。

不曉得是不是我在運算過程中，那裡少了優化?

再改寫「背包問題」的求解程式碼

之前的作法是將 cut 函式所計算的 list 結果直接 append 到全域變數 tmps 中，這樣的 cut 函式是無法作 decorator 的。

新方法則是把 cut 函式的 input, output 重新規劃，讓答案就是 return 值，這樣 input 就能對應到單一 output ，透過這個特性，我們就能加上一個 @cache decorator ，去作快取。因為在求解的過程中，勢必會遇到重覆的 input ，有了快取，可以少算一次。

其中的 _no_cache_count 值指的是第一次遇到的 input 值，而 _cache_count 值則是利用 dictionary 找到答案的次數。

要怎麼建構出 cut 函式的樣貌? 我們一開始先抽象地想像這個 cut 函式要作到的事就是 answer = cut(bar, sizes)

answer 是我們要的答案，結構是 list of list( [[ , , , ..], [ , , , ..], ..] )。而 bar 是原長度， sizes 則是需求尺寸的 list 。

假設我們帶 bar = 10， sizes = [7, 5, 3, 2] ，那麼經過 cut 運算，就能得到一個 list of list 的 answer，那到底 answer 是多少? 我們先不管。但我們可以知道 10 拿給 7 去切，可以得到 0, 1 兩種組合。

所以 cut(10, [7, 5, 3, 2]) 一定會等於 cut(10, [5, 3, 2]) 的結果其解全部在元素 0 的位置插入 0 + cut(3, [5, 3, 2]) 的結果其解全部在元素 0 的位置插入 1 。

一樣地， cut(10, [5, 3, 2]) 也會等於 cut(10, [3, 2]) 的結果其解全部在元素 0 的位置插入 0 + cut(5, [3, 2]) 的結果其解全部在元素 0 的位置插入 1 + cut(0, [3, 2]) 的結果其解全部在元素 0 的位置插入 2 。

直到 cut(10, [2]) 時，我們知道它的結果就是 ([5], ) ，為什麼是一個 tuple of list ? 因為之前我們就定義 cut 一定要回傳 list of list ，而因為這次的 cut 回傳值本身並不會被修改，所以傳個 tuple 回去，可以少用一滴滴的記憶體(應該是一滴滴而已)。

當開始有 answer 被回傳後，我們就開始作合併的工作(就是把前一個需求尺寸的用量插入 answer 內的 list)。合併後再回傳。

程式碼如下，不過在實際跑的時候，有二件事我不能理解，為了比較 cut 與 cache_cut 的效率差別，我在同一個行程上分別跑了兩次 cut, 兩次 cache_cut ，而順序是 cache_cut, cut, cut, cache_cut ，cache_cut 比 cut 快，這很容易理解，但第二次的 cut 居然會比第一次的 cut 還慢，這我就不懂了。

另外，我每次跑 cut 之前，都是用 cs = CutSteel(bar, sizes) 創建新的物件，為什麼第二次跑的 cache_cut ，它還是可以找到第一次 cache_cut 所儲存的 CACHE 呢?

最後，我還得到一個結論，當解答組合數不多時，用 cut 會比 cache_cut 快。因為小題目，遇到重覆 input 少，但如果還是全部的 input 要儲存 CACHE ，那所花費的時間還不夠重覆 input 所節省的時間了。

  1 #!/usr/bin/env python
  2 # -*- coding: utf8 -*-
  3 import types
  4 
  5 
  6 
  7 class CutSteel:
  8     u"""  目的：解鋼筋切割的組合問題(也就是背包問題)，但不只是求組合數，
  9                 也要把所有的組合列出。
 10           例： 10 公尺長的鋼筋，要切成 7, 5, 3, 2 公尺等，有多少種組合。
 11           解：
 12                  7  5  3  2
 13                 [1, 0, 1, 0]
 14                 [1, 0, 0, 1]
 15                 [0, 2, 0, 0]
 16                 [0, 1, 1, 1]
 17                 [0, 1, 0, 2]
 18                 [0, 0, 3, 0]
 19                 [0, 0, 2, 2]
 20                 [0, 0, 1, 3]
 21                 [0, 0, 0, 5]
 22     """
 23     def __init__(self, bar, sizes):
 24         if type(bar) != types.IntType or bar <= 0:
 25             raise ValueError(u'只接受正整數')
 26         for s in sizes:
 27             if type(s) != types.IntType or s <= 0:
 28                 raise ValueError(u'只接受正整數')
 29 
 30         self._no_cache_count = 0
 31         self._cache_count = 0
 32 
 33 
 34     def cache(my_function):
 35         CACHE = {}
 36         def inner_function(*args):
 37             key = str(args[1:])
 38 
 39 #            try:
 40 #                #INFO 用 try 的會比 if 慢一點點。只慢一點點。
 41 #                CACHE[key]
 42 #                args[0]._cache_count += 1
 43 #            except KeyError:
 44 #                args[0]._no_cache_count += 1
 45 #                CACHE[key] = my_function(*args)
 46 
 47             if not CACHE.get(key, None):
 48                 CACHE[key] = my_function(*args)
 49                 args[0]._no_cache_count += 1
 50             else:
 51                 args[0]._cache_count += 1
 52             return CACHE[key]
 53 
 54         return inner_function
 55 
 56 
 57     @cache
 58     def bag(self, total, sizes):
 59         u""" 只計算組合數 from thinker"""
 60         propers = tuple([sz for sz in sizes if sz <= total])
 61         if not propers:
 62             if total >= self._minsize: return 0
 63             else: return 1
 64 
 65         num = self.bag(total - propers[0], propers) + self.bag(total, propers[1:])
 66         return num
 67 
 68 
 69     def cut(self, total, sizes):
 70         u""" 本函式的 input 為「被切割長度」及「欲切割的種數」。
 71 
 72             output 為該 input 的所有組合。
 73         """
 74         if len(sizes) == 1:
 75             return (
 76                     [(total / sizes[0]), ],
 77                     )
 78         elif total < sizes[-1]:
 79             return (
 80                     [0,] * len(sizes),
 81                     )
 82 
 83         return [
 84                 [j] + tr
 85                     for j in xrange(0, total / sizes[0] + 1)
 86                     for tr in self.cut(total - sizes[0] * j, sizes[1:])
 87                 ]
 88 
 89 
 90     @cache
 91     def cache_cut(self, total, sizes):
 92         u""" 因為 cache_cut 函式本身是具有固定 input 就會產生固定 output ，
 93             它們具有一對一或多對一的關係，所以我把 input,
 94             output 放在一個 dictionary 中，若程式計算到相同的 input 時，
 95             可免計算，直接從 dictionary 拿答案。
 96 
 97             其實本函式就是複製 cut 函式後，
 98             將函式內程式碼中的 self.cut 改成 self.cache_cut ，
 99             並在函式名前加上 @cache 而已。
100         """
101         if len(sizes) == 1:
102             return (
103                     [(total / sizes[0]), ],
104                     )
105 #        elif total < sizes[-1]:
106 #            #INFO 多這個判斷式反而變慢了。因為已經用 cache 了，
107 #            #所以那些 total < sizes[-1] 情況會變成比較少，
108 #            #然而在一個 cache_cut 函式中多加一個 if ，則判斷時間會多一倍,
109 #            #加速效果反而不如預期。
110 #            return (
111 #                    [0,] * len(sizes),
112 #                    )
113 
114         return [
115                 [j] + tr
116                     for j in xrange(0, total / sizes[0] + 1)
117                     for tr in self.cache_cut(total - sizes[0] * j, sizes[1:])
118                 ]
119 
120 
121 
122 from time import time
123 import sys
124 if __name__ == '__main__':
125     #bar = sys.argv[1:]
126     #sizes = sys.argv[2:]
127     bar = 10
128     sizes = [7, 5, 3, 2]
129     sizes.sort(reverse=True)
130     sizes = tuple(sizes)
131 
132     cs = CutSteel(bar, sizes)
133     cs._minsize = min(sizes)
134     print 'Total count: %s' % cs.bag(bar, tuple(sizes))
135 
136     cs = CutSteel(bar, sizes)
137     time0 = time()
138     result = cs.cache_cut(bar, sizes)
139     print 'cache_cut spend time: %s' % (time() - time0)
140     print len(result)
141     print('\tno cache count: %s, cache count: %s'%(cs._no_cache_count, cs._cache_count))
142 
143 #    cs = CutSteel(bar, sizes)
144 #    time0 = time()
145 #    result = cs.cut(bar, sizes[:])
146 #    print 'cut spend time: %s' % (time() - time0)
147 #    print len(result)
148 #    print('\tno cache count: %s, cache count: %s'%(cs._no_cache_count, cs._cache_count))
149 #
150 #    cs = CutSteel(bar, sizes)
151 #    time0 = time()
152 #    result = cs.cut(bar, sizes[:])
153 #    print 'cut spend time: %s' % (time() - time0)
154 #    print len(result)
155 #    print('\tno cache count: %s, cache count: %s'%(cs._no_cache_count, cs._cache_count))
156 #
157 #    cs1 = CutSteel(bar, sizes)
158 #    time0 = time()
159 #    result = cs1.cache_cut(bar, sizes[:])
160 #    print 'cache_cut spend time: %s' % (time() - time0)
161 #    print len(result)
162 #    print('\tno cache count: %s, cache count: %s'%(cs._no_cache_count, cs._cache_count))
163 
164     for i in xrange(0, len(result)):
165         print(result[len(result)-i-1])

Connect MS SQL Server with python-pymssql

Two years ago, i writed a blog: "How to connect MS SQL Server with Python in the Linux OS?". I used freetds + python-sybase in this Howto. Now i have to upgrade the linux server to x86_64 architecture(original in i386), then the old python-sybase package have always been failured. The newest version released at 2010 DEC, but i tried all the 39, 38, 36 versions that no one can compile accurately.

Fortunately, my underclassman talked to me about python-pymssql. And it has been packaged in the Ubuntu, so i just use the magic command:

$ sudo apt-get install python-pymssql

My Linux server takes the power back!!!

The usage likes python-sybase, below is the example:

 1 #!/usr/bin/env python
 2 import sys, datetime, pymssql
 3 from types import IntType
 4 
 5 DB = {
 6     'ip': '127.0.0.1',
 7     'port': '1433',
 8     'user': 'user',
 9     'password': 'password',
10     'database': 'database',
11 }
12 
13 try:
14     Database = pymssql.connect(host=':'.join([DB['ip'], DB['port']]), user=DB['user'], password=DB['password'], database=DB['database'], as_dict=True)
15 except pymssql.OperationalError, msg:
16     print "Could not Connection SQL Server"
17     sys.exit()
18 else:
19     DBCursor = Database.cursor()
20 
21 sql = "select * from data_table"
22 print('sql: %s' % sql)
23 DBCursor.execute(sql)
24 
25 while 1:
26     row = DBCursor.fetchone()
27     if not row: break
28 
29     for k, v in row.items():
30         if type(k) == IntType: continue
31 
32         if k.lower() in ('some_date_field', ):
33             # change field type
34             if type(v) == datetime.date:
35                 value = v
36             else:
37                 try:
38                     value = datetime.date(*time.strptime(v, '%Y/%m/%d')[:3])
39                 except:
40                     value = None
41         else:
42             value = unicode(str(v), 'cp950')
43 
44         print('%s => %s'%(k, v))

Install Python2.5 on Ubuntu 11.04 x86_64 for Google App Engine

之前所提的「Install Python2.5 on Ubuntu 10.04 i386 for Google App Engine」，主要是在 i386 Ubuntu 的安裝方式。我這一次換了電腦，也裝了 Ubuntu 11.04 amd64 的版本，所以安裝方式有些許不同：

1. 系統內建的 sqlite 函式庫無法連結。
2. 某些 .so 檔不再放在 /usr/lib ，而是在 /usr/lib32, /usr/lib64, /usr/lib/x86_64-linux-gnu 等地。

另外在安裝 python2.5 時，也想順便套上 readline 及 ipython 。以下是安裝過程：

先裝上 Ubuntu 內建的函式庫：

$ apt-get install liblcms1-dev zlib1g-dev libfreetype6-dev libjpeg62-dev libsqlite3-dev libssl-dev tk-dev libreadline-dev

安裝 sqlite3：

$ cd sqlite-autoconf-3070603/
$ ./configure --prefix=/usr/local/sqlite3 --enable-readline --enable-threadsafe --enable-dynamic-extensions
$ make && sudo make install

安裝 Python2.5.6：

$ cd Python2.5.6/
$ ./configure --prefix=/usr/local/python25 --with-zlib -with-zlib-library=/usr/lib/x86_64-linux-gnu --with-zlib-include=/usr/include --with-tk --with-tk-library=/usr/lib32 --with-tk-include=/usr/include --with-tcl --with-tcl-library=/usr/lib32 --with-tcl-include=/usr/include --libdir=/usr/local/sqlite3/lib --includedir=/usr/local/sqlite3/include --with-freetype2 --with-jpeg --with-readline
$ make && sudo make install

安裝 ipython

$ cd ipython/
$ sudo /usr/local/python25/bin/python2.5 setup.py install

安裝 GAE 相依模組 ipaddr：

$ cd ipaddr-2.1.1/
$ sudo /usr/local/python25/bin/python2.5 setup.py install

安裝 GAE 相依模組 python-ssl：

$ cd python-ssl-1.15/
$ cp -rf ../Python2.5.6/Include/* /usr/local/python25/include/ # 需要 Python 源碼
$ sudo /usr/local/python25/bin/python2.5 setup.py install

安裝 PIL：

修改 Imaging-1.1.7/setup.py 中的參數如下：

TCL_ROOT = '/usr/lib32'
JPEG_ROOT = '/usr/lib32'
ZLIB_ROOT = '/usr/lib/x86_64-linux-gnu/'
TIFF_ROOT = '/usr/lib32'
FREETYPE_ROOT = '/usr/lib32'
LCMS_ROOT = '/usr/lib32'

檢查模組是否可使用

$ /usr/local/bin/python2.5 setup.py build_ext -i

測試模組

$ /usr/local/bin/python2.5 selftest.py

看到如下訊息，就代表模組皆有支援

　--- PIL CORE support ok
　--- TKINTER support ok
　--- JPEG support not installed
　--- ZLIB (PNG/ZIP) support not installed
　--- FREETYPE2 support ok
　--- LITTLECMS support ok

再執行

$ sudo /usr/local/python25/bin/python2.5 setup.py install

最後，再把 dev_appserver.py, appcfg.py 中的 #!/usr/bin/env python 改成 #!/usr/bin/env python2.5 即可(也不是必須的，只要你知道執行 GAE server 時是用 python2.5 就夠了)。

完成後就可以在 Ubuntu 11.04+ x86_64 中開發 GAE 程式了。

CMClass: 簡述 libsvm(Support Vector Machine library) 使用方法

libsvm乃台大林智仁老師開發的 Open source 工具，其目的為實作 Support Vector Machine 分類器，使用語言主要是 C++ ，目前也有 JAVA 版本，也提供其他語言的 wrapper ，像是 Perl, Python, Ruby, Matlab, Hashkell, Lisp 等。

詳細數學就不介紹了，怕大家睡著(但其實是因為還沒看懂)，各位可以看一下下面那段這個影片，大略了解 SVM 分類器如何區別不同資料。



本文章主要介紹的是用 Python 語言去操作 libsvm 函式庫。

先解壓縮 libsvm.tgz 檔，可以看到 python 及 windows 資料夾，如果要在 Linux 中使用的話，請在主目錄中作

$ make lib

這樣會得到 libsvm.so.2 檔，這是 libsvm 的主函式庫，而在 windows 中使用的話，它則是先幫你編譯好這個檔了，可在 windows/ 找到這個 libsvm.dll 檔。

在 Linux 中，請把 python/*py 放到 /usr/local/lib/python2.6/site-packages 中，而 libsvm.so.2 放到 /usr/local/lib/python2.6/ 。

在 windows 中，請把 python/*py 放到 C:\Python26\Lib\site-packages 中，而 libsvm.dll 請放到 C:\Python26\Lib\windows 資料夾中(因為 svmutil.py 寫死了它的相對路徑，所以務必依它的相對位置置放)。

請在 Python shell 中，鍵入下列指令，測試是否安裝成功。

>>> from svmutil import *
>>>

沒錯誤訊息，那就是安裝對了。

使用 svm ，主要就是兩個動作： 訓練及預測。

訓練：

svmutil.svm_train 函式的引數有「類別標籤」、「觀察值」、「參數」。

你的原始資料若是如下：

1. 3, 4, 5, 6 => 第二類
2. 3, 4, 5, 5 => 第一類
3. ....

前面的 #. 表第幾個觀察值，後面逗號分隔的數據為各維度的值，行末則是放置該觀察值為第幾類的說明。請把它轉成

>>> Y = [2, 1, ...]
>>> x = [(3, 4, 5, 6), (3, 4, 5, 5), ...]

類別標籤請獨立放置到一個 list 中，而觀察值維度則依序放置到另一個 list 中。接下來，就能使用 svm_train：

>>> from svmutil import *
>>> model = svm_train(Y, x, '-c 4')

所得到的 model 就是一個經過訓練的分類器。

預測

接下來，我們要拿訓練好的分類器去預測新的觀察值：

>>> p_label, p_acc, p_val = svm_predict([0]*len(new_x), new_x, model)

而 p_label 就是依 new_x 順序所對應的類別標籤 list 。

下圖是我隨機生成的 300 點，圓點為原始的觀察值，而以線相連的連續點則是預測點。



詳細程式碼請參照如下：

 1 #! /usr/bin/python
 2 # -*- coding: utf8 -*-
 3 
 4 __author__="hoamon"
 5 __date__ =u"$2011/4/12 下午 05:52:31$"
 6 
 7 from math import pi, sin, cos
 8 from random import random
 9 from matplotlib import pyplot as plt
10 from svmutil import *
11 
12 def circleData(centre, radius, down_limit_percent=0, lens=100, range=[0, 100]):
13     points = []
14     while len(points) < lens:
15         _angle = 2 * pi * random()
16         radius_percent = random()
17         if radius_percent < down_limit_percent: continue
18         _radius = radius * radius_percent
19         x = centre[0] + cos(_angle) * _radius
20         y = centre[1] + sin(_angle) * _radius
21         if range[0] <= x <= range[1] and range[0] <= y <= range[1]:
22             points.append((x, y))
23     return points
24 
25 
26 def test():
27     u""" 製作三群的隨機資料，每群皆 100 個點，點位置的 x, y 限制在 0 ~ 100 之間
28 
29         最後利用 matplotlib 繪製出來的圖，"單點"表原始資料，而連續點畫線的部份，
30         該點位的類別則是利用 svm_predict 計算出來的。
31 
32         Y = [1, 1, 1, ..., 2, 2, 2, ..., 3, 3, 3, ...]
33         x = [(x1, y1), (x2, y2), ...]
34     """
35     Y = [1] * 100 + [2] * 100 + [3] * 100
36     x1, x2, x3 = (circleData((35, 40), 12),
37         circleData((35, 40), 48, down_limit_percent=0.25),
38         circleData((80, 80), 20)
39         )
40     x = x1 + x2 + x3
41 
42     m = svm_train(Y, x, '-c 4')
43 
44     #INFO 在 100x100 的畫布上，打出 40000 個點，拿這 4 萬個點去給 m 作預測，算出這 4 萬個點的類別
45     points = [(i*0.5, j*0.5) for j in xrange(0, 200) for i in xrange(0, 200)]
46     p_label, p_acc, p_val = svm_predict([0]*40000, points, m)
47 
48     line_1, line_2, line_3, pre_label = [], [], [], p_label[0]
49     for i in xrange(0, 200):
50         for j in xrange(0, 200):
51             index = i * 200 + j
52             now_label = p_label[index]
53             if now_label == 1 :
54                 line_1.append(points[index])
55             elif now_label == 2 :
56                 line_2.append(points[index])
57             elif now_label == 3 :
58                 line_3.append(points[index])
59 
60     fig = plt.figure()
61     ax = fig.add_subplot(111)
62     ax.plot([p[0] for p in x1], [p[1] for p in x1], 'ro')
63     ax.plot([p[0] for p in x2], [p[1] for p in x2], 'go')
64     ax.plot([p[0] for p in x3], [p[1] for p in x3], 'bo')
65     ax.plot([p[0] for p in line_1], [p[1] for p in line_1], 'r-', alpha=0.5)
66     ax.plot([p[0] for p in line_3], [p[1] for p in line_3], 'b-', alpha=0.5)
67     ax.set_title('Points of three classes')
68     ax.set_xlabel('x')
69     ax.set_ylabel('y')
70     ax.set_xlim(0, 100)
71     ax.set_ylim(0, 100)
72     plt.show()
73     return m, p_label, p_acc, p_val
74 
75 
76 if __name__ == "__main__":
77     test()

無法在 Windows 上的 NetBeans 作中文註解

為了讓 Python 程式能容易在團隊之間快速流動，我們要求大家在程式編碼上一律使用 utf8 。只要在程式檔的第一行宣告 #-*- coding: utf8 -*- 以及使用 utf-8 編碼存檔即可。

不過，在 Windows 中執行時，因為它還活在 cp950 的時代，所以我們還要在 Python 主安裝目錄中的 Lib/site-packages/sitecustomize.py 中加入

import sys

sys.setdefaultencoding('utf8')

這樣 python 程式在執行時，才不會遇到 UnicodeEncodeError (其實偶爾還是會遇到，原因是搞混了 Unicode 編碼及 UTF-8 編碼)。

而在使用 NetBeans 時，我們也會在 /etc/netbeans.conf 中設定 -J-Dfile.encoding=utf8 來讓 NetBeans 正常顯示程式中的 UTF-8 編碼中文字。

不過，在 mercurial commit 時，卻無法使用中文作註解。這時候，只要在 netbeans.conf 加入 -J-Dmercurial.encoding=utf8 即可。

使用 PayPal Express Checkout 作線上收款機制

若你不太了解什麼是金流系統，可以先去看「簡述金流系統」。

消費者在線上購買商品或勞務，所謂的付款其實只牽扯到兩件事：『身份驗證』及『確認額度』。但這兩件事都是特許公司如銀行或信用卡公司才能作的事。所以我們得透過中間人或中間人的中間人(金流公司)幫我們作到這兩件事，而我選的是 PayPal ，它是跨國的金流公司，我個人認為十分適合純網際網路公司使用。

從誰那裡匯多少錢到誰那裡? 有三個變數：『付款的人』、『付多少』及『收款人』。這『收款人』當然是我們自己的公司囉。在程式中設定收款帳戶只要設定『帳戶名稱(USERNAME)』、『密碼(PASSWORD)』及『簽名(SIGNATURE)」就行了，如何申請這三種資料請看我的另篇文章。

而『付多少』的設定變數名則為 AMT 。但在消費者刷卡時，要讓他明確地了解買的東西到底有什麼? 價錢是多少? 要刷多少錢? 我們得另外設定訂單的顯示變數。有商品名稱(L_NAME0)、商品描述(L_DESC0)、商品編號(L_NUMBER0)、購買數量(L_QTY0)、商品單價(L_AMT0)、所有商品小計(ITEMAMT)、運送及處理費用(SHIPPINGAMT)、稅金(TAXAMT)等。

這些變數後有帶 0 的表示它可以是多值，如果該筆訂單有第二項商品的話，就設定 L_NAME1 、 L_DESC1 、 L_NUMBER1 、 L_QTY1 、 L_AMT1 ，以此類推。

這些訂單顯示變數有幾項原則：

• ITEMAMT 必須等於 L_AMT0 * L_QTY0 + L_AMT1 * L_QTY1 + ... + L_AMTn * L_QTYn


• AMT 必須等於 ITEMAMT + SHIPPINGAMT + TAXAMT

違反這兩個原則， PayPal 會報錯的。

而『付款的人』部份就不是我們程式設計師該處理的，這部份交由 PayPal 自己與消費者確認卡號是否正確、與發卡銀行確認是否允許消費者刷該筆訂單的金額。等到 PayPal 作完『身份確認』及『額度確認』後，PayPal 會回傳一個 TOKEN ，告知我們消費者有能力消費該筆訂單，如果我們接受該筆交易，就以這個 TOKEN 回覆給 PayPal ，那它就幫我們刷下消費者的卡片了。之後就能在 PayPal 的帳務管理介面中看到消費者的付款紀錄。

上面的觀念了解了，我們這就進行程式的實作吧!

PayPal 的付款程序要經過 3 次的 API 呼叫，分別是 SetExpressCheckout, GetExpressCheckoutDetails, DoExpressCheckoutPayment 。

• SetExpressCheckout 是整理好一份訂單資訊供消費者瀏覽。


• GetExpressCheckoutDetails 是抓取當次交易的詳細資訊，但不包含消費者的卡號。


• DoExpressCheckoutPayment 要求 PayPal 對消費者進行刷卡動作，完成交易。

而消費者瀏覽網頁順序則是『我們的訂單頁面』=>『確定購買』=>『SetExpressCheckout』=>『PayPal 付款頁』=>『PayPal 確認頁』=>『GetExpressCheckoutDetails+DoExpressCheckoutPayment』=>『我們的購買成功頁面』。

我們自己所寫的『確定購買』程式中，會紀錄消費者的購買資訊，產生訂單編號，完成後執行 SetExpressCheckout API 呼叫動作。所謂的呼叫，其實不過就像是 html 中的 form submit 。很懶惰的作法是輸出一個如下的 html 表單，然後要求消費者自己手動按下送出鈕。

 1 <form method="POST" action="https://api-3t.paypal.com/nvp">
 2     <input type="hidden" name="USER" value="API_username_do_not_copy_me">
 3     <input type="hidden" name="PWD" value=" API_password_do_not_copy_me">
 4     <input type="hidden" name="SIGNATURE" value="API_signature_do_not_copy_me">
 5     <input type="hidden" name="L_NAME0" value="test_product_name">
 6     <input type="hidden" name="L_DESC0" value="test_description">
 7     <input type="hidden" name="L_NUMBER0" value="test1">
 8     <input type="hidden" name="L_QTY0" value="1">
 9     <input type="hidden" name="L_AMT0" value="85">
10     <input type="hidden" name="ITEMAMT" value="85">
11     <input type="hidden" name="SHIPPINGAMT" value="10">
12     <input type="hidden" name="TAXAMT" value="5">
13     <input type="hidden" name="AMT" value="100">
14     <input type="submit" name="METHOD" value="SetExpressCheckout">
15     <input type="hidden" name="VERSION" value="63.0">
16     <input type="hidden" name="CURRENCYCODE" value="TWD">
17     <input type="hidden" name="PAYMENTACTION" value="Sale">
18     <input type="hidden" name="CANCELURL" value="http://www.YourCancelURL.com">
19     <input type="hidden" name="RETURNURL" value="http://www.YourReturnURL.com">
20 </form>

這裡有幾個地方要注意， form method 一定是 POST ， form action 一定是 https://api-3t.paypal.com/nvp ，input name="METHOD" 的 value 一定是 SetExpressCheckout 。

VERSION 代表你呼叫的 API 版本是多少，版本號太小的 API ，可能會有些參數不支援。不過，以我使用的經驗，上面的參數都能跑在 53 ~ 63 之間。但能設得愈大愈好。

而 CURRENCYCODE 代表收取的幣別， TWD 代表新台幣， USD 代表美金，其他貨幣請參閱這裡。

PAYMENTACTION 的值有三種： Sale, Authorization, Order ， Sale 表一般銷售，消費者要買，你一定賣; Authorization 表須確認的銷售，如消費者要買 Giant 的 TCR SL 3 車架，但貴公司沒建置庫存管理，所以消費者下單後，你得到大如足球場的倉庫去找，找得到就賣，找不到只好跟消費者 Say Sorry! Order 表須更長時間的確認銷售，像 Authorization 最多只會在帳務管理系統中等 3 天讓你按下請款鈕，但 Order 可以等到 29 天。

CANCELURL 是當消費者在 PayPal 付款頁中，反悔了，在他取消交易時， PayPal 會導引他回到你的網站。

RETURNURL 是當消費者在 PayPal 確認頁按下「立即付款」， PayPal 會導引他回到你的網站，理論上，這個網頁就是你執行 GetExpressCheckoutDetails + DoExpressCheckoutPayment 的地方。

從這個 html form 範例中，可以了解呼叫 SetExpressCheckout API 真的是非常簡單的事，只要把握正確的 name - value pair(nvp) 即可。

不過我們是 Python 程式設計師，怎麼能用 html form 這麼簡單的東西來呼叫 API ，當然要用 urllib 囉! 把下面的程式插到『確定購買』程式的最後面，這樣就不用消費者自己手動按送出鈕了。

 1 from google.appengine.api import urlfetch
 2 import urllib
 3 
 4 string_hash = {
 5     "USER": "API_username_do_not_copy_me", "PWD": " API_password_do_not_copy_me",
 6     "SIGNATURE": "API_signature_do_not_copy_me", "L_NAME0": "test_product_name",
 7     "L_DESC0": "test_description", "L_NUMBER0": "test1", "L_QTY0": "1",
 8     "L_AMT0": "85", "ITEMAMT": "85", "SHIPPINGAMT": "10", "TAXAMT": "5",
 9     "AMT": "100", "METHOD": "SetExpressCheckout", "VERSION": "63.0",
10     "CURRENCYCODE": "TWD", "PAYMENTACTION": "Sale",
11     "CANCELURL": "http://www.YourCancelURL.com",
12     "RETURNURL": "http://www.YourReturnURL.com",
13 }
14 form_data = urllib.urlencode(string_hash)
15 result = urlfetch.fetch(url='https://api-3t.paypal.com/nvp',
16     payload=form_data,
17     method=urlfetch.POST,
18     headers={'Content-Type': 'application/x-www-form-urlencoded'},
19     deadline=10)
20 
21 hash = {}
22 for i in result.content.split('&'):
23     k, v = i.split('=')
24     hash[k] = urllib.unquote(v)
25 
26 redirect_url = 'https://www.paypal.com/cgi-bin/webscr?cmd=_express-checkout&useraction=commit&token=%s' % hash['TOKEN']
27 return HttpResponseRedirect(redirect_url)

跑到 redirect_url 網址後，就是 PayPal 自己與消費者互動的網頁，等到消費者確定付款了，就會再轉回我們的 RETURNURL 程式。在 RETURNURL 頁面中，首先呼叫 GetExpressCheckoutDetails 得到該 token 所對應的付款資訊。然後再執行 DoExpressCheckoutPayment 即可完成信用卡刷卡動作。

 1 # exec GetExpressCheckoutDetails
 2 token = request.GET.get('token')
 3 string_hash = {
 4     "USER": "API_username_do_not_copy_me", "PWD": " API_password_do_not_copy_me",
 5     "SIGNATURE": "API_signature_do_not_copy_me", "METHOD": "GetExpressCheckoutDetails",
 6     "VERSION": "63.0", "TOKEN": token,
 7 }
 8 form_data = urllib.urlencode(string_hash)
 9 result = urlfetch.fetch(url='https://api-3t.paypal.com/nvp',
10     payload=form_data,
11     method=urlfetch.POST,
12     headers={'Content-Type': 'application/x-www-form-urlencoded'},
13     deadline=10)
14 
15 hash = {}
16 for i in result.content.split('&'):
17     k, v = i.split('=')
18     hash[k] = urllib.unquote(v)
19 
20 if hash['ACK'] != 'Success':
21     error_messages = []
22     for k, v in hash.items():
23         error_messages.append('%s: %s'%(k, v))
24     raise Exception(';\n'.join(error_messages))
25 
26 # exec DoExpressCheckoutPayment
27 string_hash = {
28     "USER": "API_username_do_not_copy_me", "PWD": " API_password_do_not_copy_me",
29     "SIGNATURE": "API_signature_do_not_copy_me", "METHOD": "DoExpressCheckoutPayment",
30     "VERSION": "63.0", "TOKEN": token,
31     "AMT": "100", "CURRENCYCODE": "TWD",
32 }
33 form_data = urllib.urlencode(string_hash)
34 result = urlfetch.fetch(url='https://api-3t.paypal.com/nvp',
35     payload=form_data,
36     method=urlfetch.POST,
37     headers={'Content-Type': 'application/x-www-form-urlencoded'},
38     deadline=10)
39 
40 hash = {}
41 for i in result.content.split('&'):
42     k, v = i.split('=')
43     hash[k] = urllib.unquote(v)
44 
45 if hash['ACK'] != 'Success':
46     error_messages = []
47     for k, v in hash.items():
48         error_messages.append('%s: %s'%(k, v))
49     raise Exception(';\n'.join(error_messages))
50 
51 return HttpResponseRedirect('http://www.YourThankURL.com/')

就這樣，你會在 PayPal 的帳務管理系統中，看到消費者的付款紀錄。

指派問題使用 python + lp_solve 解決

指派問題乃線性規劃的一種特例，它的特性是不須強調解為 0-1 變數或整數值，但最後算出來它卻一定就是 0 或 1 ，只是這種說法是學理上的，當我們使用程式來計算時，往往因為這些工具在計算過程中使用數值分析的方法，造成解的結果只會接近 0 或是 接近 1 ，而不是純正的 0 或 1。

這也就是我在第 73 行中，使用 v > 0 而不是 v == 1 的原因，如果是寫 v == 1 的話，有些 v 值是 0.999999 的，就不會顯現了。事實上，使用 v > 0.5 會更好。不過，我最後檢查時，發現 > 0 就可以秀出這 50 個 x 的值，也就算了。

lp_solve 函式庫安裝方法請見舊文。

 1 # -*- coding: utf8 -*-
 2 """ 問題： 
 3     
 4     指定 0, 1, 2, ..., 49 等 50 個不可重複的數字給 x0 ~ x49，例如 x0 = 12, x1 = 33, ...
 5 
 6     y = sin(1*x0) + sin(2*x1) + sin(3*x2) + ... + sin(50*x49)
 7 
 8     求解 y 之最大值？
 9 
10     解法：
11 
12     此問題可視為一種指派問題，也就是說有 0 ~ 49 等員工，要放到 x0 ~ x49 的職位去，
13     這樣決策變數就會變成 p00(值為 1 代表 x0=0), p01(值為 1 代表 x1=0),
14     p02 , ..., p49_49 等 2500 個決策變數，且其值必為 0 或 1 。
15 
16     雖然目標函式看起來是非線性的，但其實是線性的， y 函式的係數應該長得如下：
17 
18             x0          x1          x2          ...
19     0       0(C00)      0(C01)      0(C02)      ...
20     1       0.84(C10)   0.91(C11)   0.14(C12)   ...
21     2       0.91(C20)   -0.76(C21)  -0.28(C22)  ...
22     ...     ...         ...         ...         ...
23 
24     所以如果決策變數是 p20 = p01 = p12 = 1，其餘為 0 ，則代表 x0 = 2，x1 = 0，x2 = 1，
25     這樣 y = 0.91 + 0 + 0.14 = 1.05 。
26 
27     所以目標式可以寫成 y = C00 * p00 + C01 * p01 + ... + C49_49 * p49_49 。
28 
29     最後再加上限制式
30     
31     p00 + p01 + ... + p0_49 = 1
32     p10 + p11 + ... + p1_49 = 1
33     ...
34     p49_0 + p49_1 + ... + p49_49 = 1
35 
36     p00 + p10 + ... + p49_0 = 1
37     p01 + p11 + ... + p49_1 = 1
38     ...
39     p0_49 + p1_49 + ... + p49_49 = 1
40 
41     等 100 條限制式後，就能求 y 的最佳解。
42 
43 """
44 from math import sin
45 import lpsolve55 as L
46 
47 LENGTH = 50
48 C = []
49 
50 for i in xrange(LENGTH):
51     for j in xrange(LENGTH):
52         C.append(-1*sin((j+1)*i)) # lp_solve 預設解極小值問題，所以我把目標函數係數全乘以 -1
53 
54 lp = L.lpsolve('make_lp', 0, LENGTH**2)
55 L.lpsolve('set_verbose', lp, L.IMPORTANT)
56 ret = L.lpsolve('set_obj_fn', lp, C)
57 
58 for i in xrange(LENGTH):
59     p = [0,] * (LENGTH ** 2)
60     for j in xrange(i*LENGTH, i*LENGTH+LENGTH): p[j] = 1
61     ret = L.lpsolve('add_constraint', lp, p, L.EQ, 1)
62 
63     p = [0,] * (LENGTH ** 2)
64     for j in xrange(0, LENGTH):
65         p[j*LENGTH+i] = 1
66     ret = L.lpsolve('add_constraint', lp, p, L.EQ, 1)
67 
68 L.lpsolve('solve', lp)
69 print u'目標值： %s' % (L.lpsolve('get_objective', lp) * -1) #要乘以 -1 來還原目標值。
70 vars = L.lpsolve('get_variables', lp)[0]
71 print u'決策變數： %s' % vars
72 for (ij, v) in enumerate(vars):
73     if v > 0:
74         i = ij / LENGTH
75         j = ij % LENGTH
76         print 'x%s = %s, ' % (j, i),
77         if i % 5 + 1 == 5: print

目標值最佳解為 47.8620523191 。

各變數值如下：
x21 = 0, x32 = 1, x47 = 2, x33 = 3, x1 = 4,
x37 = 5, x16 = 6, x45 = 7, x11 = 8, x25 = 9,
x18 = 10, x30 = 11, x7 = 12, x17 = 13, x0 = 14,
x41 = 15, x36 = 16, x22 = 17, x49 = 18, x9 = 19,
x44 = 20, x26 = 21, x43 = 22, x13 = 23, x42 = 24,
x35 = 25, x8 = 26, x20 = 27, x39 = 28, x40 = 29,
x29 = 30, x10 = 31, x34 = 32, x4 = 33, x2 = 34,
x38 = 35, x24 = 36, x6 = 37, x46 = 38, x5 = 39,
x27 = 40, x28 = 41, x14 = 42, x23 = 43, x48 = 44,
x19 = 45, x31 = 46, x12 = 47, x15 = 48, x3 = 49,

=== 後記 ===

經老師指導後，使用

ret = L.lpsolve('set_binary', lp, [1,]*(LENGTH**2)) #大約加在第 59 行後

令決策變數為 0-1 二元變數後，計算時間馬上減少了 60% 。

道路施工的排程問題，類似背包問題，但須考慮不同的排列方式

如：長度 10 公尺的路面，若有 7 公尺/日、 5 公尺/日、 3 公尺/日的施工工班可供選擇，則有幾種的排程組合? 此問題很像背包問題，但在背包問題中，它不須考慮裝入物品的順序，而只考慮種類。若問題改為路面總長度 1000 公尺，而有 [260, 230, 190, 140, 80] 幾種工班時，我的解答是 69225 種。以下是我的解法：

 1 class LineSerial:
 2     u"""  目的：解路面排程問題，如：長度 10 公尺的路面，若有 7 公尺/日、 5 公尺/日、 3 公尺/日
 3         的施工工班可供選擇，則有幾種的排程組合。
 4 
 5         解如下，共 17 種：
 6             [7, 7], [7, 5], [7, 3],
 7             [5, 7], [5, 5],
 8             [5, 3, 7], [5, 3, 5], [5, 3, 3],
 9             [3, 7],
10             [3, 5, 7], [3, 5, 5], [3, 5, 3],
11             [3, 3, 7], [3, 3, 5],
12             [3, 3, 3, 7], [3, 3, 3, 5], [3, 3, 3, 3],
13     """
14     def __init__(self, total, sizes):
15         """ serial_times 則是在計算 serial 函式被呼叫幾次。
16         """
17         sizes.sort(reverse=True)
18         self._sizes = sizes
19         self.serial_times = 0
20         self.result = []
21         self.serial(total, None, [])
22 
23 
24     def serial(self, total, length, tmp):
25         u""" 將 total 依序給 _sizes 中的所有元素去切，切完後就放入 tmp ，
26             當 total <= 0 時, 再放入 self.result 中。
27         """
28         #self.serial_times += 1
29         tmp.append(length)
30         if total <= 0:
31             self.result.append(tmp[1:])
32             return
33 
34         for s in self._sizes: self.serial(total-s, s, tmp[:])
35 
36 
37 
38 if __name__ == '__main__':
39     from time import time
40     total = 1000
41     lengths = [260, 230, 190, 140, 80]
42     time0 = time()
43     cs = LineSerial(total, lengths)
44     print time() - time0
45     print u'總組合數: %s' % len(cs.result)
46     print u'serial 遞迴次數: %s' % cs.serial_times
47     #for i in cs.result: print i

使用 genetic algorithm 來求解非線性問題。如 y = [ sin(1*x0) * sin(2*x1) ] + ... + [ sin(49*x48) * sin(50*x49) ]，求 y 的最大值

問題描述： 指定 0,1,2,.........49 等50個數字給 x0~x49(不可重複)，且

y = [ sin(1*x0) * sin(2*x1) ] + [ sin(3*x2) * sin(4*x3) ] + ... + [ sin(49*x48) * sin(50*x49) ]

請求解 y 之最大值?

本問題我使用 pyevolve 函式庫來幫我處理染色體的突變、重組、交配工作。我只需要提供目標函數(eval_func)的計算方式即可。本問題我的 y 最佳解是 20.4676 ，決策變數是 [33, 26, 36, 16, 45, 28, 37, 1, 19, 2, 25, 14, 0, 22, 6, 17, 35, 24, 11, 12, 27, 42, 49, 32, 13, 20, 23, 43, 41, 30, 4, 9, 21, 3, 10, 34, 38, 15, 18, 5, 47, 39, 44, 40, 8, 7, 31, 48, 46, 29] 。

 1 from pyevolve import G1DList
 2 from pyevolve import GSimpleGA
 3 from pyevolve import Selectors
 4 from pyevolve import Statistics
 5 from pyevolve import DBAdapters
 6 import pyevolve
 7 from math import sin
 8 
 9 """ 指定 (0,1,2,.........49 等50個數字不可重複）給 x0~x49，例如  x0=12,  x1= 33, ....
10     y = [ sin(1*x0) * sin(2*x1) ] + [ sin(3*x2) * sin(4*x3) ] + ... + [ sin(49*x48) * sin(50*x49) ]
11     求解 y 之 最大值＝?
12 """
13 
14 def eval_func(chromosome):
15     score = 20.0 #為了不讓 score 的值小於 0，因為 pyevolve 不支援適存值小於 0 。
16     list = map(lambda a,b: (a, b), xrange(50), chromosome)
17     list.sort(key=lambda a: a[1])
18     for i in xrange(25):
19         score += sin((2*i+1)*list[i*2][0]) * sin((2*i+2)*list[i*2+1][0])
20 
21     return score
22 
23 # Enable the pyevolve logging system
24 pyevolve.logEnable()
25 # Genome instance, 1D List of 50 elements
26 genome = G1DList.G1DList(50)
27 # Sets the range max and min of the 1D List
28 genome.setParams(rangemin=0, rangemax=500)
29 # The evaluator function (evaluation function)
30 genome.evaluator.set(eval_func)
31 # Genetic Algorithm Instance
32 ga = GSimpleGA.GSimpleGA(genome)
33 # Set the Roulette Wheel selector method, the number of generations and
34 # the termination criteria
35 ga.selector.set(Selectors.GRouletteWheel)
36 ga.setGenerations(5000)
37 ga.terminationCriteria.set(GSimpleGA.ConvergenceCriteria)
38 # Sets the DB Adapter, the resetDB flag will make the Adapter recreate
39 # the database and erase all data every run, you should use this flag
40 # just in the first time, after the pyevolve.db was created, you can
41 # omit it.
42 sqlite_adapter = DBAdapters.DBSQLite(identify="ex1", resetDB=True)
43 ga.setDBAdapter(sqlite_adapter)
44 # Do the evolution, with stats dump
45 # frequency of 20 generations
46 ga.evolve(freq_stats=20)
47 # Best individual
48 print ga.bestIndividual()