雜談 #25 Me, Myself,Python and Shit

  • 休息了一星期。
  • 五一假期後才正式開始新工作。即是還有兩天最後休息日,之後又要開始營營擾擾的(正常)生活。
  • 新工作會有很長的通勤時間。很久沒有在交通時間聽歌,老而彌堅的 iPod 5 和很平但音質不錯的耳機也很久沒用。日後可能會一邊聽歌一邊讀書,皆因現在的人乘搭交通工具很吵,完全沒有公德心可言,不單有小孩的亂叫、大聲的講電話,還有就是智能電話玩遊戲的聲音。最仆街的還有用手提電話的揚聲器聽歌。
  • Emacs1 跟來的 python mode (python.el) 不好。我今日終於將它轉成 python-mode.el 。雖然較慢但是功能強大。但我的要求其實好簡單,就是 Python shell 是要有記憶的,不能好似 python.el 那樣, eval 完一段 code 之後卻即時忘記,咁樣點試野呀?
  • 最近也認識了 ipython 此物。但是,在 Emacs 中用 ipython 卻變成這個屎樣。暫時仍未知道如何處理,故此用回原來的 python shell 。
  • 最近玩得最多的是 Google App Engine 。這幾天也想玩熟個 git 。
  • 最近看了個 blog 他這樣寫:「練精學懶﹐不將五十音倒背如流﹐奢談日文文法什麼的﹐不過白說而已。」本篇文寫的 Python 很有這個 feel 。
  • The Avengers ,不過了了。在處理戲劇節奏方面,很有問題。反而同期的另一爆炸電影 Battleship 在處理節奏還更好。對,我是只看爛片的。
  1. Cocoa Emacs 不是 Aquamacs []

Python’s list comprehension

竟然有人把 Sudoku 推上來1 那就不如又順手用那個例子講下 Python 。

我覺得 Python 的兩種 data structure 是非常好用,一是 list ,另一是 dict 。
最近報了的 udacity course 近乎濫用 list comprehension 功能,我也要令自己理解它在做甚麼。在理解 list comprehension 之前,可以先看看 map 這個功能。
例如有個 list [1, 2, 3, 4] ,你想每個 item 都乘 2 。當然可以用 for loop 及 append 。

1
2
3
4
somelist = [1, 2, 3, 4]
dlblist = []
for item in somelist:
    dlblist.append(item * 2)
somelist = [1, 2, 3, 4]
dlblist = []
for item in somelist:
    dlblist.append(item * 2)

據聞這個方法是很慢的,是否如此我並不知道。
另一個做法是用 functional programming 常用到的 map 。例如:

1
2
3
4
somelist = [1, 2, 3, 4]
def doubleup(x):
    return x * 2
dlblist = map(doubleup, somelist)
somelist = [1, 2, 3, 4]
def doubleup(x):
    return x * 2
dlblist = map(doubleup, somelist)

更似 functional programming 的方法,是用 lambda 。那就連 doubleup 的 function 都不用 define 。例如:

1
2
somelist = [1, 2, 3, 4]
dlblist = map(lambda x: x * 2, somelist)
somelist = [1, 2, 3, 4]
dlblist = map(lambda x: x * 2, somelist)

所謂的 list comprehension ,正正就像是用 map 加 lambda 那樣,只不過看上去好似易看一些。

1
2
somelist = [1, 2, 3, 4]
dlblist = [item * 2 for item in somelist]
somelist = [1, 2, 3, 4]
dlblist = [item * 2 for item in somelist]

原來的 sudoku 問題有 transpose function ,樣子如此:

1
2
3
4
5
6
7
8
9
10
def transpose(sudoku):
    # nrow of the sudoku
    tsudoku = []
    nrow = len(sudoku)
    for i in range(0,nrow):
        colvec = []
        for j in range(0,nrow):
            colvec.append(sudoku[j][i])
        tsudoku.append(colvec)
    return tsudoku
def transpose(sudoku):
    # nrow of the sudoku
    tsudoku = []
    nrow = len(sudoku)
    for i in range(0,nrow):
        colvec = []
        for j in range(0,nrow):
            colvec.append(sudoku[j][i])
        tsudoku.append(colvec)
    return tsudoku

如用到 list comprehension 是可以變成這樣的 one-liner :

1
2
def transpose(sudoku):
    return [[sudoku[j][i] for j in range(0, len(sudoku))] for i in range(0, len(sudoku))]
def transpose(sudoku):
    return [[sudoku[j][i] for j in range(0, len(sudoku))] for i in range(0, len(sudoku))]

但這是否 readable 我就不清楚了。

  1. 據聞有人可以一行搞掂這個 sudoku 。 []

Udacity: Sudoku

Udacity CS101 上周的 Programming 功課,最難是這一條,是 check 一個簡化版數獨是否正確。1
問題指示如此

#THREE GOLD STARS

#Sudoku [http://en.wikipedia.org/wiki/Sudoku]
#is a logic puzzle where a game
#is defined by a partially filled
#9 x 9 square of digits where each square
#contains one of the digits 1,2,3,4,5,6,7,8,9.
#For this question we will generalize
#and simplify the game.

#Define a procedure, check_sudoku,
#that takes as input a square list
#of lists representing an n x n
#sudoku puzzle solution and returns
#True if the input is a valid
#sudoku square and returns False
#otherwise.

#A valid sudoku square satisfies these
#two properties:

# 1. Each column of the square contains
# each of the numbers from 1 to n exactly once.

# 2. Each row of the square contains each
# of the numbers from 1 to n exactly once.

correct = [[1,2,3],
[2,3,1],
[3,1,2]]

incorrect = [[1,2,3,4],
[2,3,1,3],
[3,1,2,3],
[4,4,4,4]]

Python 沒有 buildin 的 matrix 格式,故此以 list of list 的方式表達。而此 course 學的 Python 指令也不多,這才增加了此問題的難度。
很多的同學在網上 forum 指太難。這個問題最佳的解決方法,就是將大問題解為細問題。
這個問題的最細 unit ,是 check 每一橫行 Vector 的每個數字是否 unique 。例如 [1,2,3,4] ,每個數字都是 unique 。而 [4,4,4,4] 就不是 unique 了。用 abstraction 的方法,可以將如此 function 暫名為 checkVector ,就先不去想如此的 function 如何 define 。
只要用 checkVector 查 matrix 的所有橫行,就最少證實了原來 matrix 所有橫行是正確。
可能我太習慣用 R 來思考,我想到只要將如此 matrix transpose (即是將直行轉成橫行),再 check 橫行,也可證明直行也是正確的。
我寫 program 實在不叻,故此是很 verbose 的。但如此 verbose 也有好處,就是可以容易理解。
Udacity 下季有 CS212 ,由 Peter Norvig 教,我已報讀了。友人說我好像好勤學新野。對,我何時都想這樣,而且這些 course 是免費的,夫復何求。最新看了一篇文,是由一位曾於 HKU 任教,再回到美國教書的 computer scientist 寫的,他說:

My students cheated like crazy. On one occasion, I caught 35 out of 100 students cheating on a programming assignment. This is not specific to HKU. My friends at HKUST had problems of a similar magnitude. I believe this is partially due to the dark side of HK culture. Hong Kong is not about intellectual achievement. It is about profit; making money; success in the material world. Half of the shelf-space in HK bookstores is devoted to books on business, marketing, negotiation, and so forth. Cheating is in some sense a profitable activity: maximum return for minimum outlay.

我需要的是 intellectual achievement 。

correct = [[1,2,3],
[2,3,1],
[3,1,2]]

incorrect = [[1,2,3,4],
[2,3,1,3],
[3,1,2,3],
[4,4,4,4]]

def transpose(sudoku):
# nrow of the sudoku
tsudoku = []
nrow = len(sudoku)
for i in range(0,nrow):
colvec = []
for j in range(0,nrow):
colvec.append(sudoku[j][i])
tsudoku.append(colvec)
return tsudoku

def checkVector(vector, n):
checkN = 1
logicVector = []
while checkN < = n: logicVector.append(checkN not in vector) checkN = checkN + 1 badVector = True in logicVector return badVector #print checkVector([1,2,2,4], 4) #print transpose(incorrect) def check_sudoku(sudoku): widthSudoku = len(sudoku) # first check the orignal for row in sudoku: if checkVector(row, widthSudoku): return False for row in transpose(sudoku): if checkVector(row, widthSudoku): return False return True [/code]

  1. 真數獨除了要 check 9 行直行、9 行橫行,還要 check 九個 3×3 的方格數字是否 unique 。最尾的一個 criteria 對於 CS101 來說太難了。但要是真的要做,只要將九個 3×3 拆成 vector 再 check 便可。 []

Evolution of manpower in HA

這不是用 R 畫的,是用 Pylab 。數據來自 98 至 09 年 HA Statistical report
圖中每格是 500 人。

Source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from pylab import *
 
medical = [3581,3804,3979,4222,4460,4617.5,4871.8,4858.8,4898.1,4935.35,5057,5160.5]
nursing = [19614,20435,19880,19746,19710,19567.5,19307.9,19161.7,19248.0,19211.99,19273,19521.6]
allied = [4295,4392,4379,4467,4590,4721,4891,4829.6,4894.3,4965.83,5063.1,5231.1]
hca = [None, None, None, 5848,6011,6751,6837.5,6888.3,7081.7,7251.13,7769.6,8329.9]
 
year = [1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009]
subplot(4,1,1)
title('Evolution of manpower in Hospital Authority: 1998-2009')
plot(year, hca, 'r-', linewidth=3)
axis([1998, 2009, 5000, 9000])
ylabel('HCA / WA')
subplot(4,1,2)
plot(year, medical, 'g-', linewidth=3)
axis([1998,2009,3000,7000])
ylabel('Medical')
subplot(4,1,3)
plot(year, allied, 'b-', linewidth=3)
axis([1998, 2009, 4000, 7000])
ylabel('Allied Health')
subplot(4,1,4)
plot(year, nursing, 'k-', linewidth=3)
ylabel('Nursing')
axis([1998, 2009, 18000, 22000])
xlabel('Year')
show()
from pylab import *

medical = [3581,3804,3979,4222,4460,4617.5,4871.8,4858.8,4898.1,4935.35,5057,5160.5]
nursing = [19614,20435,19880,19746,19710,19567.5,19307.9,19161.7,19248.0,19211.99,19273,19521.6]
allied = [4295,4392,4379,4467,4590,4721,4891,4829.6,4894.3,4965.83,5063.1,5231.1]
hca = [None, None, None, 5848,6011,6751,6837.5,6888.3,7081.7,7251.13,7769.6,8329.9]

year = [1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009]
subplot(4,1,1)
title('Evolution of manpower in Hospital Authority: 1998-2009')
plot(year, hca, 'r-', linewidth=3)
axis([1998, 2009, 5000, 9000])
ylabel('HCA / WA')
subplot(4,1,2)
plot(year, medical, 'g-', linewidth=3)
axis([1998,2009,3000,7000])
ylabel('Medical')
subplot(4,1,3)
plot(year, allied, 'b-', linewidth=3)
axis([1998, 2009, 4000, 7000])
ylabel('Allied Health')
subplot(4,1,4)
plot(year, nursing, 'k-', linewidth=3)
ylabel('Nursing')
axis([1998, 2009, 18000, 22000])
xlabel('Year')
show()

Afraid of Recursion

就算上完一大輪 CS 堂,我對 Recursion 的認知仍是半桶水,明顯不及 Iteration 。
當要我去理解一些有 Recursion 的 code ,就會覺得好驚,更加別說要將問題化解成 Recursion 能夠解決的樣子。
很想去克服恐懼,就是要多下苦功。看書中的 example code 是明的,例如這個。1

1
2
3
4
5
6
def countdown(n):
    if n < = 0:
        print 'Blastoff!'
    else:
        print n
        countdown(n-1)
def countdown(n):
    if n < = 0:
        print 'Blastoff!'
    else:
        print n
        countdown(n-1)

Recursion 應該要有兩個重要的部份,就是 base case 和 simplifying algorithm 。以上的碼, n < = 0 就是 base case 。而 n-1 就是 simplifying algorithm 。以上的都不難明。 但是以下的東西就難明了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def generate_all_subsets(s):
    "Return a sequence containing all the substrings of the string s."
    # print 'from start again'
    if len(s) == 0:
        # print 'blast!'
        return [""]
    # Include every subset of the elements that doesn't contain s[0]...
    # print 'S:'+str(s)
    subsets = generate_all_subsets(s[1:])
    # print 's[1:]:'+str(s[1:])
    # print 'subsets'
    # print subsets
    ans = subsets[:]
    # print 'enter'
    # ...and every subset that does (these are generated by adding s[0] to
    # every subset of the previously generated sequence).
    for subset in subsets:
        # print 'subset:'+str(subset)
        # print 's0 + subset:'+str(s[0]+subset)
        ans.append(s[0] + subset)
        # print 'ans'
        # print ans
    return ans
def generate_all_subsets(s):
    "Return a sequence containing all the substrings of the string s."
    # print 'from start again'
    if len(s) == 0:
        # print 'blast!'
        return [""]
    # Include every subset of the elements that doesn't contain s[0]...
    # print 'S:'+str(s)
    subsets = generate_all_subsets(s[1:])
    # print 's[1:]:'+str(s[1:])
    # print 'subsets'
    # print subsets
    ans = subsets[:]
    # print 'enter'
    # ...and every subset that does (these are generated by adding s[0] to
    # every subset of the previously generated sequence).
    for subset in subsets:
        # print 'subset:'+str(subset)
        # print 's0 + subset:'+str(s[0]+subset)
        ans.append(s[0] + subset)
        # print 'ans'
        # print ans
    return ans

是別人寫的,目的是輸入一個 String ,卻會回報此 String 的所有 substring 。例如輸入 abc ,應該會回報 a, b, c, ab, bc 和 abc 。
我加入了大量的 print statement 去看看這個東西怎樣運作,有些成效,不過仍然有點一頭霧水。我發現理解 recursion 的最大困境是這東西很難 hand simulation ,我不能畫個 table 去理解。

  1. 取自 how to think like a computer scientist []