Friday, March 11, 2011

讓 Perl 走進你的生活

本文是用來回顧剛接觸 Perl 的心得,以及推薦新手跳入 Perl 所寫的。

從 1987 年 Larry Wall 發明 Perl 以來,今年 Perl 已經24 歲,可能比你我還年輕,不過以電腦語言的角度來看算是老了。筆者在多年前就已經接觸過 Perl,可惜當時覺得程式艱澀難懂,不如 C 來的直接。直到最近因工作需要重新學習,才發覺過往的偏見。

借用 Alan Perlis 的話: "A language that doesn't affect the way you think about programming, is not worth knowing." (若是一種語言不會影響你對寫程式的想法,那便不值得學習。)
而讓我改變對寫程式的想法的,便是 Learning Perl 這本書。

Learning Perl的作者 Randal L. Schwartz (以下簡稱 Randal)在書的第一章就指出,Perl是非常高階的語言,所以code的密度很高,長度只有相對應的C的四分之一到四分之三。我認為用一個中文字來表現Perl的編程精神就是"短"。短程式的好處不少,不論是閱讀時間或是寫程式的時間都比較短。這就像是自然語言中的成語,可以把一段故事濃縮成寥寥數字。

借用 Randal 第一章的程式碼來說明


while (<>) {
  chomp;
  print join("\t", (split /:/)[0, 2, 1, 5] ), "\n";
}

希望第一次看到 Perl 的朋友不要轉頭離開。
任何程式語言的目的都是為了幫助使用者解決問題,而不是折磨使用者。
這段Perl程式目的是: 依序讀取命令列中每個檔案的每一行,去除尾部的換行符號厚,依冒號分隔欄位,並列印出其中四個欄位的值。假設我們有下的檔案 data.txt:

Id:Name:Age:Gender:Height:Weight

001:John:20:Male:180:70
002:Alice:17:Female:160:50



當我們在命令列下這樣的指令時:

> perl program.pl data.txt

結果會是:

Id      Age     Name    Weight
001     20      John    70
002     17      Alice   50


如果你看到這裡,一定會想知道這段程式要怎麼解析,<>是甚麼? chomp是甚麼? join 和 split 是甚麼?
在此筆者不會做完整解釋,請隨著 Randal 一同進入 Perl 的世界即可,那過程會比我現在說明得更加有趣數十倍。不過我想帶給各位Perl這種所謂"高階"程式的精神,就是要符合使用者的自然習慣。我們可以用一種很不嚴謹的角度來看剛才這段程式。首先我們想要一行一行處理資料,所以就需要一個 while 迴圈,由於我們要從命令列指定的檔案讀出資料,這整件事就用一個名詞 <> 來表示,讀到一行資料以後要用冒號分隔,所以就使用 split。

至於讀者可能會問說,那讀入的資料是暫存在哪個變數呢? Perl認為這是可以省略的變數,所以動了一些手腳。就好比我們在日常生活中,你拿起一個裝水的杯子,下一個動作是喝水,你不需要再多說明我是從手上的杯子喝水的。

最後結尾放上 Learning Perl 這本書的封面,各位請不要拿錯了呀 :)

Saturday, February 12, 2011

shuffling / random permutation

又到了野人獻曝的時間了 :)

最近和前輩在聊面試有那些問題可以出
前輩提到一個經典的問題:如何隨機排序一組撲克牌?
換個說法,就是要產生一種52張牌的排列。

前輩提到這個問題可以用排序演算法來解決。
我上維基查了一下,果然在Knuth的大作 The art of computer programming 中有給出兩個演算法 [1]。

假設我們要排序的陣列是 src,大小為N,以 0-based 作為索引方式。
第一個演算法是這樣的:產生另外一個陣列 a,給 a 中的每一個元素一個亂數,接下來對 a 排序,排序的同時將 src 內元素依相同順序移動。排序時可以選用任意的演算法,因此可以在 O(N lg N) 時間內完成。

Knuth 書中的第二個方法更有效率,只需 O(N) 時間即可完成。演算法是: 從 i=N-1 開始依次往前走訪陣列的每個位置,對於每個 i ,產生一個亂數 0<=j<i ,並交換 src[i], src[j]。以 python 來寫的話會像這樣:

for i in range(N-1, 0, -1):
    j = random.randint(0,i)
    src[i], src[j] = src[j], src[i]

有看過這些演算法的朋友會覺得到目前為止都是老調重彈,沒錯,請在往下看。我認為這兩個演算法其實是有關連的,第二個方法可視為第一個方法的特例: 也就是使用 selection sort 來做排序。selection sort 的想法為,每次從未排序的數列中挑出最大(或最小)的一個,將其移到排序完的數列。用簡單的例子來表現:

假設我們要按遞增順序排序這四個數字: 3 2 4 1

第一步是找出最大的數字 4,並放到陣列尾端
3 2 (4) [1] => 3 2 1 | 4

第二步會找到 3,並放到 4 的前面
(3) 2 [1] | 4 => 1 2 | 3 4

接下來會找到 2,順序不變
1 (2) | 3 4 => 1 | 2 3 4

排序完成!

觀察每一步的過程,可分成兩階段,第一階段是找出未排序數列中最大的數字,第二階段是交換到排序數列的開頭。其中第一階段原本要花費 O(n) 的時間以找出最大的值所在的位置,但是既然在第一個演算法中,每個位置的值都是亂數,所以我們可以直接從中隨機挑一個位置當作是最大的數字,這樣有相同的效果,而且時間複雜度只有 O(1)。

好,獻曝完畢 :p

以 selection sort 能夠說明第二個演算法是第一個方法的特例,也許嘗試其他排序法會帶來不同的發現呢。

[1] http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm

Friday, January 14, 2011

Kurukshetra Athena 來自印度的數學程式競賽

上週從 Project Euler 傳來一個數學程式競賽的消息。
競賽的網址如下:
http://www.athena.kurukshetra.org.in/

這個競賽的題目都是數學相關問題,包含動態規劃、數論和許多領域,厲害的人也許能夠不依賴電腦就算出答案哩。雖然今年比賽已經結束了,有興趣的人還是可以去看看題目,並期待明年的比賽!

我今年沒有花很多時間,一周的時間內只完成了七題 :p
Score: 700 (完成七題)
Rank: 241

Question 6

There are 52735727364727372 students and 2889221271829121 teachers in a school . On children's day each teacher brings x toffees with him/her . All the toffees are collected and distributed equally to all the students . At the end it was found that there was exactly one toffee remaining .
What is the least possible value of x ?


我的想法
恩,這是很經典的一個問題。
首先我發現到分配之後只剩下一顆太妃糖,這表示老師的數目a和學生的數目b是互質的。接著把未知數 x 和 a,b 關聯起來,並且引入一個輔助變數 y 來表示每個學生所拿到的太妃糖數目,寫成數學形式是:
ax-by=1

接著我去查詢兩個互質的數有甚麼關連,發現了一個形式相似的公式: Bézout's identity,此公式說對於任意非零整數a和b,令其最大公因數為d,則存在x和y使得 ax+by=d。

要解出 x 和 y 可使用 Extended Euclidean algorithm,用 python 來寫的話只需要六行,而且還支援大數運算,真是相當輕鬆。

def extended_gcd(a,b):
  """Return x,y satisfy ax+by=gcd(a,b)"""
  if a % b == 0:
    return 0,1
  else:
    r = extended_gcd(b, a % b)
  return r[1], r[0] - (r[1] * (a / b))


找到 x, y 之後回到原來的問題。理論上符合 ax+by=d 的 (x,y) 有無限多組,此題目要求我們找的 x 為最小的正整數,剛好 extended_gcd 演算法得到的就是題目所要的。

Saturday, November 13, 2010

字串遊戲 -- 如何快速計算文章中每個字出現的次數?

最近讀了 Bentley 所寫的 Programming Pearls 的專欄15,討論的主題為字串。這本書在台灣的能見度似乎不高,基峰出了一本中譯本之後很快就絕版了,想買都買不到,現在我手上是一本英文版加上朋友從借來的中譯版:)
這本是值得一看的好書,強烈推薦。

看完專欄15後,忍不住手癢動手實驗一下。
第一小節的問題是,給你英文聖經的電子檔,請找出書中一共有多少個單字? 出現頻率最高的單字為何?

首先我到 http://printkjv.ifbweb.com/ 下載整本文字檔格式的聖經
此版本的聖經共有 4,397,206 個字元。

書中提供的第一個小程式是 C++ 版本,使用 map 作為存放單字的資料結構。map 的實作為平衡二元搜尋樹,所以加入單字或是尋找已出現過的單字的複雜度都為 O(log n)。
以下的程式是我稍微修改過的版本:

inline bool isletter(char c)
{
  return (c>='a' && c<='z') || (c>='A' && c<='Z');
}
string trim_nonword_char(string s)
{
  string sout;
  for(unsigned int a=0; a<s.size(); a++)
    if (isletter(s[a]))
  sout.push_back(s[a]);
  return sout;
}
void main(void)
  typedef map<string, int> mymap;
  mymap M;
  mymap::iterator j;
  string t;
  while(cin >> t)
  {
    string tb = trim_nonword_char(t);
    if (tb.size() > 0)
      M[tb]++;
  }
  int totalwords = 0;
  for (j=M.begin(); j != M.end(); j++)
  {
    cout << j->first << " " << j->second << "\n";
    totalwords += j->second;
  }
  cout << "Total number of words = " << totalwords << endl;
}

我們的mymap中,key的型態是string,而value的型態是int,用來儲存出現次數。18~23行從標準輸入讀入一個word,去除非英文字母字元後放入map之中。利用了map的強大能力,緊緊短短數行程式就完成了這個工作。25~29行印出每個word和他出現的次數,由於採用二元搜尋樹的實作,你會發現 word 是依照順序由小到大排序的。

至於第二個問題,如何依照找出頻率最高的單字,Bentley 建議可以使用另外一個map,使用頻率做為key,出現的單字做為value。由於數個單字有可能出現相同次數,所以我們使用 vector<string> 做為value來儲存這些單字。依此實做的C++程式僅有四行。

map<int, vector<string>> cmap;
for (j=M.begin(); j != M.end(); j++)
{
    cmap[j->second].push_back(j->first);
}

注意map的順序是由小到大,所以cmap裡面最後面才是出現字數最多的單字。

現在我們可以回答開頭的問題:此檔案共有804875個單字,其中有14683個不重複單字,出現頻率最高的十個單字為:


62910 the
39290 and
35055 of
13783 to
12884 that
12863 And
12547 in
9773 shall
9756 he
8985 unto

在我的電腦上處理這個檔案所花的時間為1.1秒,拜硬體的進步所賜,比起 Bentley 十年前所得到的7.6秒快了近十倍。

這就是最快的方法了嗎? 非也,Bentley在書中提到可以用 hash 取代 map 來加快速度。

Sunday, October 24, 2010

Visual C++ 2010 Express 使用

這篇文章零碎紀錄了一些初學 Visual C++ 2010 Express 的事項。

Q: IDE 的選單變的好簡潔,一些項目都不見了,要怎麼找出來?
A: 使用 Tools->Settings->Expert Settings ,從預設的 Basic Settings 換成 Expert Settings。

Q: 我沒有辦法直接設定全域的路徑。在 Tools->Options->Projects and Solutions->VC++ Directories 中無法編輯。
A: Visual C++ 2010 做了一些更動,必須要在Property Manager中修改,詳情請參考 VS Project Team Blog 的文章。

Q: 哪邊可以找到 IDE 的配色
A: 推薦 Studio Styles。我是選用 Son-of-obsidian 這個主題。

Saturday, October 23, 2010

加減乘除需多久? -- 估計C語言中基本運算所需的時間

隨著個人電腦的時脈不斷增加,同一個程式的執行速度也越來越快,但是你可有估計過,在現今 2GHz 的 CPU 上,執行一個C語言的加法指令要花多少時間? 而乘法、除法要花多少時間呢?

在 Jon Bentley 的經典著作 Programming Pearls 中,他給了一個範例程式 timemod.c (註1) 來估計計算所需的時間成本。他的方法是跑一個雙層 for 迴圈,在裡面執行各種運算,並計算所花費的時間。

我以一台2009年的個人電腦來做實驗,
CPU為 Intel Core 2 Quad Q8200,時脈為 2.33GHz,Cache大小如下:
  L1 Data Cache = 4*32 KBytes
  L1 Inst. Cache = 4*32 KBytes
  L2 Cache=2048 KBytes*2
編譯器為Visual C++ 2010 Express,Optimization選項全部關掉。


以下為列出各種運算的執行時間,單位均是奈秒(nanosecond):



C Time Cost Model, n=5000
Integer Arithmetic (n=5000)
 {}                    44    44    45    44    45     1.8
 k++                   60    59    57    55    57     2.3
 k = i + j             65    65    65    65    65     2.6
 k = i - j             65    65    65    65    65     2.6
 k = i * j             64    65    65    65    64     2.6
 k = i / j            106   102   100   100    91     4.0
 k = i % j            114   101   100   100   100     4.1
 k = i & j             65    65    65    64    65     2.6
 k = i | j             65    65    65    65    64     2.6

首先看整數運算,先看最上面的藍色底色部分,{}是指兩層空迴圈所消耗的時間。前面五個數字是執行n^2=25000000次花的時間(milliseconds),一共執行五次,最後面的數字是統計這五次執行總共花費的時間,計算每次迴圈內部所花的時間(nanoseconds)。
第二行是在迴圈中放入單一的指令 k++,由最後的數字可知迴圈內部花費了 2.3-1.8 = 0.5 nanoseconds(ns)。相較於 Bentley 的結果是45倍的速度!
接下來是加法和減法,一個指令花費約 0.8ns。令我有點驚訝的是乘法和加法一樣快。至於除法也很快,一個的花費是 2.2ns,不過是加法的 2.75 倍而已。取餘數和除法幾乎相同。


Floating Point Arithmetic (n=5000)
 fj=j;                 87    87    88    87    89     3.5
 fj=j; fk = fi + fj;   87    86    86    86    86     3.4
 fj=j; fk = fi - fj;   87    86    86    86    86     3.4
 fj=j; fk = fi * fj;   88    87    88    88    88     3.5
 fj=j; fk = fi / fj;  216   215   215   215   215     8.6

浮點數加、減、乘法花費 1.6ns。


Array Operations (n=5000)
 k = i + j             65    65    65    64    64     2.6
 k = x[i] + j          75    75    76    75    75     3.0
 k = i + x[j]          75    75    76    75    76     3.0
 k = x[i] + x[j]       88    86    86    86    86     3.5


Comparisons (n=5000)
 if (i < j) k++        70    70    70    70    70     2.8
 if (x[i] < x[j]) k++  86    86    75    96    86     3.4

原本以為 if 很慢,沒想到只花了 2.8-2.3 = 0.5 ns。

Array Comparisons and Swaps (n=5000)
 k = (x[i]<x[k]) ? -1:1  119   120   119   120   119  4.8
 k = intcmp(x+i, x+j)    141   140   140   140   140  5.6
 swapmac(i, j)           131   131   131   131   131  5.2
 swapfunc(i, j)          224   226   224   217   231  9.0
Max Function, Macro and Inline (n=5000)
 k = (i > j) ? i : j   91    92    92    93    92     3.7
 k = maxmac(i, j)      97    97    97    97    97     3.9
 k = maxfunc(i, j)    184   185   185   185   185     7.4
Math Functions (n=1000)
 fk = j+fi;             3     2     2     3     3     2.6
 k = rand();           27    27    27    27    27    27.0
 fk = sqrt(j+fi)       24    23    23    24    24    23.6
 fk = sin(j+fi)        44    44    44    44    44    44.0
 fk = sinh(j+fi)      475   476   475   474   475   475.0
 fk = asin(j+fi)       60    60    60    60    60    60.0
 fk = cos(j+fi)        44    44    45    44    45    44.4
 fk = tan(j+fi)        56    59    55    56    56    56.4
Memory Allocation (n=500)
 free(malloc(4000));    85    83    85    84    85   337.6
 free(malloc(16000));   83    83    83    82    83   331.2
 free(malloc(64000));   97    97    98    97    96   388.0
 free(malloc(128000));  94    95    94    94    93   376.0
Secs: 18.17

記憶體配置花費的時間和大小有關,在16KBytes以下需要花費約340ns,在128KBytes左右增加為380ns。

參考資料
[1] 關於此程式的詳細說明,請見 Programming Pearls 的附錄3

Friday, October 15, 2010

推薦 Linux入門書籍 -- Linux kernel in a nutshell

有興趣學習Linux的朋友,推廌可以從"Linux kernel in a nutshell"(註1)這本書開始看。無須大量基本知識,只需要基本的指令操作就可以開始動手編譯、設定kernel。而且還不到200頁,很快就能夠看完。

不過我一開始遇到一點麻煩。由於書中使用的kernel版本為2.6.18,所以我去找了Ubuntu 6.10(2006年10月發行的版本),安裝好了之後發現沒辦法編譯程式,理由是沒有安裝libc6-dev套件。
嘗試使用下面的指令安裝
$ sudo apt-get install libc6-dev

但是套件已經找不到了,就錯誤訊息來看,我認為是此版本的套件更新服務已經終止。到wikipedia查了一下之後得到確認(註2)。原來ubuntu對於每個版本的支援期間才約兩年而已。不過其中有特別為伺服器設計的Long Term Support (LTS)版本,像6.06, 8.04, 10.04這三個,就有約五年的更新支援。
所以我有兩個選擇,一個是採用6.06,另一個是改用最新的版本10.10。

好,實際跑跑看。我使用VirtualBox來建立虛擬硬碟,編譯kernel 2.6.35-2在我的Intel Q8400上花了約40分鐘。Try it yourself!

參考資料
[1] 此書可由作者 Greg Kroah-Hartman 的網頁下載
[2] 請參見Wikipedia:Ubuntu的發行版本