youxi.doc

python游戏编写实例教程

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 
哇! 的确不是盖的. 很好, 而且现在你知道了别人不知的新答案. 就把它贴上去罢. 就在你决定的时候按钮之际, 你到底犹豫了: "我对这个算法不是很了解, 如果别人问起的话怎样回答呢? 这会让我像个东抄西抄的小偷呢! 不, 要不我要明白它的原理, 不然就自己做一个比它更好的." 你觉得壮志无限. 
但是现在已经很晚, 你要去睡了. 无奈你在床上反覆地思考著更好的方法, 你整个晚上都没睡好. 
待续...... 
第二天:
你醒来第一件事, 洗脸刷牙. 编程爱好者并不一定和终日蓬头垢面同义. 然后呢, 看看电视报纸, 做些公益活动, 今天是礼拜天嘛. 废话少说, 终於你在电脑前坐下, 登入了你喜爱的 Slackware / RedHat / Redflag / Mandrake / Debian / WindowsXP / Chinese2000 / DOS / Solaris/ AIX / Unicos / OSX [作者按: 请依实际情况增删, 但千万拜托不要把 SCO 也加进来], 这些都是 Python 能够运行的平台. 
你记起你以前学到递归时听过的话: 任何递归/回溯函数都可以还原成非递归形式的. 於是你决定用你自己的方式一试. 你默念著求排列的方法, 5 个数取一个, 剩下 4 个, 再取一个, 剩下 3 个 .... 於是你写出一个新的程式, 和最初的一个很相像: 
    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"))
这个程式依次创建 5, 4, 3, 2, 1 个数的列表, 每个都不包括之前被选的数字, 然后把 5 个数合起来完成一种排列.当然, 你还有空间做 unroll. 但现在问题在於, 你对程式的要求是事先并不知道要求多少个数字的排列, 就是你不知道要写几个 for 才够. 但现在你认为有一个好办法: 既然 Python 是动态的, 它可以执行自己写出来的编码, 为什么不叫它自己帮自己来写这个循环程式以完成工作呢? 你觉得这种让程式来为自己写程式的想法很科幻也很妙, 而且让你记起了以前听到很多资深程式员爱用的 m4 宏语言. 於是你赶紧试了一个. 你认为可以用 counter0, counter1, counter2...来代替 i, j, l, m...的循环子命名法. 
    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.'
运行一下, 
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. 
看来格式是弄对了. 现在算算运行时间, 会不会好些呢? 也许会比以前更快, 也许因为要再执行自己产生的程式而更慢, 一切都要看实际的数据才能呢! 你修改了 permute5.py 以便它能标准化地计算时间. 你开始觉得 import calc 实在是挺聪明的设计. 
    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]))
开始计时: 
$ time cpython permute5.py 1234567 4 
Got 5040 items. 
Maximum at 6531742 ,product 4846002 
 
real    0m0.213s 
user    0m0.200s 
sys     0m0.010s 
啊哈! 那个什么量级 O(n) 的也被你打败!! 你觉得它的量级其实不是 O(n), 那只是对找一整个排列其中一个的时候才有用, 要把整个排列都算出来的话还是要回到 n! 上的. 
你非常自豪. 但这也许是适当的时候提醒自己谦虚的妤处. 既然都到了这个地步了, 何不再走多一步, 翻一下书看看, 也许你找到的方法已经早有别人发现了. 果真是这样的话, 你, 一个无知的白痴, 到处大吹大擂自己的发明是会被笑话的. 
於是你找出了封尘的电脑和数学教科书. 找到了排列组合一章, 开始细读. 终於你找到了这样的一幅图画: 
                      [4321]   
                      [3421] 
             [321]  < [3241]      
      [21] < [231]... [3214] 
             [213]... 
[1] < 
             [321]... 
      [21] < [231]... 
             [213]...       
书中写到, 要产生一个排列其实可以用这样一个方法: "先选一个数 1, 然后第二个数 2 可以放在 1 的前面或是后面. 而每一个放法都会产生一个 2 位数, 对於每一个这样的两位数, 第三个数 3, 都可以放在它的前面, 中间, 或是最后; 如此产生一个 3 位数; 而每一个 3 位数, 第 4 位数都可以插入到这 3 个数的任何一个空位中, 如此类推. 书中还列出了一个程式范例呢! 并声这个方法要和已知的最快的算排列的方法速度相若. 
你急不可待地开始把书中的描述实现. 用 Python, 你很快又得到了一个全新的程式:
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)
测试结果如下: 
$ time cpython permute6.py 1234567 4 
Got 5040 items. 
Maximum at 6531742 ,product 4846002 
 
real    0m0.167s 
user    0m0.150s 
sys     0m0.020s 
哇塞! 书中自有黄金屋咧! 想不到这个才是最快的算法. 你开始感到要击败这次的对手不是不件容易的事, 而且现在已经很晚了, 你身心也都被疲倦所包围著. 你绝望地看著这个新的程式码和它那美妙的结构, 作出最后的尝试: 
待续... 
守夜人:
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 产生的四位数字排列结果, 你细心地反覆观看, 终於看出了一些端倪: 其实所产生的排列是有一种对称性的, 第一个和最后一个是完全次序相反的, 而第二个又和倒数第二个完全相反. 利用这些对称性, 也许你可以把计算时间打个对折哟. 而你研究了一下程式的实现方法后你发现只要改一行! 就可以实现这样的功能: 就是第一行 seqn = [ seq.pop() ] 改成 seqn = [ seq.pop()+seq.pop() ]. 这样你就实现了只产生其中一半的排列, 尔后你只要把这个列表中的元素都掉个就完成了整个排列. 程式如下 
    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 # 这个等一下再探讨
   23 #calc.calc2(thelist, where)
测试数据表示果然这个改良了的程式要比原来快了刚好一倍. 这次应该足够了. 但是要得到整个排列的话要把这半个列表重抄一次而且每个元素都要反过来: "1234" -> "4321". 但是在 Python 之中的字串并没有反序的函数, 因此你必须先把字串变成列表, 再反过来, 然而 list.reverse() 这个函数偏偏很讨厌的不会传回任何值 (因为它是 in-place 的缘故), 所以你要用 i = list(item); i.reverse; i = ''.join(i); 这个复杂的方法. 你想了想, 这个做法大概会把原来只做一半排列所省下来的时间都浪费掉了. 你思考半天, 终於决定重写 calc.py 部份以便直接利用已知的半个列表. 
#!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, []