為什麼OJ上有些人提交的代碼運行那麼快? 有人總結這些技巧么

01-04

比如UvaOJ上 AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: Volume 0. Getting Started 中的題目 10055Hashmat the Brave Warrior 題目很簡單，可是我想了半天也就優化到 run time 0.060，可是為什麼就是有人能做到 run time 0.000 !? 0.02左右的也是一大片。到底是用了什麼trick?

man 一下unlocked_stdio，有驚喜哦！

====================================

scanf讀取的速度還是比不上getchar的，不過因為getchar在POSIX里是線程安全的，由於UVa上judge時必然不會用到單線程，則可以改成getchar_unlocked來進一步加速，然後手工實現「讀取整數、浮點數」。
對於int這種內置的類型而言，可以通過循環展開來加速，當然對於浮點類型也可以，不過效果不如int明顯。

例子：

#include & #include & #include & #include &


#define N 100000000

int a[N];
int main() {

    srand(time(0));

int i; int64_t ans = 0; for (i = 0; i &< N; ++i) a[i] = rand(); clock_t start = clock(); for (i = 0; i &< N; ++i) ans += a[i]; clock_t end = clock(); printf("elapsed %.6lf ", (1.0 * end - start) / CLOCKS_PER_SEC); printf("%llu ", ans); return 0; } /* * -O0: elapsed 0.400270 * -O2: elapsed 0.068826 */

#include & #include & #include & #include &


#define N 100000000

int a[N];
int main() {

    srand(time(0));

int i; int64_t ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0, ans5 = 0, ans6 = 0, ans7 = 0, ans8 = 0, ans9 = 0, ans10 = 0; int64_t ans = 0; for (i = 0; i &< N; ++i) a[i] = rand(); clock_t start = clock(); for (i = 0; i &< N; i += 10) { ans1 += a[i + 0]; ans2 += a[i + 1]; ans3 += a[i + 2]; ans4 += a[i + 3]; ans5 += a[i + 4]; ans6 += a[i + 5]; ans7 += a[i + 6]; ans8 += a[i + 7]; ans9 += a[i + 8]; ans10 += a[i + 9]; } ans = ans1 + ans2 + ans3 + ans4 + ans5 + ans6 + ans7 + ans8 + ans9 + ans10; clock_t end = clock(); printf("elapsed %.6lf ", (1.0 * end - start) / CLOCKS_PER_SEC); printf("%llu ", ans); return 0; } /* * -O0: elapsed 0.137793 * -O2: elapsed 0.045422 */

可見這樣循環展開可以幫助編譯器更好地優化代碼。

還可以使用一些gcc builtin的代碼，例如__builtin_ctz, __builtin_popcount，比自己寫的要高效一點(原諒我不會更高效的實現)。

例子：

#include & #include & #include &


uint32_t cnt(uint32_t x) {

    uint32_t ret = 0;

    while (x &> 0) {

        x = x - 1;

        ++ret;

    }

    return ret;

}
int main() {

    int i;

clock_t start = clock(); for (i = 0; i &< 0xffffff; ++i) fprintf(stdout, "%u ", __builtin_popcount(i)); clock_t end = clock(); fprintf(stderr, "%.6lf ", (end * 1.0 - start) / CLOCKS_PER_SEC); start = clock(); for (i = 0; i &< 0xffffff; ++i) fprintf(stdout, "%u ", cnt(i)); end = clock(); fprintf(stderr, "%.6lf ", (end * 1.0 - start) / CLOCKS_PER_SEC); return 0; } /* * 使用時請將stdout重定向至/dev/null. * -O0: 內置 = 1.795766; 手工實現 = 2.541025; * -O2: 內置 = 1.677343; 手工實現 = 1.801183; */

現代CPU基本都有分支預測的功能了，倘若能夠利用好這一點，則速度可能會更加得快。

現在有一個問題：有2個長度為n的整形數組，現要將它們交換a[i], b[i]，使得b[i]&>=a[i]恆成立。一開始可能會這樣寫：

void minmax(int a[], int b[], int n) { int i; int t; for (i = 0; i &< n; ++i) { if (a[i] &> b[i]) { t = a[i]; a[i] = b[i]; b[i] = t; } } } /* 分支誤判高,懲罰嚴重 */

而如果這樣寫:

void minmax(int a[], int b[], int n) { int i; int _min, _max; for (i = 0; i &< n; ++i) { _min = a[i] &< b[i] ? a[i] : b[i]; _min = a[i] &< b[i] ? b[i] : a[i]; a[i] = _min; b[i] = _max; } } /* 使用了條件數據傳送，真的可以提高性能 */

（以上兩段代碼來自CSAPP）

註：以上代碼均在 -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE 編譯選項下測試完成。

===============================================================

編寫對cache友好的代碼可又是一個能加速的利器。

例如，以前的矩陣相乘（樸素）我是這樣寫的：

void foo() { int a[N][N], b[N][N], c[N][N]; memset(c, 0, sizeof(c)); for (int i = 0; i &< N; ++i) { for (int j = 0; j &< N; ++j) { for (int k = 0; k &< N; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } }

我以為沒有什麼，直到我看了CSAPP，原來上面這個版本對cache不太友好，沒有利用好數組b的那一行cache。

void foo() { int a[N][N], b[N][N], c[N][N]; memset(c, 0, sizeof(c)); for (int k = 0; k &< N; ++k) { for (int i = 0; i &< N; ++i) { int t = a[i][k], *p = b[k]; for (int j = 0; j &< N; ++j) { c[i][j] += t * p[j]; } } } }

^ 這個版本儘可能地利用了c、b的cache。

^ 以上2圖來自CS:APP第二版432頁..具體的分析也在這頁上。

使用分塊來提高時間局部性

若能夠將矩陣分塊來乘，這樣不僅可以（可能）使得L1容納這個塊，使得速度提升，還優化了時間複雜度...

blablabla...上面這些其實對題主的幫助很小啊！然後就沒有然後了啊！

一個重要技巧是優化輸入…… 把scanf改成getchar暴力實現會改善許多……

一個技巧不過估計都知道就是內存管理，別用malloc或者new，都用靜態的

如果極限要求速度的話，盡量減少STL的使用

一個比較tricky的技巧是優化一些定址，這是我常用的。譬如：

for (int i = 0; i &< 100; i++) a[X][Y][i] = i

可以優化成

int helper = a[X][Y]

for (int i = 0; i &< 100; i++) helper[i] = i;

或者

map& mp;

if (mp.find(x) != mp.end()) cout &<&< mp[x] &<&< endl

可以優化成

map&::iterator it = mp.find(x);

if (it != mp.end()) cout &<&< mp-&>second &<&< endl;

等

其他的暫時想不到特別系統的了，大概還是一些程序邏輯的簡化。

用gnu prof 或者 VC的 profiler 跑一跑，看一看，會有幫助

0.02的不知道是怎麼做的，我只能做到0.042，排名是36..

沒在代碼的層次上優化過，基本上還可讀，可能改下細節能到0.03x

思路是整個過程用字元串操作，不轉化成整形，能省下很多時間，

具體做法是按照我們算豎式那樣，從後向前按位進行計算，結果是負的就借位。

輸入輸出使用fgets、fputs，開銷比較小。

附上代碼：

#include& #define MAX_INPUT 24 #define MAX_OUTPUT 12 void calc(char *lower, char *greater, int low_len) { char out[MAX_OUTPUT]; char result[MAX_OUTPUT]; char ch; int i, len_out; for(i = 0; i &< low_len; ++i) { char a = *(lower - i); char b = *(greater - i); out[i] = b - a + "0"; } for( ; (ch = *(greater - i)) != " "; ++i) { out[i] = ch; } out[i] = ""; len_out = i; for(i = 0; i &< len_out; ++i) { if(out[i] &< "0") { out[i] += 10; out[i+1] -= 1; } result[len_out - i - 1] = out[i]; } result[len_out] = " "; result[len_out+1] = ""; for(i = 0; result[i] == "0"; ++i); if(result[i] == " ") --i; fputs(result + i, stdout); } int main() { char _buffer[MAX_INPUT]; char *buffer = _buffer + 1; _buffer[0] = " "; while(fgets(buffer, MAX_INPUT, stdin)) { char *lower, *greater; int i, j, len; for(i = 0; buffer[i] !=" " ; ++i); lower = buffer + i - 1; len = i; for(j = i ; buffer[j] != " "; ++j); greater = buffer + j - 1; while(j - i - 1 &<= len) { char *tmp; if(j - i - 1 == len) { int k; char ch; for(k = 0; k &< len ; ++k) { if(lower[2 + k] != buffer[k]) break; } if(k==len || lower[2+k] &>= buffer[k]) break; } tmp = lower; lower = greater; greater = tmp; len = j - i - 1; break; } calc(lower, greater, len); } return 0; }

應該不是什麼trick 就是運氣好

事實上我做過一些測試在POJ上交打表or各種常數優化以期跑得快些但實際上在64ms以下就是純憑RP了

你可以拿A+B試試 0MS 16MS 32MS（甚至更慢）隨機出現（這些數字有點奇怪應該只是恰巧，但我覺得連續交對縮短這些時間還是有一定幫助的至少緩存是有了我自己寫的checker會運行兩遍取第二遍的時間以利用緩存= =）

因為對於運行得如此快的程序內核對進/線程的調度已經會明顯地影響評測程序的測時精度

尤其是在下午或者晚上這種伺服器負載大的時候 UVa這樣全球級別的就沒有下午晚上了 POJ的話還能利用深夜和清晨來提高一點點咩哈哈