NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » 一般 » 綜合討論區
 程式加速技巧討論

作者 主題: 程式加速技巧討論  (閱讀 22631 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
程式加速技巧討論
« 於: 十一月 28, 2009, 10:50:56 pm »

有鑑於NPSC自2008年起,對於題目的測資有加強,不再像過去只要「解出來」就好,而是要求最有效率的解法,故在此討論一些程式加速的技巧,希望對各位同學有幫助,也歡迎各位分享自己程式加速的技巧。
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
技巧一:使用內建排序法
« 回覆 #1 於: 十一月 28, 2009, 10:56:05 pm »

一般初學者常用的排序外,不外乎是選擇排序法、泡沫排序法或是插入排序法等,這些排序法很簡單易學,但是它的執行速率是O(N^2),對於很多題目來說並不夠快。

幸好,C 或 C++ 裡都有內建一些排序函數,C 裡面有 qsort 函數,C++的STL裡的 <algorithm> 也有 sort 函數,兩者都是O(NlogN)的排序法,只要會用 struct 自定型別,再自定一個比較函數,則可輕鬆使用。詳細的用法,請自行參加書籍或相關網站。
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
技巧二:使用建表
« 回覆 #2 於: 十一月 28, 2009, 11:02:46 pm »

建表法是常用的加速法之一,例如質數的篩法也是類似的觀念,由於NPSC不要求建表的動作必須在程式執行中完成,特別是NPSC2008高中組決賽的題目F「數列」該題,官方版的標準解法就是本地建表,也就是先寫一個程式把表格的內容輸出到檔案裡,再把這些資料當作主程式陣列一開始的值,故在建表後不會再改變內容的情況下,可利用此一技巧來加速。
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
技巧三:IO優化
« 回覆 #3 於: 十一月 28, 2009, 11:11:30 pm »

一般我們討論程式的效能時,多半是用Big-O的量級去分析,但是NPSC有些題目的測資高達數10MB以上,故IO也佔用了不少時間,因此對於這類的題目(例如輸入一個2000x2000以上的二維陣列的題目),必須對IO做優化處理,以減少IO所花費的時間。

一般來說,C++的 cin 速度比 C 的 scanf 來得慢,而 scanf 又比使用 gets、getline 來得慢,故可以針對需要 IO 優化的題目使用適當的 IO 函數來加快處理。

另外,如果是整數的處理,不論是 cin 還是 scanf,都比以字串輸入進來後再自己轉換成整數來得慢。像NPSC2006高中組初賽題目F「營地」該題,因為資料都是一個位數的整數,所以可以用字元的方式來取代以整數的方式輸入,程式可以加快 2~5 倍以上。
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
技巧四:使用 hash 或 map 取代循序搜尋
« 回覆 #4 於: 十一月 28, 2009, 11:28:33 pm »

在某些 Graph 的題目,節點的名稱並不是從 0 開始的編號,而可能是一個字串,這時候常見的做法是用一個表格把字串和編碼做一個對應。然後這樣在使用的時間,由於是一個一個名稱比對下來,其實也是花了不少時間,加上這個動作可能是在迴圈的內層執行,所以無形中讓程式的時間複雜度又多了一個N。

比較快的方法,是可以用 hash 來處理,因為 hash 的時間複雜度是接近O(1)的常數時間,或者也可以用C++的STL裡的 map 來實作這個對應表,map 的用法很類似其他高階 Script Language 裡的 hash,而它的實作應該是B-Tree這種樹狀資料結構,所以時間複雜度是O(logN),也比原本的循序搜尋法的O(N)快上不少。
記錄

lose

  • 新手
  • *
  • 文章數: 12
    • 檢視個人資料
回覆: 程式加速技巧討論
« 回覆 #5 於: 十一月 29, 2009, 09:59:24 am »

關於技巧三:IO優化
在輸入的部份
即使不是 一位數字  也可以加快速度
在ZERO測試 效果算是不錯
在於輸出的部份   
假若只輸出一位數字的話,改用字元的輸出,速度會比較快
代碼: [選擇]
EX:
int t,m;
while(scanf("%d",&t)==1)
  while(t--)
    {
      m=input();
      printf("%d\n",m);
    }
/************************/
正整數
/************************/
long long int input()   
{   
  char cha;   
  unsigned long long int x=0;   
  while(cha=getchar())   
     if(cha!=' '&&cha!='\n') break;   
  x=cha-48;   
  while(cha=getchar())   
    {   
     if(cha==' '||cha=='\n') break;   
      x=x*10+cha-48;   
    }   
    return x;   
}
/*************************/
±整數
/************************/
long long int input()   
{   
  char cha;   
  unsigned long long int x=0,flag=1;   
  while(cha=getchar())   
     if(cha!=' '&&cha!='\n') break;   
   if(cha!='-')
       x=x*10+cha-48; 
   else flag=-1;   
  while(cha=getchar())   
    {   
     if(cha==' '||cha=='\n') break;   
      x=x*10+cha-48;   
    }   
    return x*flag;   
}
/************************/
±浮點數
/************************/
double point()
{
  char cha;
  double poi=0,num=1;
    while(cha=getchar())   
    {   
     if(cha==' '||cha=='\n') break;   
     num=num/10;
     poi=poi+(cha-48)*num;
    }   
    return poi;
}         
double input()   
{   
  char cha,flag=1;   
  double x=0;   
  while(cha=getchar())   
     if(cha!=' '&&cha!='\n') break;   
   if(cha!='-')
       x=x*10+cha-48; 
   else flag=-1;
  while(cha=getchar())   
    {   
     if(cha==' '||cha=='\n') break;   
     if(cha=='.')
      {
        x=x+point();
        break;
      }
       x=x*10+cha-48; 
    }   
    return x*flag;
}

記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 程式加速技巧討論
« 回覆 #6 於: 四月 05, 2010, 06:21:52 pm »

IO 優化有件事要留意一下唷

x=x*10+(c-48)

不然如果是 int input(){

2147483647應該會爆炸 .
記錄

suhorng

  • 初級會員
  • **
  • 文章數: 26
    • 檢視個人資料
回覆: 程式加速技巧討論
« 回覆 #7 於: 四月 05, 2010, 08:34:06 pm »

有差的是乘除法,否則加減法在 x86 平台下是沒差的,

所以就算不括括弧也不會錯。

會爆掉的地方譬如說輸入 -2147483648 就得特殊處理了|||
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: 程式加速技巧討論
« 回覆 #8 於: 四月 05, 2010, 08:50:57 pm »

感謝suhorng神人指點 ^^


是小弟C++學的不精

真是對不起
記錄

ACRash

  • 新手
  • *
  • 文章數: 11
    • 檢視個人資料
回覆: 程式加速技巧討論
« 回覆 #9 於: 十二月 06, 2010, 10:57:24 am »

還有一個更偏門的技巧

陣列索引值比指標取值來的慢

所以說 譬如:

for(int i = 0; i < 1000000; i++) {bla bla bla}

可以改成

for(int *i = ary, *lim = ary + 1000000; i < lim; i++) {bla bla bla}

只需把code中的 ary[ i] 改為 *i 即可.

不過加速的幅度並不大, 除非是執行時間正好卡邊界, 否則沒什麼用.
記錄
+ NPSC補完計劃 » 一般 » 綜合討論區
 程式加速技巧討論