十月 1, 2011

hoamon's sandbox
hoamon
hoamon's sandbox is about »

tag cloud

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

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

十二月 20, 2007

hoamon's sandbox
hoamon
hoamon's sandbox is about »

tag cloud

» 原來這就是背包問題呀!

日前(好久前了)提了一個讀研究所時所解決的問題,那時還滿自傲的,畢竟在讀土木的同學中,還沒看到有人會解。

那是一個解決鋼筋裁切的廢料量最佳化所衍生的難題。也就是要列出一根原料鋼筋要切成工地用尺寸的組合問題,如:18公尺的鋼筋若要切成 10, 7, 5, 4, 3 公尺長的鋼筋,則有那幾種切法。

Thinker 提了一個很好的方法來計算它的組合數有多少。不過,因為我要的是有那幾種組合,所以不曉得他的方法能否套用。

之前,我是用 Perl 來解這個問題的,不過,程式已經找不到了,不是我沒作版本控制,那時候用的是 CVS,然而在歷經多次系統安裝, CVS 的儲存庫已經不知在那了。

所以,我用 Python 重寫這個方法。有兩種解法,第一種是用我之前的觀念來解的。第二種是昨天想的,不過,第二種卻比較沒效率。

 1 #!/usr/bin/env python
 2 # -*- coding: utf8 -*-
 3 def cut(length, k, tmp):
 4     if k == sizeslen:
 5         if length >= sizes[-1]:
 6             return
 7         else:
 8             tmps.append(tmp[:])
 9             return
10
11     comp = int(length/sizes[k])
12     for i in xrange(comp+1):
13         j = comp - i
14         tmp[k] = j
15         cut(length-sizes[k]*j, k+1, tmp[:])
16
17 from time import time
18 import sys
19 if __name__ == '__main__':
20     bar = float(sys.argv[1])
21     sizes = [float(s) for s in sys.argv[2:]]
22     sizes.sort()
23     sizes.reverse()
24     sizeslen = len(sizes)
25     tmps = []
26     tmp = [0,]*sizeslen
27     time0 = time()
28     cut(bar, 0, tmp[:])
29     print time() - time0
30     print len(tmps)

第二種:
 1 #!/usr/bin/env python
 2 # -*- coding: utf8 -*-
 3 def cut(L, x, k, tmp, num):
 4     num[0] += 1
 5     diff = L-x[0]
 6     if diff > mat[0][0]:
 7         if tmp[x[1][0]] != 0: return
 8         else: tmp[x[1][0]] = x[1][1]
 9     elif diff < mat[0][0] and diff >= 0:
10         if tmp[x[1][0]] != 0: return
11         else: tmp[x[1][0]] = x[1][1]
12         tmps.append(tmp[:])
13         return 
14     else:
15         return
16     for (i, s) in enumerate(mat[k+1:]):
17         cut(L-x[0], s, i+k+1, tmp[:], num)
18         
19 def sort_by_value(k):
20     return (k, k[0])
21
22 from time import time
23 import sys
24 if __name__ == '__main__':
25     time0 = time()
26     bar = float(sys.argv[1])
27     sizes = [float(s) for s in sys.argv[2:]]
28     lensizes = len(sizes)
29     tmps = []
30     mat = []
31     for (i, s) in enumerate(sizes):
32         comp = int(bar/s)
33         for j in xrange(1, comp+1):
34             mat.append((s*j, (i, j)))
35     mat.sort(key=sort_by_value)
36     tmp = [0, ]*lensizes
37     num = [0]
38     for (i, m) in enumerate(mat):
39         cut(bar, m, i, tmp[:], num)
40
41     print time() - time0
42     print len(tmps)
43     print num[0]

新的觀念是把需求尺寸的倍數尺寸拿來當切割尺寸。如:10公尺要給7, 5, 3, 2 來切的話,我先把需求尺寸變成 7, 10, 5, 9, 6, 3, 10, 8, 6, 4, 2 等尺寸來切,如果在切的過程,剛好又遇到擁有相同因數的尺寸則跳過,像是10公尺已經被 8 切掉了,後來又遇到 2 的話,就停止處理。

在人工演練的過程中,覺得第二種方法所跑的迴圈數比較少,然而寫成程式後,效率卻比較差,且實際的迴圈數也比較多。

十月 29, 2007

hoamon's sandbox
hoamon
hoamon's sandbox is about »

tag cloud

» 小(大)學生一定要有電腦及網路才可以畢業!

這陣子燦坤、家樂福、全國電子推了幾個廣告,訴求就是「威脅」、「利誘」、「柔性呼喚」要開學的學生或是學生家長,在學涯生活中一定得買台電腦,要不然學習會輸別人的。

這是商人的詭計,與情人節買花、普渡要旺旺的道理是一樣的。但在聽我說下去前,請你們先去看看一個高級知識份子的文章「不要學電腦,不要學英文」,以下三個網址的內容都一樣的:
http://home.pchome.com.tw/internet/intro33/new_page_8.htm
http://blog.yam.com/eyesfun/article/8155310
http://www.pczone.com.tw/vbb3/thread/21/71021/

看完了嗎?還沒,請記住,我的文章沒他好,如果你不看他的,卻繼續看我的,那代表你沒眼光。再給你 3 分鐘。

曾在南投縣北山國中上過一個學期的資訊課。學期開始,我就為同學們介紹什麼是資訊、什麼是電腦,電腦不等同資訊;資訊也不等同電腦,所以我們上課其實不是一直在用電腦的,我會上點數學、講些社會上應用電腦資訊的例子,像是快遞如何透過資訊系統協助送貨、 7-11 如何管理庫存…之類的。

而最重要的一點是,我出的作業,一定要在課堂上作完。

因為我知道不是每個小朋友家裡都有電腦及網路的。台灣雖然是開發中國家,雖然是資訊產品的最大出口國之一,但還是有人家裡不能買或不願買一台電腦,辦條網路線的。

家裡沒有電腦,我是一點都不覺得有什麼關係的,尤其對小朋友來說,電腦對他們一點都不重要。何必為了 1 個月花 3 小時作一個文書處理作業買台電腦回家呢!況且如果老師真的出了電腦作業,也真的要求小朋友帶回家作出來,那也沒有關係,至少對市區學生來說,我們多半都有圖書館,圖書館裡有電腦、網路可以使用,像是欣榮紀念圖書館中還有 Ubuntu 可以用呢!又或者學校的電腦教室也可以使用呀!要不然學費中的電腦使用費是繳心酸的嗎(但大部份的家長其實不知道電腦使用費有一部份是花在教師電腦及全校網路連線費)?

但以上所說,不代表現在學校老師了解這個現象

我的姪子、姪女目前就讀南光國小,就常遇到老師要他們回家打報告、找資料,打報告是沒問題啦!因為家裡有電腦,但找資料的話,卻因沒有網路,所以他們就會跟家裡大人說:「要到姑丈家家,或是舅舅家用網路。」於是 3 分鐘找資料,剩下的時間花網路遊戲。

所以當我聽到老師又出網路作業回家作的時候,心裡就不高興。對小朋友來說,在網路上找資料一點都不重要。重要的應該是教他們「如何利用資訊」。甚至我還覺得根本不要教所謂的文書處理軟體、影像處理軟體、網頁製作軟體等,這些東西對他們未來的益處不若「如何利用資訊」來得重要。

資訊有很多形式,紙本的、口述的、數位的、網路的…,資訊的儲存位置也有很多地方,其中對小朋友(其實對大朋友也是)最有幫助的是圖書館。但學校老師常常不教(或許是他們也不會運用圖書館),只(會)用 Google 找資料的人是愚蠢又懶惰的。

而事實上,許多國中小電腦老師也只會教小朋友文書處理軟體,於是國小教一遍,國中又教一遍,搞得小朋友認為電腦就是這樣子,除了網路遊戲外,其他都是一整個無聊。

如果可以,我希望電腦可以晚一點教。

拿我親身的實例來說:高四(1995)時,我爸就買了一台 Win95 的電腦,要拿來幹什麼,我不知道,但當我上大學時,它成了我寫作業的工具,利用它來打報告及玩 NHL 97 ,一直到研究所,我才踏入重灌電腦/程式設計的行列,我還記得高中工藝課看不懂老師寫的 basic 程式,只好看同學打三國志三的情景,但比起這些國高中就有在玩電腦的同學,現在與他們相比,在電腦科學/應用上並不輸他們呀。

如果可以,我真的希望電腦可以晚一點教,因為有太多更重要的東西要學了。

biggo.com.tw

A Django site.