PageRank



轉移公告

計劃把 http://blog.hoamon.info/ 文章全部轉移至 http://www.hoamon.info/blog/ 這裡,而本 Blogger 站台的文章近 500 篇,我預計在 2014-12-31 前移轉完畢,完成後 http://blog.hoamon.info/ 將只作代轉服務,一律把舊連結如 http://blog.hoamon.info/index.html 轉成 http://www.hoamon.info/blog/index.html ,敬請舊雨新知互相走告。

新文章只發佈在 http://www.hoamon.info/blog/

何岳峰 敬上

2011年9月16日 星期五

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

之前的作法是將 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])

2011年9月12日 星期一

賽德克‧巴萊觀前感 - 談第一、二次霧社事件及抗日那些事

聲明: 既然是觀前感,就表示我還沒看過電影,所以本文不是談魏導演的手法及電影優劣,只是要談談它的背景故事,請不要拿本篇文章結論來當作該看或不看電影的論點。我是一定會去看「賽德克‧巴萊」,為的不是「莫那‧魯道是個英雄,能發揮臺灣人精神」? 而是為了一部花費 7 億打破臺灣電影史紀錄的電影。常看電影的人應該都知道,不是花大錢的電影就比較好看,使錢也是一種門道,我就想看看臺灣導演會不會使錢。

筆者在國史館臺灣文獻館當了二年的替代役,在這個地方工作所得到的好處之一,是打破了我過去對歷史資料來源的迷思。

原來在歷史課本上所看到的內容,是有人在機關公文中尋尋覓覓拼湊出來的,或者是說史料內容除了口述、古籍、文獻、紀要、遺跡…這些外,居然也可以是從前朝機關往來文書中汲取而來,而這種地方來的史料,是很花費功夫的,可能看了涵蓋 2 年期間的數千份公文,卻只找到 2 張圖:「太魯閣族的衣著、紋面情形。」。

從這兩張圖中,我們才知道要重演 1900 年左右的故事時,裡面的人該穿什麼樣的衣服、紋什麼樣的面。當然這是考據史實的拍法,如果不講究,拿塊黑黑紅紅花花的布套上去,我想臺灣也沒多少人會知道這是錯的,或許連現今太魯閣族人也不見得認得出來。因為這是 110 年前的事,服飾花樣會進步,尤其在這 110 年之間,臺灣經歷了兩個統治者,他們無不想抹去大家對前朝的記憶。

既然執政者能依優勢抹去大家對前朝的記憶,所以他們所留下的檔案公文,有些也不盡然是真的,那些公務員擬公文時,也知道這將來會成為證據,所以不該寫的,就不會寫了。我們要研究歷史的話,也得有這份體認,要從多方管道得來資訊,並作交叉驗證。

好了,我總要進入正題了。

在臺灣有讀過書的人,都知道莫那‧魯道是抗日英雄,與他最相關的歷史就是第一次霧社事件。不過,課本沒講的是:「有其他原住民部落帶著日本人一起打賽德克族的德固達雅分支(備份)、之前莫那‧魯道也幫著日本人打泰雅族(備份)以及第二次霧社事件是原住民族彼此相殺」。

為什麼在我們印象中,乃原住民族不滿日本政府的欺壓,起而反抗而來? 怎麼也有其他原住民是站在日本那一邊,甚至連莫那‧魯道也曾跟日本站同一邊。到底他還是不是抗日英雄呢?

他是抗日英雄這件事,其實並不重要,重要的是我們政府希望我們相信這件事,而且起而效尤,這樣才能延續執政權的正當性,是他們讓我們遠離日本暴政,請詳閱這篇格文

要讓人民效尤抗日,就得找個偉人,述說他的事蹟,去除枝節得到純正連貫易消化的故事,讓人民好吸收。這像不像置入性行銷呀! 原來我們政府幾十年前就在作了。

但是撥開那些政治實體的詞語,我們把焦點放在人身上,從這些歷史中,我只看到一群人為了資源,而必須從別人那邊奪取。

像是:「日本在明治維新後,需支應日本社會生活水準提升而效法大英帝國所採取的殖民帝國主義」、「中國越族被中原漢族趕到海峽另一邊而與臺灣平埔族融合」、「原住民服從日本以換取其他原住民族的獵場」。

歷史重覆上演著人類在地球上巧取豪奪資源後,再分配給某一部份人享用的故事。而且結局往往是產業層次較高的社群贏了。

從「槍炮、病菌與鋼鐵」一書得來的觀念:「地理能決定人類社會的優劣(而不是人類基因決定優劣)」,所以在一塊土地上,如果它養成一個國家實體,具有法治、軍隊、領袖的話,那表示其他人種來這塊地,在假以時日後,也同樣發展的了。這個論點,告訴我們如果給 1683 年的臺灣平埔族人、 1930 年的臺灣原住民人更多時間,他們也能同樣發展至現在的產業層次。但是中國越族、漢族來了、日本也人來了,他們被迫學習別人的文化、語言。而現在呢?

現今的臺灣人身上的血液多半都有越族、漢族、平埔族、高山族甚至日本人的血液,你如果把自己定位在「被欺壓的平埔族或是高山族」上,那你如何忽視「越族、漢族」的血源,就像你支持「莫那‧魯道抗日是體現臺灣人精神一樣」,你如何看待那些協助日本的原住民族,而且他們的後代目前多半還住在霧社,是真真實實地存在,難道他們就不是臺灣人嗎? 我不這麼認為。只要是住在臺灣(含澎湖、金門、馬祖、綠島、蘭嶼、小琉球),他就應該是個臺灣人,不須宣誓、不用驗血,簡單講,我採屬地主義。

從資源的角度來看莫那‧魯道,我們就可以了解他之前服從日本但後來卻反抗日本的源由,其實就是讓他的族人們過得好(雖然不是他親口說的,是我以同理心猜想的)。他一開始也知道日本的產業層次高、人數多,反抗只是以卵擊石,豪無勝算,直到後來得罪了日本人,只好用生命來賭一把,不過結果你知道的:「他輸了」。歷史沒法重來,所以我們不知道,如果他當時忍下了,是否還是會被滅族? 很多時候,領袖也不知道該不該作,他只能賭。

如果我們人類社會能朝向與棲地均衝發展,資源有多少就用多少,不用擴張領地來掠奪資源,應該會少了很多殘酷的戰爭。只是這目標作不到,因為「全球化」及「氣候變遷」讓我們很難作到「與棲地均衝發展」。

所以,我想有生之年可能還是會面臨到資源分配不足的事情,唉~ 那該怎麼因應呢? 我還沒想到。還是去看電影吧! 它應該沒那麼難讓人懂。

2011年9月10日 星期六

終於能在臺灣看到 NFL 例行賽轉播

筆者從小就是個不愛運動的小孩,一直覺得這是不動大腦、四肢發達的人才作的事,這個信念一直維持到大一時期。

我在唸大學時,已經是個只愛待在家裡鬼混的小孩,因為高中時大多把該玩的都玩過了。於是,我大學花在第四台的時間還不少,一開始看得當然是電影而已,而 ESPN 很少轉到,直到某天轉到舊金山淘金者的美式足球季後賽。過去只在電影中大略見識過,對其比賽規則當然是不懂,也因筆者對於不懂的事,就愛搞懂,也不管 EPSN 只有原音轉播,反正我就是一邊看一邊猜。看著看著也略知一二,就這樣一路看到 Brett Favre 帶著 Green Bay 拿下 '96 超級盃。

等到美式足球季結束後,我開始另尋它種運動比賽節目,而台灣大聯盟正巧於 '97 正式開打,一開始都是袁定文當球評的,而他剛開始作球評時,花了不少時間在解釋棒球比賽的門道,不像我以前看國際賽時,只專注在國家隊有沒有安打、有沒有得分上。於是,我開始對「運動比賽」改觀了,它不像我所認為的是「四肢發達」的人才搞的玩意,沒有腦袋還真是混不出局面。當時,我對棒球可是深深地著迷,不但看直播,也看重播,有時一場比賽我看了三遍。是的,你猜到了,我大學很少在唸書的。

對「運動」改觀後,我就百無禁忌了,冰球(Hockey)、足球(Soccer)、板球(Cricket)都看,就是不看籃球,因為我不喜歡跟風。甚至,我還買了 '97 NHL 的電腦遊戲,那個老闆還說:「真沒想到,這遊戲會有人買。」

因為袁博士當時也在年代台的 Catch the fever 節目擔任球評轉播美國大聯盟,所以我後來對美國棒球的了解反而比美式足球還深了。

然而,因為袁博士及王建民所帶來的美國職棒熱潮間接地讓 EPSN 臺灣台壓縮了其他球類比賽的預算,使得我看洋基比賽看到吐,也沒什麼機會再看到美式足球例行賽了。

直到今年(2011), ASN 運動台作到了「直播 NFL 例行賽」的服務,使用中華電信 MOD 只要多花 11 塊,就能升級到豪華特餐,這其中包含了 ASN 運動台。

剛剛我在 MOD 上看了 2011 NFL Kickoff 綠灣包裝工 V.S 紐奧良聖徒,喚起了十幾年前的記憶。我想我一定是又老了。
Related Posts Plugin for WordPress, Blogger...