- 從游戲開(kāi)始:
- 第二天:
- 守夜人:
- 終篇:
- 課后檢討:
一切從游戲開(kāi)始:
- 故事虛構(gòu), 是從一個(gè)真的游戲再綜合新聞組的內(nèi)容而來(lái).
緣起:
這是一個(gè)晴朗的星期六下午, 你悠閑地在網(wǎng)上瀏覽. 忽然間你看到一個(gè)留言板上的小游戲. 它很簡(jiǎn)單,
問(wèn)題是: 把五個(gè)數(shù)字 56789, 放到 {{{[][][] * [][], 令結(jié)果最大.
你最先對(duì)自己說(shuō): "這有什么難, 把最大的放到最大位數(shù)那里就行了." 你再心算了一下, 也許不對(duì). 每個(gè)結(jié)果要看其他位置上放了什么數(shù)才行. 你開(kāi)始覺(jué)得有些興趣了, 反正你正在學(xué)一種好玩的編程語(yǔ)言, 何不練習(xí)一下呢?
於是你開(kāi)出你心愛(ài)的 Python, 開(kāi)始思考: "其實(shí)我要的是一個(gè)程式, 我給它各種數(shù)字的組合, 然后它自動(dòng)幫我找出最大的一個(gè). 如果我傳入 1,1,1,1,1 和 1,1,1,1,2, 它會(huì)知道要算 111 * 11 和 111 * 12, 求出較大的是 111 * 12 并輸出這個(gè)組合以及其乘積. 這個(gè)程式并不難嘛."
1 # calc.py
2 def calc(seq):
3 maximum = 0
4 max_item = []
5 for i in seq:
6 product = (i[0]*100 + i[1]*10 + i[2]) * (i[3]*10 + i[4])
7 if product > maximum:
8 maximum = product
9 max_item = i
10 elif product == maximum:
11 max_item += ','+i
12 return max_item, maximum
13
14 seq = [ [5,6,7,8,9], [5,6,7,9,8] ]
15 max_item, maximum = calc(seq)
16 print "Maximum at", max_item, ",product", maximum
你試了一下,
$python calc.py
Maximum at [5, 6, 7, 9, 8] ,product 90160
沒(méi)問(wèn)題. 現(xiàn)在你只要給出所有的排列即可. 你打了幾行, 覺(jué)得 [5,6,8,7,9] 這樣打太辛苦了, 而且用 i[0]*100 + i[1]*10 ... 的方法好像太難看了, 因此你有必要做一次修改. 好, 用字串吧. "56789", 這樣輸入時(shí)較方便, 而且 int("567") * int("89") 要好看得多, 也應(yīng)該快些. 另外你也把程式改得更短, 看起來(lái)像是個(gè)有經(jīng)驗(yàn)的人所寫(xiě).
1 # calc.py
2 def calc(seq, where):
3 maximum, max_item = 0, []
4 for i in seq:
5 product = int(i[:where]) * int(i[where:])
6 if product > maximum:
7 maximum, max_item = product, i
8 elif product == maximum:
9 max_item += ','+ i
10 print "Maximum at", max_item, ",product", maximum
11
12 if __name__ == "__main__":
13 seq = [ "56789", "56798" ]
14 where = 3
15 calc(seq,where)
嗯, 好些了. 那句 if __name__ == "__main__" 是為了將來(lái)你把 calc.py 做為模組來(lái)用時(shí)而設(shè)的. 在別的程式中用 import calc 的話那幾行就不會(huì)運(yùn)行了.
現(xiàn)在你可以隨自己的意來(lái)解更普遍的問(wèn)題, 比如 123 放在 []*[][], 或是 1234567 放在 [][][][]*[][][] 這樣的問(wèn)法. 現(xiàn)在你開(kāi)始輸入排列了. "56789", "56798", "56879", "56897", .......... 沒(méi)多久你又覺(jué)得自己太愚蠢了, 為什么不叫電腦程式自動(dòng)產(chǎn)生這些無(wú)聊的排列呢? 56789 一共有 5! 也就是 120 種排列方法呢! 如果你想算 123456789 的話, 用手輸入可能要用去一生的時(shí)間!!
於是你開(kāi)始想如何產(chǎn)生排列的算法了. 用循環(huán)就可以了, 不過(guò)循環(huán)會(huì)產(chǎn)生重覆的組合, 譬如 555*55. 但我們可以加些條件式進(jìn)去把重覆項(xiàng)拿走. 於是你有了第一個(gè)程式解.
1 #permute1.py
2 def permute(seq):
3 result = []
4 for a in seq:
5 for b in seq:
6 for c in seq:
7 for d in seq:
8 for e in seq:
9 if a!=b and a!=c and a!=d and a!=e and \
10 b!=c and b!=d and b!=e and \
11 c!=d and c!=e and d!=e:
12 result.append(''.join([a,b,c,d,e]))
13 return result
14
15 seq = list("56789")
16 where = 3
17 thelist = permute(seq)
18 import calc
19 calc.calc(thelist,where)
你小心地記著用 ''.join() 的方法產(chǎn)生字串要比用 a+b+c+d 快, 同時(shí)也認(rèn)為用 import calc 的方式會(huì)讓你更容易為不同的地方做些速度的微調(diào). 你開(kāi)始運(yùn)行程式了:
%python permute1.py
Maxmum at 87596 ,product 84000
你成功了. 啊哈, 你認(rèn)為可以貼到留言板上去領(lǐng)賞了. 經(jīng)過(guò)一些考慮后, 你覺(jué)得還是要做到更普遍的功能, 就是讓用戶輸入排列多少個(gè)數(shù)字, 怎樣分割. 研究了一下程式, 你覺(jué)得用循環(huán)好像無(wú)法達(dá)到要求, 因?yàn)槟闶虑安⒉恢酪哦嗌賯€(gè)數(shù)字, 因此你不知道要寫(xiě)多少個(gè)循環(huán)才夠. 面對(duì)這種情況, 你好像只能用遞歸的方法了.
你知道如何求得, 例如, 5 個(gè)數(shù)字的排列: 先挑一個(gè)數(shù), 有五種選擇; 當(dāng)選定了一個(gè)數(shù)之后挑第二個(gè)數(shù)時(shí)只剩下四個(gè)選擇, 依此類推. 因此五個(gè)數(shù)共有 5*4*3*2*1 共 120 個(gè)排列. 當(dāng)你面對(duì) "56789" 這五個(gè)數(shù)的排列問(wèn)題時(shí), 你先挑出一個(gè)數(shù), 例如 6, 那剩下的便是一個(gè)四個(gè)數(shù)字的排列問(wèn)題了. 就是說(shuō), 56789 的排列可以簡(jiǎn)化 (或是簡(jiǎn)單復(fù)雜化:p) 成字頭為 5 的所有排列加上字頭為 6 的所有排列加字頭為 7 的所有排列加字頭為 8 的所有排列再加字頭為 9 的所有排列. 想通了這點(diǎn), 你決定用遞歸函數(shù)來(lái)寫(xiě)程式, 先依次在 56789 中選出 5, 然后把剩下的 6789 當(dāng)做是一個(gè)新的求四位數(shù)排列的問(wèn)題再次調(diào)用函數(shù), 以得到所有以 5 為字頭的排列; 再選出 6, 剩下的 5789 調(diào)用函數(shù). 而每次求 6789 或是 5789 的排列時(shí)再把它簡(jiǎn)化成另一個(gè)求 3 個(gè)數(shù)字的排列問(wèn)題, 直到要求的排列只剩下一個(gè)數(shù).
以下就是你的函數(shù), 不過(guò)你還不知道它到底是不是正確的, 因?yàn)閷?xiě)遞歸函數(shù)很易出錯(cuò), 因此你要先試一下.
1 #permute2.py
2 def permute(seq):
3 l = len(seq)
4 if l == 1:
5 return [seq]
6 else:
7 res=[]
8 for i in range(len(seq)):
9 rest = seq[:i] + seq[i+1:]
10 for x in permute(rest):
11 res.append(seq[i:i+1] + x)
12 return res
13
14 seq = list("1234")
15 thelist = permute(seq)
16 thelist = [ ''.join(x) for x in thelist ]
17 print thelist
你運(yùn)行后得到以下的結(jié)果:
$ python permute2.py
['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314',
'2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421',
'4123', '4132', '4213', '4231', '4312', '4321']
看來(lái)是正確的. 但有沒(méi)有辦法再快一些呢? 你想了半天, 終於發(fā)現(xiàn)其實(shí)你不必等到 l = 1 的時(shí)候才有所動(dòng)作, 你可以在 l = 2 的時(shí)候就干些事了. 因?yàn)槟阒?l = 2 的話, 排列一定是 [ [0,1], [1,0] ] 的, 這樣你起碼可以用些力氣幫電腦一把. 當(dāng)然如果你把 l = 3 的排列也寫(xiě)出來(lái)更好, 但寫(xiě)到 l = 4 或以上大可不必了. 這種幫它一下的做法在程式優(yōu)化中的學(xué)名是 unroll, 你隱約記得是學(xué)過(guò)的. 好, 現(xiàn)在你有另一個(gè)程式了.
1 #permute3.py
2 def permute(seq):
3 l = len(seq)
4 if l <= 2:
5 if l == 2:
6 return [ seq, [seq[1], seq[0]] ]
7 else:
8 return [seq]
9 else:
10 res=[]
11 for i in range(len(seq)):
12 rest = seq[:i] + seq[i+1:]
13 for x in permute(rest):
14 res.append(seq[i:i+1] + x)
15 return res
16
17 seq = list("12345")
18 thelist = permute(seq)
19 thelist = [ ''.join(x) for x in thelist ]
20 print thelist
現(xiàn)在你可以正式測(cè)試了. 你把 permute3.py 改了一下, 以便可以從命令行取得數(shù)字以及分割方法. 程式變成下面的樣子, 同時(shí)你也對(duì) permute2.py 做了相同的修改.
1 #permute3.py
2 def permute(seq):
3 l = len(seq)
4 if l <= 2:
5 if l == 2:
6 return [ seq, [seq[1], seq[0]] ]
7 else:
8 return [seq]
9 else:
10 res=[]
11 for i in range(len(seq)):
12 rest = seq[:i] + seq[i+1:]
13 for x in permute(rest):
14 res.append(seq[i:i+1] + x)
15 return res
16
17 import sys, calc
18 seq = list(sys.argv[1])
19 where = int(sys.argv[2])
20 thelist = [ ''.join(x) for x in permute(seq) ]
21 Print 'Got', len(thelist), 'items.'
22 calc.calc(thelist, where)
你開(kāi)始試行了. 用 time 方式來(lái)看程式到底運(yùn)行了多長(zhǎng)時(shí)間吧.
$ time python permute2.py 56789 3
Got 120 items.
Maximum at 87596 ,product 84000
real 0m0.057s
user 0m0.050s
sys 0m0.000s
$ time python permute3.py 56789 3
Got 120 items.
Maximum at 87596 ,product 84000
real 0m0.040s
user 0m0.030s
sys 0m0.010s
呵, 不錯(cuò). 修改了的就是快些. 到了這個(gè)地步, 你開(kāi)始覺(jué)得好奇了. 像求排列這樣一個(gè)常見(jiàn)的問(wèn)題, 不知道別人都是怎樣做的呢. 也許應(yīng)該到網(wǎng)上去找找看, 或者有一兩個(gè)已經(jīng)寫(xiě)好的程式片斷可以抄的. 你可不想弄錯(cuò)一個(gè)原來(lái)己經(jīng)有標(biāo)準(zhǔn)答案的問(wèn)題. 把 permute2.py 貼上留言板或者會(huì)令自己看起來(lái)像一個(gè)三流的程式設(shè)計(jì)員, 這可是你最不想見(jiàn)到的. 於是你在網(wǎng)上到處搜尋. 不過(guò)似乎都是以遞歸算法為主的, 直至用了一些時(shí)間, 你終於在 ASPN: 的網(wǎng)上程式碼收集站上看到了這一個(gè)片斷:
1 # permute4.py
2 def permute(seq, index):
3 seqc = seq[:]
4 seqn = [seqc.pop()]
5 divider = 2
6 while seqc:
7 index, new_index = divmod(index,divider)
8 seqn.insert(new_index, seqc.pop())
9 divider += 1
10 return ''.join(seqn)
作者聲稱這個(gè)算法的量級(jí)是 O(n) 的. 你覺(jué)得難以置信, 但不妨一試. 由於你理解到這個(gè)函數(shù)每次只傳回排列中的某一項(xiàng), 因此你寫(xiě)了個(gè)小程式去驗(yàn)算它.
1 # test.py
2 from permute4.py import permute
3
4 seq = list("1234")
5 for i in range(30):
6 print permute(seq, i),
試驗(yàn)一下:
$ python test.py
1234 1243 1324 1423 1342 1432 2134 2143 3124 4123 3142 4132 2314
2413 3214 4213 3412 4312 2341 2431 3241 4231 3421 4321 1234 1243
1324 1423 1342 1432
測(cè)試顯示這個(gè)函數(shù)沒(méi)問(wèn)題. 但它怎樣做到的呢? 你研究了一下, 每個(gè)不同的 index 值都傳回唯一的排列, 而且大過(guò) n! 的 index 會(huì)從頭來(lái)算起, divider 每次都要增加一, 列表的排法又是按商余數(shù)來(lái)重整. 唉, 不得要領(lǐng). 嗨! 管它呢. 反正能用就行了. 於是你修改 permute4.py, 加入一個(gè)新的函數(shù)求 factorial, 這樣就可以調(diào)用 permute 得到所有的排列. 并進(jìn)行計(jì)時(shí). 你用了更多的數(shù)字, 以便速度的差別更明顯些.
1 # permute4.py
2 def permute(seq, index):
3 seqc = seq[:]
4 seqn = [seqc.pop()]
5 divider = 2
6 while seqc:
7 index, new_index = divmod(index,divider)
8 seqn.insert(new_index, seqc.pop())
9 divider += 1
10 return ''.join(seqn)
11
12 def fact(x):
13 f = 1
14 for i in range(1,x+1):
15 f *= i
16 return f
17
18 import sys, calc
19 seq = list(sys.argv[1])
20 where = int(sys.argv[2])
21 n = fact(len(seq))
22 thelist = [ permute(seq, i) for i in range(n) ]
23 print 'Got', len(thelist), 'items.'
24 calc.calc(thelist, where)
$ time cpython permute3.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002
real 0m0.461s
user 0m0.440s
sys 0m0.020s
$ time cpython permute4.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002
real 0m0.389s
user 0m0.370s
sys 0m0.010s
哇! 的確不是蓋的. 很好, 而且現(xiàn)在你知道了別人不知的新答案. 就把它貼上去罷. 就在你決定的時(shí)候按鈕之際, 你到底猶豫了: "我對(duì)這個(gè)算法不是很了解, 如果別人問(wèn)起的話怎樣回答呢? 這會(huì)讓我像個(gè)東抄西抄的小偷呢! 不, 要不我要明白它的原理, 不然就自己做一個(gè)比它更好的." 你覺(jué)得壯志無(wú)限.
但是現(xiàn)在已經(jīng)很晚, 你要去睡了. 無(wú)奈你在床上反覆地思考著更好的方法, 你整個(gè)晚上都沒(méi)睡好.
待續(xù)......
第二天:
你醒來(lái)第一件事, 洗臉?biāo)⒀? 編程愛(ài)好者并不一定和終日蓬頭垢面同義. 然后呢, 看看電視報(bào)紙, 做些公益活動(dòng), 今天是禮拜天嘛. 廢話少說(shuō), 終於你在電腦前坐下, 登入了你喜愛(ài)的 Slackware / RedHat / Redflag / Mandrake / Debian / WindowsXP / Chinese2000 / DOS / Solaris/ AIX / Unicos / OSX [作者按: 請(qǐng)依實(shí)際情況增刪, 但千萬(wàn)拜托不要把 SCO 也加進(jìn)來(lái)], 這些都是 Python 能夠運(yùn)行的平臺(tái).
你記起你以前學(xué)到遞歸時(shí)聽(tīng)過(guò)的話: 任何遞歸/回溯函數(shù)都可以還原成非遞歸形式的. 於是你決定用你自己的方式一試. 你默念著求排列的方法, 5 個(gè)數(shù)取一個(gè), 剩下 4 個(gè), 再取一個(gè), 剩下 3 個(gè) .... 於是你寫(xiě)出一個(gè)新的程式, 和最初的一個(gè)很相像:
1 # permute5.py
2 def permute(seq):
3 result = []
4 for i in seq:
5 seq1 = seq[:]
6 seq1.remove(i)
7 for j in seq1:
8 seq2 = seq1[:]
9 seq2.remove(j)
10 for l in seq2:
11 seq3 = seq2[:]
12 seq3.remove(l)
13 for m in seq3:
14 seq4 = seq3[:]
15 seq4.remove(m)
16 result.append(''.join([i,j,l,m,seq4[0]]))
17 return result
18
19 print permute(list("12345"))
這個(gè)程式依次創(chuàng)建 5, 4, 3, 2, 1 個(gè)數(shù)的列表, 每個(gè)都不包括之前被選的數(shù)字, 然后把 5 個(gè)數(shù)合起來(lái)完成一種排列.當(dāng)然, 你還有空間做 unroll. 但現(xiàn)在問(wèn)題在於, 你對(duì)程式的要求是事先并不知道要求多少個(gè)數(shù)字的排列, 就是你不知道要寫(xiě)幾個(gè) for 才夠. 但現(xiàn)在你認(rèn)為有一個(gè)好辦法: 既然 Python 是動(dòng)態(tài)的, 它可以執(zhí)行自己寫(xiě)出來(lái)的編碼, 為什么不叫它自己幫自己來(lái)寫(xiě)這個(gè)循環(huán)程式以完成工作呢? 你覺(jué)得這種讓程式來(lái)為自己寫(xiě)程式的想法很科幻也很妙, 而且讓你記起了以前聽(tīng)到很多資深程式員愛(ài)用的 m4 宏語(yǔ)言. 於是你趕緊試了一個(gè). 你認(rèn)為可以用 counter0, counter1, counter2...來(lái)代替 i, j, l, m...的循環(huán)子命名法.
1 # permute5.py
2 def genfunc(n):
3 head = """
4 def permute(seq0):
5 result = [] """
6 boiler = """
7 for counter%i in seq%i:
8 seq%i = seq%i[:]
9 seq%i.remove(counter%i)"""
10 for i in range(1,n):
11 space = ' '*i
12 head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i)
13 temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)])
14 head = head + '\n' + space + " result.append(''.join([%s]))"%(temp)
15 return head + '\n return result\n'
16
17 import sys
18 functext = genfunc(len(sys.argv[1]))
19 print functext
20 exec(functext)
21 print dir()
22 thelist = permute(list(sys.argv[1]))
23 print 'Got', len(thelist), 'items.'
運(yùn)行一下,
sh-2.05b$ python permute5.py 12345 3
def permute(seq0):
result = []
for counter1 in seq0:
seq1 = seq0[:]
seq1.remove(counter1)
for counter2 in seq1:
seq2 = seq1[:]
seq2.remove(counter2)
for counter3 in seq2:
seq3 = seq2[:]
seq3.remove(counter3)
for counter4 in seq3:
seq4 = seq3[:]
seq4.remove(counter4)
result.append(''.join([counter1,counter2,counter3,counter4,seq4[0]]))
return result
['__builtins__', '__doc__', '__name__', 'calc', 'functext', 'genfunc',
'permute', 'sys']
Got 120 items.
看來(lái)格式是弄對(duì)了. 現(xiàn)在算算運(yùn)行時(shí)間, 會(huì)不會(huì)好些呢? 也許會(huì)比以前更快, 也許因?yàn)橐賵?zhí)行自己產(chǎn)生的程式而更慢, 一切都要看實(shí)際的數(shù)據(jù)才能呢! 你修改了 permute5.py 以便它能標(biāo)準(zhǔn)化地計(jì)算時(shí)間. 你開(kāi)始覺(jué)得 import calc 實(shí)在是挺聰明的設(shè)計(jì).
1 # permute5.py
2 def genfunc(n):
3 head = """
4 def permute(seq0):
5 result = [] """
6 boiler = """
7 for counter%i in seq%i:
8 seq%i = seq%i[:]
9 seq%i.remove(counter%i)"""
10 for i in range(1,n):
11 space = ' '*i
12 head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i)
13 temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)])
14 head = head + '\n' + space + " result.append(''.join([%s]))"%(temp)
15 return head + '\n return result\n'
16
17 import sys, calc
18 functext = genfunc(len(sys.argv[1]))
19 #print functext
20 exec(functext)
21 thelist = permute(list(sys.argv[1]))
22 print 'Got',len(thelist),'items.'
23 calc.calc(thelist,int(sys.argv[2]))
開(kāi)始計(jì)時(shí):
$ time cpython permute5.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002
real 0m0.213s
user 0m0.200s
sys 0m0.010s
啊哈! 那個(gè)什么量級(jí) O(n) 的也被你打敗!! 你覺(jué)得它的量級(jí)其實(shí)不是 O(n), 那只是對(duì)找一整個(gè)排列其中一個(gè)的時(shí)候才有用, 要把整個(gè)排列都算出來(lái)的話還是要回到 n! 上的.
你非常自豪. 但這也許是適當(dāng)?shù)臅r(shí)候提醒自己謙虛的妤處. 既然都到了這個(gè)地步了, 何不再走多一步, 翻一下書(shū)看看, 也許你找到的方法已經(jīng)早有別人發(fā)現(xiàn)了. 果真是這樣的話, 你, 一個(gè)無(wú)知的白癡, 到處大吹大擂自己的發(fā)明是會(huì)被笑話的.
於是你找出了封塵的電腦和數(shù)學(xué)教科書(shū). 找到了排列組合一章, 開(kāi)始細(xì)讀. 終於你找到了這樣的一幅圖畫(huà):
[4321]
[3421]
[321] < [3241]
[21] < [231]... [3214]
[213]...
[1] <
[321]...
[21] < [231]...
[213]...
書(shū)中寫(xiě)到, 要產(chǎn)生一個(gè)排列其實(shí)可以用這樣一個(gè)方法: "先選一個(gè)數(shù) 1, 然后第二個(gè)數(shù) 2 可以放在 1 的前面或是后面. 而每一個(gè)放法都會(huì)產(chǎn)生一個(gè) 2 位數(shù), 對(duì)於每一個(gè)這樣的兩位數(shù), 第三個(gè)數(shù) 3, 都可以放在它的前面, 中間, 或是最后; 如此產(chǎn)生一個(gè) 3 位數(shù); 而每一個(gè) 3 位數(shù), 第 4 位數(shù)都可以插入到這 3 個(gè)數(shù)的任何一個(gè)空位中, 如此類推. 書(shū)中還列出了一個(gè)程式范例呢! 并聲這個(gè)方法要和已知的最快的算排列的方法速度相若.
你急不可待地開(kāi)始把書(shū)中的描述實(shí)現(xiàn). 用 Python, 你很快又得到了一個(gè)全新的程式:
1 # permute6.py
2 def permute(seq):
3 seqn = [seq.pop()]
4 while seq:
5 newseq = []
6 new = seq.pop()
7 #print "seq:",seq,'seqn', seqn ,'new', new
8 for i in range(len(seqn)):
9 item = seqn[i]
10 for j in range(len(item)+1):
11 newseq.append(''.join([item[:j],new,item[j:]]))
12 seqn = newseq
13 #print 'newseq',newseq
14 return seqn
15
16 import sys, calc
17 seq = list(sys.argv[1])
18 where = int(sys.argv[2])
19 thelist = permute(seq)
20 print 'Got', len(thelist), 'items.'
21 calc.calc(thelist, where)
測(cè)試結(jié)果如下:
$ time cpython permute6.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002
real 0m0.167s
user 0m0.150s
sys 0m0.020s
哇塞! 書(shū)中自有黃金屋咧! 想不到這個(gè)才是最快的算法. 你開(kāi)始感到要擊敗這次的對(duì)手不是不件容易的事, 而且現(xiàn)在已經(jīng)很晚了, 你身心也都被疲倦所包圍著. 你絕望地看著這個(gè)新的程式碼和它那美妙的結(jié)構(gòu), 作出最后的嘗試:
待續(xù)...
守夜人:
Got 24 items.
['1234', '2134', '2314', '2341', '1324', '3124', '3214', '3241', '1342',
'3142', '3412', '3421', '1243', '2143', '2413', '2431', '1423', '4123',
'4213', '4231', '1432', '4132', '4312', '4321']
上面就是 permute7.py 產(chǎn)生的四位數(shù)字排列結(jié)果, 你細(xì)心地反覆觀看, 終於看出了一些端倪: 其實(shí)所產(chǎn)生的排列是有一種對(duì)稱性的, 第一個(gè)和最后一個(gè)是完全次序相反的, 而第二個(gè)又和倒數(shù)第二個(gè)完全相反. 利用這些對(duì)稱性, 也許你可以把計(jì)算時(shí)間打個(gè)對(duì)折喲. 而你研究了一下程式的實(shí)現(xiàn)方法后你發(fā)現(xiàn)只要改一行! 就可以實(shí)現(xiàn)這樣的功能: 就是第一行 seqn = [ seq.pop() ] 改成 seqn = [ seq.pop()+seq.pop() ]. 這樣你就實(shí)現(xiàn)了只產(chǎn)生其中一半的排列, 爾后你只要把這個(gè)列表中的元素都掉個(gè)就完成了整個(gè)排列. 程式如下
1 # permute7.py
2 def permute(seq):
3 seqn = [ seq.pop()+seq.pop() ]
4 while seq:
5 newseq = []
6 new = seq.pop()
7 #print "seq:",seq,'seqn', seqn ,'new', new
8 for i in range(len(seqn)):
9 item = seqn[i]
10 for j in range(len(item)+1):
11 newseq.append(''.join([item[:j],new,item[j:]]))
12 seqn = newseq
13 #print 'newseq',newseq
14 return seqn
15
16 import sys, calc
17 seq = list(sys.argv[1])
18 where = int(sys.argv[2])
19 thelist = permute(seq)
20 print 'Got', len(thelist), 'items.'
21 print thelist
22 # 這個(gè)等一下再探討
23 #calc.calc2(thelist, where)
測(cè)試數(shù)據(jù)表示果然這個(gè)改良了的程式要比原來(lái)快了剛好一倍. 這次應(yīng)該足夠了. 但是要得到整個(gè)排列的話要把這半個(gè)列表重抄一次而且每個(gè)元素都要反過(guò)來(lái): "1234" -> "4321". 但是在 Python 之中的字串并沒(méi)有反序的函數(shù), 因此你必須先把字串變成列表, 再反過(guò)來(lái), 然而 list.reverse() 這個(gè)函數(shù)偏偏很討厭的不會(huì)傳回任何值 (因?yàn)樗?in-place 的緣故), 所以你要用 i = list(item); i.reverse; i = ''.join(i); 這個(gè)復(fù)雜的方法. 你想了想, 這個(gè)做法大概會(huì)把原來(lái)只做一半排列所省下來(lái)的時(shí)間都浪費(fèi)掉了. 你思考半天, 終於決定重寫(xiě) calc.py 部份以便直接利用已知的半個(gè)列表.
#!python
# calc.py
def calc(seq, where):
maximum, max_item = 0, []
for i in seq:
product = int(i[:where]) * int(i[where:])
if product > maximum:
maximum, max_item = product, i
elif product == maximum:
max_item += ','+i
print "Maximum at", max_item, ",product", maximum
def calc2(seq, where):
maximum, max_item = 0, []
for i in seq:
product = int(i[:where]) * int(i[where:])
if product > maximum:
maximum, max_item = product, i
elif product == maximum:
max_item += ','+i
rev = list(i)
rev.reverse()
i = ''.join(rev)
product = int(i[:where]) * int(i[where:])
if product > maximum:
maximum, max_item = product, i
elif product == maximum:
max_item += ','+i
print "Maximum at", max_item, ",product", maximum
當(dāng)然你保留了以前的函數(shù) calc 而只是新加一個(gè)專門給 permute7.py 調(diào)用的 calc2 函數(shù). 你試了一下速度, 成功了比 permute6.py 快了一丁點(diǎn). 雖然只是這一點(diǎn)兒點(diǎn)兒, 你也覺(jué)得快活無(wú)比. 因?yàn)橛忠淮? 你為一個(gè)大家都覺(jué)得好的方法做出了改良.
雖然你知道在這個(gè)階段如果你把 calc.py 整合到排列產(chǎn)生器中也許會(huì)得更好的提速效果, 但你覺(jué)得現(xiàn)在這樣已經(jīng)可以很多人都認(rèn)同你的能力了. 而且能把一個(gè)高效的排列產(chǎn)生器獨(dú)開(kāi)來(lái)也許是聰明的做法, 因?yàn)閷?lái)你一定會(huì)再用它的. 你看了一下所有的程式, 從 permute1.py 到 permute7.py, 再做了一次速度的檢定. 反正是最后一次了, 干脆做個(gè)大的吧.
$ time python permute2.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m46.478s
user 0m46.020s
sys 0m0.430s
$ time python permute3.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m38.997s
user 0m38.600s
sys 0m0.400s
$ time python permute4.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m33.845s
user 0m33.460s
sys 0m0.380s
$ time python permute5.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m10.681s
user 0m10.530s
sys 0m0.150s
$ time python permute6.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902
real 0m8.279s
user 0m8.110s
sys 0m0.170s
$ time cpython permute7.py 123456789 5
Got 181440 items.
Maximum at 875319642 ,product 843973902
real 0m7.827s
user 0m7.650s
sys 0m0.180s
嗯, 很不錯(cuò). 最快的要比原先快上近七倍呢! 於是你打算明天一有空便把這個(gè)最好的公式貼到網(wǎng)上去, 讓更多人分享. 你很放心地去睡覺(jué)了.
但是不知為了什么, 你總覺(jué)得有些事煩擾著你, 還有什么不妥的地方呢? 你實(shí)在想不到了, 迷迷糊糊地抱著迷惑不安的心情入夢(mèng).
終於你忍不住爬了起床, 再一次回到電腦屏幕前. 你想到了一個(gè)致命的問(wèn)題, 對(duì)於很大很大的排列, permute7.py 還是會(huì)嘗試一下子把所有的排列都做出來(lái), 不用多久電腦資源就會(huì)被耗光的. 你也許要另想一個(gè)方法, 每次只做一個(gè)排列. 但你是否可以把所有的排列用 1, 2, 3, 4 的方法數(shù)出來(lái)呢?
你看著教科書(shū)上的那幅圖畫(huà), 這樣的樹(shù)狀結(jié)構(gòu)應(yīng)該有辦法的, 你對(duì)自己說(shuō).
慢慢讀著書(shū)上的文字. 設(shè)想有 n 個(gè)數(shù)字, 先取第一個(gè)數(shù)字. 再取第二個(gè)數(shù)字, 第二個(gè)數(shù)可以放在第一個(gè)數(shù)的左或右面, 就是有 0, 1 兩個(gè)選擇. 再取第三個(gè)數(shù), 放到前面選好的兩個(gè)數(shù)字中, 可以放在最左, 中間, 最右, 就是有 0, 1, 2 三個(gè)選擇. 嗯, 很自然嗎. 忽然你想到了二進(jìn)位, 八進(jìn)位那些數(shù)系轉(zhuǎn)換關(guān)系. "我可以設(shè)計(jì)這樣一個(gè)數(shù), ...xyz, 其中個(gè)位數(shù) z 是二進(jìn)位的, 也就是放第二個(gè)數(shù)的兩個(gè)位置; 十位數(shù) y 是三進(jìn)位的, 化表放第三個(gè)數(shù)字的三個(gè)位子, 然后百位數(shù)是四進(jìn)位, 千位數(shù)是五進(jìn)位的, 依以類推." 沒(méi)錯(cuò), 這樣設(shè)計(jì)的話, 如果 0 表示放於最左面的話, 則 "2021" 這個(gè)數(shù)就代表了排列五個(gè)元素 (abcde), 取一個(gè) a, 然后第二個(gè) b 放在 a 的右面成 ab, 取 c 放到最右面成為 abc, 取 d 放到最左面成 dabc; 最后 e 放到中間去成為 daebc. 至於 "2021" 這個(gè)特別的設(shè)計(jì)的數(shù)可以用 ..+ x*4 + y*3 + z*2 這樣的計(jì)算來(lái)映對(duì)到自然數(shù)的數(shù)列上去.
沒(méi)錯(cuò)了, 如求 4 個(gè)數(shù)的 4! = 24 個(gè)排列, 第 18 個(gè)排列可以這樣求得, 18 除 2, 余數(shù)是 0, 所以第二個(gè)數(shù)放在第一個(gè)數(shù)的左面; 然后商 9 再除 3, 余數(shù) 0, 所以第三個(gè)數(shù)於在頭兩個(gè)數(shù)的最左; 最后 3 除以 4, 余數(shù)是 3, 因此第四個(gè)數(shù)要放在前三個(gè)數(shù)的第 4 個(gè)空位, 也就是最右面. 利用這個(gè)方法, 你就不必先求出整個(gè)排列才能開(kāi)始計(jì)算. 盡管這好像犧牲了時(shí)間, 但省下了大量的空間. 你完全可以算出 1000 個(gè)數(shù)的最大排列方法, 縱使那可能要用去幾個(gè)月的運(yùn)算. 你更高興的是用這個(gè)方法, 你可以把整個(gè)計(jì)算拆開(kāi)成為一個(gè)一個(gè)的部份: 譬如說(shuō)求 10! = 3628800 個(gè)排列, 你大可以把 1 到 1000000 讓一部電腦做, 1000001 到 2000001 讓另一部來(lái)做 ... 大家的工作并不重覆, 這等於實(shí)現(xiàn)并行運(yùn)算了! 啊哈! 妙極了!
忽然你靈光一閃, 對(duì)了, 這個(gè)不正是 permute4.py 的算法嗎! 你昨天還久思不得其解呢, 現(xiàn)在你已經(jīng)完全明白了. 嗚, 雖然這么好的算法原來(lái)不是你原創(chuàng)的, 但是你仍然異常興奮. 因?yàn)槟愕乃悸肪购湍切┐笈兓ハ辔呛? 你漸漸記起了當(dāng)你還在玩 DOS 游戲機(jī)的年代, 曾有個(gè)古怪的人向你吹噓過(guò)某個(gè)電腦撲克游戲中用了一個(gè)威力很大的洗牌法, 多么的快而且公平, 不必怕黑客們用已知的隨機(jī)數(shù)表來(lái)出千. 現(xiàn)在你猜到了, 那個(gè)算法很可能就是眼下這一個(gè)了. 有 52 張牌, 如果要預(yù)先算出 52! 個(gè)排列才能洗牌可真要命呢.
你覺(jué)得舒服多了, 你整理了一下程式, 打算把結(jié)果告訴大家. 然而剛才的不安感又重新來(lái)襲. 你再看了一次最后也應(yīng)該是最棒的程式, 心中安慰自己道: "千萬(wàn)不要跌進(jìn)低等程式員的的陷阱, 他們瘋也似的不斷追求, 郤從來(lái)不知道自己的目標(biāo), 也不知道什么才是好. 完美的設(shè)計(jì)不在于你無(wú) 法添加新的功能, 完美的設(shè)計(jì)是再也不能精簡(jiǎn)現(xiàn)有的功能." 你覺(jué)得 permute7.py 已迫近了這一個(gè) 極限. 但你內(nèi)心深處并沒(méi)有因此而舒坦開(kāi)來(lái), 一種懸空的感覺(jué)自足下升起. 也許是你太累了, 于是 者你決定閉目養(yǎng)神數(shù)分鐘再開(kāi)始上網(wǎng), 可惜你很快地迷迷糊糊地進(jìn)入了夢(mèng)境.
待續(xù)...
終篇:
你做了一個(gè)夢(mèng), 夢(mèng)中你看到阿凡提騎著他那出名的毛驢來(lái)到你面前并向你提出挑戰(zhàn): "除非你解答了我的難題,不然我的驢子會(huì)不停在你耳邊嘶叫令你無(wú)法睡好! 問(wèn)題是: 把數(shù)字 56789 放到 [][][]*[][] 里得出最大的的乘積...." 你發(fā)出會(huì)心的微笑, 正想祭出你的 permute7.py 之時(shí)忽然想起阿凡提是不可能懂得電腦編程的! 你心中登時(shí)涼了一大截: 阿凡提的方法一定不必用電腦算出所有的排列方法, 并很快的得知答案的. 隨著一聲震天的驢嘶, 你驚醒了, 發(fā)現(xiàn)原來(lái)你伏在電腦桌上睡去了, 不小心壓著了鍵盤(pán)上的方向鍵而令你的電腦發(fā)出了痛苦的 BEEP 聲.
回想夢(mèng)境, 你打算暫時(shí)離開(kāi)電腦, 回到問(wèn)題本身上來(lái): 怎樣才能"看"出最大的乘積呢 ?
你拿出紙筆, 開(kāi)始計(jì)算:
假設(shè)五個(gè)數(shù)為 [a][b][c]*[d][e], 展開(kāi)的話成為
a * 100 * d * 10
+ a * 100 * e * 1
+ b * 10 * d * 10
+ b * 10 * e * 1
+ c * 1 * d * 10
+ c * 1 * e * 1
這個(gè)可以寫(xiě)成一個(gè)矩陣:
d e
a 1000 100
b 100 10
c 10 1
你這樣想到: 在整個(gè)答案中, a 帶來(lái)的頁(yè)獻(xiàn)是一個(gè)百位數(shù)加上一個(gè)十位數(shù), 而 d 的頁(yè)獻(xiàn)是一個(gè)百位數(shù)加十位數(shù)加個(gè)位數(shù), 因此 d 要比 a 更重要. 要取得最大的積則一定要把 56789 中最大的 9 放在 d 的位置, 然后是 a, 如此類推.
為了方便計(jì)算,你干脆用對(duì)數(shù)來(lái)記數(shù) 100 = 10e2, 用 2 來(lái)代表好了, 因此:
d e
a 3 2
b 2 1
c 1 0
計(jì)算每一行或列的和, 把它稱為該數(shù)的基值, 我們得到
a = 5, b = 3, c = 1, d = 6, e = 3.
咦? b 和 e 的基值是一樣的, 怎么辦!
你思考著: "啊哈! 因?yàn)槲覀冇昧藢?duì)數(shù), 而 log(1) = 0 因此把 b 和 e 之間的微小分別給忽略了!" 好吧, 試把每個(gè)數(shù)都加大一個(gè), 得到:
d e
a 4 3
b 3 2
c 2 1
這樣基數(shù)變成了: a = 7, b = 5, c = 3, d = 9, e = 6. 這些基數(shù)代表了該位置的重要性, 可以按大小分予不同的數(shù)字.
好, 按基數(shù)的大小來(lái)分配數(shù)字你得到了 865 * 97. 一對(duì)答案, 喲! 不一樣! 正確解是 875 * 96. 哪里不對(duì)了呢? 仔細(xì)分析下來(lái), 你發(fā)現(xiàn) b 和 e 互換了. 換的原因是這樣的:
b 的頁(yè)獻(xiàn): b * d * 100 + b * e * 10 e 的頁(yè)獻(xiàn): e * a * 100 + e * b * 10 + e * c
粗看的話 e 的頁(yè)獻(xiàn)要大一些, 但因?yàn)槲覀儼?9 配給了 d 而 8 配給了 a, 因此最終的結(jié)果是 b 的實(shí)際頁(yè)獻(xiàn)要比 e 大. 由於 e 和 b 的基數(shù)只相差在 e * c 這個(gè)個(gè)位數(shù)乘積上, d 和 a 之間的分配結(jié)果把這個(gè)小的差異覆蓋掉了.
你考慮著: "要把這樣的覆蓋也算上去的話, 也許可以做一個(gè)二階基數(shù). 如 b * d 的基數(shù)是 100, 但是由於 d 的基數(shù)為 9, 那 b 的二階基數(shù)可以算成 9, 代表和 b 相關(guān)的是一個(gè)較為重要的數(shù); 同樣 e * a 的基數(shù)是也是 100 但由於 a 的基數(shù)只是 7, 因此 e 的二階基數(shù)只是 7 而已. 這樣就可以得出 b 要比 e 更重要了."
於是你有了一個(gè)想法: 先寫(xiě)出相關(guān)矩陣, 然后計(jì)算每個(gè)數(shù)的基數(shù)和二階基數(shù), 再進(jìn)行排序, 當(dāng)兩個(gè)基數(shù)很接近時(shí)就用二階基數(shù)來(lái)判別哪個(gè)較重要. 嗯, 你覺(jué)得自己聰明極了, 於是開(kāi)始驗(yàn)算, 但很快又發(fā)現(xiàn)其實(shí) b 和 e 的二階基數(shù)原來(lái)也是一樣的!! 大家都是 15. 也許我們要用一個(gè)三階基數(shù)才能分辨他們.
你又想了一些新的二階基數(shù)的定義, 有些的確給出正確的答案, 但你漸漸覺(jué)得這一切并不很妥當(dāng). 因?yàn)榫退隳苡?jì)出 56789, 但是在更多的排列, 如 7 位數(shù)甚至 9 位數(shù)的排列你怎樣保證答案也一定準(zhǔn)確呢, 而兩個(gè)基數(shù)到底怎樣才算是比較接近呢? 仔細(xì)審視你的方法, 用對(duì)數(shù)來(lái)表示乃至直接相加來(lái)求所謂的基數(shù)統(tǒng)統(tǒng)都是即興的, 毫不嚴(yán)謹(jǐn). 或者要真正解決他們必需要把每一種情況都算進(jìn)來(lái), 而那樣做的話必然要計(jì)算 n! 那么多次! 說(shuō)到底還是要算排列的.
你有些失望, 但暗中覺(jué)得松了一口氣, 因?yàn)榈降资?permute7.py 得到最后的勝利. 你伸了一下懶腰, 原來(lái)天都快亮了. 這時(shí)你感到有些餓, 便去拿了半個(gè)涼饅頭, 沖了一些可可. 你對(duì)著空空的螢光屏, 靜靜地坐了大概十分鐘, 然后答案進(jìn)入你的腦海, 謎團(tuán)被解開(kāi)了.
你的方法是求出所有位置的"重要性"(用你的語(yǔ)言就是求基數(shù)), 然后依次把最大的數(shù)字分配給最重要的位置. 但是位置的重要性是和其他位置糾纏在一起的, 因此一次過(guò)算出所有位置的重要性必須考慮大量不同的組合排列, 并不實(shí)際.
但是, 我們其實(shí)可以每次只求第一個(gè)最大的基數(shù)的位置 (abc*de 的情況下最大的基數(shù)是 d), 這個(gè)最大的基數(shù)是沒(méi)有爭(zhēng)議的. 當(dāng)求得這個(gè)位置時(shí), 干脆把最大的數(shù)字放到該位子上, 然后再求一次基數(shù), 找出接下來(lái)最大的位子, 這個(gè)位子也是無(wú)可爭(zhēng)議的. 如此一來(lái), 原來(lái)求 5 個(gè)數(shù)字的全排列成就簡(jiǎn)化為 5 次簡(jiǎn)單的回圈. 一個(gè)求 Factorial(n) 的問(wèn)題變成了 n 次循環(huán)!
啊哈!
你精神大好, 從另一個(gè)角度切入:
假如 5 個(gè)數(shù)字一樣, 11111, 最大的乘積只能是 111 * 11, 現(xiàn)在容許改大一個(gè)數(shù), 改哪個(gè)會(huì)使結(jié)果最大 ?
211 * 11, 121 * 11, 112 * 11, 111 * 21, 111 * 12 ? 答案是 111 * 21, 也就是 d 的位置. 好, 把 d 替換成 9.
問(wèn)題變成 5 個(gè)數(shù)字, 111 * 91, 改一個(gè)數(shù)(除了 9), 改哪一個(gè) ?
211 * 91, 121 * 91, 112 * 91, 111 * 19 ? 答案是 211 * 91, 也就是 a 的位置. 好, 替換成 8.
依此類推, 答案正正是 875 * 96.
你重開(kāi)電腦, 很快地把新方法輸入程式, 并改名為 wise.py.
1 def solve(seq,where):
2 n = len(seq)
3 seq.sort()
4 seq.reverse()
5 table = [ [] for i in range(n) ]
6 left, right = where, n - where
7 leftr = long('1'*left)
8 rightr = long('1'*right)
9 flag=[]
10 for item in [ int(x) for x in seq]:
11 for i in range(left):
12 table[left-i-1] = (leftr + 10**i) * rightr
13 for i in range(right):
14 table[right-i+where-1] = leftr * (rightr + 10**i)
15 for i in flag:
16 table[i] = 0
17 tablesorted = table[:]
18 tablesorted.sort()
19 maxindex = table.index(tablesorted[-1])
20 if maxindex >= where:
21 rightr = rightr + (item-1) * 10**(right-maxindex+where-1)
22 else:
23 leftr = leftr + (item-1) * 10**(left-maxindex-1)
24 flag.append(maxindex)
25 #print maxindex, leftr, rightr
26 return leftr, rightr
27
28 import sys
29 leftr, rightr = solve(list(sys.argv[1]),int(sys.argv[2]))
30 print "Maximum at", leftr,rightr, ',product', leftr*rightr
你驗(yàn)算了一下結(jié)果, 完全正確! 這時(shí)你好奇地再次 time 了一下程式的速度
$time python permute7.py 123456789 5
Got 181440 items.
Maximum at 875319642 ,product 843973902
real 0m7.827s
user 0m7.650s
sys 0m0.180s
$ time python wise2.py 123456789 5
Maximum at 87531 9642 ,product 843973902
real 0m0.042s
user 0m0.010s
sys 0m0.030s
哇! 快了近兩百倍! 當(dāng)然了. 如果算更多位的排列會(huì)快更多, 因?yàn)?wise.py 跳離了 n! 的限制.
你現(xiàn)在覺(jué)得舒服多了. 你真的解了這個(gè)問(wèn)題. 你不再怕有人會(huì)寫(xiě)出更快 10 倍的程式了. 你既有了"聰明"的答案 (軟解) 來(lái)對(duì)付阿凡提和他的驢子, 而在硬解方面, 你也自信有世界第一流的排列產(chǎn)生器. 你完全滿足了, 你不再感到疲累, 心中疑猶一掃而空. 這時(shí)你身體感到一陣震栗但心中卻喜樂(lè)無(wú)窮, 你第一次感受到了編程之道的洗禮. 并且, 你學(xué)會(huì)了所有程式大師都有的態(tài)度: 我沒(méi)法用中文來(lái)形容, 這種態(tài)度叫做 "to hack". 你知道只要你熟練并保持這種態(tài)度來(lái)面對(duì)生命中的難題, 你很快就可以滿師出山了.
你最后一次瀏覽了一下你的程式碼, 發(fā)現(xiàn)在 wise.py 中, 其實(shí)每一個(gè)循環(huán)完成后, 最重要的位置和最次要的位子都是不容爭(zhēng)議的, 因此大可放心地替換兩個(gè)數(shù)字而不是一個(gè), 那程式可以再快一倍. 不過(guò)你覺(jué)得現(xiàn)在己經(jīng)很夠了, 你頗有禪機(jī)地自言自語(yǔ)道: "我已經(jīng)找到明月,再糾纏只下去只是妄執(zhí)於指月的手而已." 你熟練地登出系統(tǒng)并關(guān)上電腦, 你知道這次你可以真正安心地睡一覺(jué)了.
哎喲! 天已亮了, 今天是禮拜一, 你要上班的. 喔! 又要被老板說(shuō)上班一條蟲(chóng), 下班一條龍...... 慘.......
全篇完.
課后檢討:
一) 在上面的故事中,我們看到了解決編程問(wèn)題的五個(gè)方法.
- 把問(wèn)題規(guī)范成一個(gè)普遍的形式,這樣更容易和別人交流以及找相關(guān)資料.
- 自己嘗試找答案.
- 在網(wǎng)上搜尋更好的答案.
- 想一個(gè)方法來(lái)打敗這個(gè)更好的答案.
- 翻查教科書(shū)或是文獻(xiàn),從基本開(kāi)始思考有沒(méi)有最好的解.這些書(shū)能被選成教本一定有它的原因.
- 研究問(wèn)題的特殊情況, 也許會(huì)有別出心裁的巧妙方法.
二) 故事中每個(gè)程式都只有二三十行大小,說(shuō)明 Python 語(yǔ)言表達(dá)力強(qiáng)且語(yǔ)意很濃縮, 做為快速開(kāi)發(fā)或是測(cè)算自己的想法都是非常好的.
三) Python 程式濃縮之余,它的語(yǔ)言也異常的清晰.回看上面的程式,你會(huì)發(fā)現(xiàn)它們?nèi)疾浑y明白.這說(shuō)明 Python 程式更加容易維護(hù).
四) 在故事中,我們有很大的篇幅是在討論方法而只有小部份是在描述 Python 的語(yǔ)言特性.這證明 Python 更適合用來(lái)教授編程的概念. 事實(shí)上, Python 的作者 Guido 和很多人都認(rèn)為 Python 是電腦教育的首選語(yǔ)言. 教師可以讓學(xué)生靜靜地思考,學(xué)通運(yùn)算的法則; 而不是上來(lái)就瘋狂地敲打鍵盤(pán),并要記住一大堆電腦語(yǔ)言的古怪特徵.
五) 整個(gè)故事圍繞於算法的改進(jìn)而較少碰到 Python 程式的優(yōu)化問(wèn)題. 也許在續(xù)集中(如果有的話), 我們要嘗試一下在固定的算法及盡量少改動(dòng)程式碼的條件下, 提高 Python 程式的效率. 我暫時(shí)想到的方法包括:
- 利用較新和較快的語(yǔ)法. 如 yield, generator.
- 用 Python 的自帶優(yōu)化選項(xiàng)以及內(nèi)建模組.
- 用第三方的擴(kuò)展模組, 如 Numpy, Scipy.
- 用編譯方式代替解釋, 如 freeze, py2exe.
- 用 JIT 類的方法, 如 Psyco.
- 用 Thread, 在多 CPU 的機(jī)器上平行運(yùn)算.
- 最后一樣要大改程式了, 用 C 來(lái)做擴(kuò)展.
- 更有 'to hack' 感覺(jué)的, 修改 Python 主干程式, 加入像 string.reverse() 這樣的輔助函數(shù).
六) 文中所用的測(cè)試硬件:
七) 啃涼饅頭對(duì)腦筋有幫助.
八) 如果你能想到更好的方法, 歡迎聯(lián)絡(luò)本人: glace_at_chinesepython.org