大家可以上去看看
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，讓程式更好看，有空可以看看啦，但我真的如果如書這樣寫出來，我自己都會頭暈吧。
future reading: http://www.wretch.cc/blog/bonddealer/16143955
談到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」是不是被重複算了。
資料集越大，被重複算的運算就越多，程式就越慢。
到這邊是不是有大大已經想到，大的資料集要怎麼處理了呢？
