資訊學院的30門課-演算法與google code jam

Google Code Jam 2009我參加過一次，依當時的評分標準，至少要能寫出一題，能夠在限定時間內跑完的code，才能晉級。但是幾乎都是要用dynamic programming的技巧，我用遞迴解一題後，想當然爾，效能不佳，所以我就放棄了。

大家可以上去看看
http://code.google.com/codejam/

既然是軟體，就不能不講到正在全球各地舉行的google code jam 2011，

難度極高，在資格賽的幾個題目中，解出來的難度不高，但是要在極嚴格的執行時間跑出來，

就不能夠亂寫囉，除了要有一台不錯的運算平台之外，挑選的程式語言也很重要，例如很多人用C/C++，

但是最重要的莫過於演算法了。因為這些題目都會讓人無意間進入一種迷思，大部分是divide and conquer的題目，

但是重複計算了一部的運算而不自知。而且某些題型在小範圍的資料中，可以使用遞迴解，但是太多層function call又往往使效能不彰。

演算法教科書提到dynamic programming，當初課本只有兩個範例，所以其實讀的不是很懂，這兩天我又去書局罰站了，翻了一下培養與鍛鍊程式設計的邏輯腦。其實只是用二維或者三維array把之前算過的值儲存起來，碰到一樣的狀況，就直接查表就好，大家都知道查表可以很快，就不用丟到遞迴裡或者loop裡去跑了。不過我相信以mis的programming應用角度而言，不要說dynamic programming，連遞迴我也只用過兩次。

另外瀏覽一下放在他隔壁的Short Coding 寫出簡捷好程式-短碼達人的心得技法。

不過這本書是會讓人頭暈的書，很多觀念以前都讀過，

有些小技巧的確在不失可毒性的狀況下，可以讓程式更短，甚至縮短巢狀level，讓程式更好看，有空可以看看啦，但我真的如果如書這樣寫出來，我自己都會頭暈吧。

http://job.achi.idv.tw/2011/09/26/%E8%AE%80%E5%9F%B9%E9%A4%8A%E8%88%87%E9%8D%9B%E9%8D%8A%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88%E7%9A%84%E9%82%8F%E8%BC%AF%E8%85%A6%EF%BC%9A%E4%B8%96%E7%95%8C%E7%B4%9A%E7%A8%8B%E5%BC%8F%E8%A8%AD%E8%A8%88/

future reading: http://www.wretch.cc/blog/bonddealer/16143955

http://blog.chinatimes.com/charles0714/archive/2011/09/12/297799.html

談到google程式大賽

雖然我不曉得程式怎麼寫效能才高，但可以分享為甚麼我的程式跑的慢，為甚麼大的資料集運算很慢，

一般網頁或視窗是程式設計課程中，都沒有注重在如何讓程式跑的最快，有志參加的coder，一定要記得這些重點才能晉級。

2011我做的是第三題

Problem C. Candy Splitting

http://code.google.com/codejam/contest/dashboard?c=975485#s=p2

提示一下，弟弟的加法就是XOR，哥哥才會進位的加法。這樣題目就容易理解了。

像我這種程式效能上的差異，不是單純使用高級硬體就能cover掉的。

#include

#include

#include

using namespace std;

int main(int argc, char *argv[])

{

int compute(int *candy, int candyNum, int s, int x, int p, int max);

FILE *input;

int i, j, x, sum, ans;

int looptime, candyNum;

int candy[1001];

input = fopen("D:\\Dev-Cpp\\3-test.txt","ro");

fscanf(input,"%d",&looptime);

for(i=0; i

fscanf(input,"%d",&candyNum);

sum = 0;

x = 0;

for(j=0; j

fscanf(input,"%d",&candy[j]);

// sum += candy[j];

}

for(j=0; j

//printf("%d ", candy[j]);

sum += candy[j];

x ^= candy[j];

}

//printf("=%d",sum);

ans = compute(candy, candyNum, sum, x, 0, 0);

printf("Case #%d: ", i+1);

if(ans==0) {

printf("NO\n");

}else{

printf("%d\n", ans);

}

fflush(stdout);

}

system("PAUSE");

return EXIT_SUCCESS;

}

int compute(int *candy, int candyNum, int s, int x, int p, int max) {

int max1,max2;

int a, b;

if( candyNum == 0 ) {

return max;

}

a = x ^ candy[0];

b = p ^ candy[0];

if(a == b) {

max = (max<(s - candy[0]))? (s - candy[0]): max;

}

//printf("[ a=%d, b=%d, x=%d, p=%d, max=%d ]", a, b, x, p, max);

max1 = compute(candy+1, candyNum-1, s-candy[0], a, b, max);

max2 = compute(candy+1, candyNum-1, s, x, p, max);

return (max1>max2)?max1:max2;

}

這邊用到recursive去解，雖然CS教科書上recursive的例子很多，但在google code jam的題目中，

幾乎都是效能殺手。

max1 = compute(candy+1, candyNum-1, s-candy[0], a, b, max);

max2 = compute(candy+1, candyNum-1, s, x, p, max);

因為例如「第三堆到第六堆的XOR」與「第四堆到第七堆的XOR」，其中「第四堆到第六堆的XOR」是不是被重複算了。

資料集越大，被重複算的運算就越多，程式就越慢。

到這邊是不是有大大已經想到，大的資料集要怎麼處理了呢？