2011/10/16

資訊學院的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,讓程式更好看,有空可以看看啦,但我真的如果如書這樣寫出來,我自己都會頭暈吧。




談到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」是不是被重複算了。
資料集越大,被重複算的運算就越多,程式就越慢。
到這邊是不是有大大已經想到,大的資料集要怎麼處理了呢?

沒有留言:

張貼留言