11
this linkで指定されたコーディングコンペでは、多くのデータをstdinに読み込み、いくつかの計算を行い、多くのデータをstdoutに表示する必要があります。Fast I/O in c、stdin/out
私のベンチマークでは、できるだけ最適化しようとしていますが、ほとんどの時間はかかります。
あなたが入力として持っているものは、文字列（1 <= len <= 100'000）であり、qの列はqのもと1 <= q <= 100'000です。
私は100倍大きいデータセットで私のコードをベンチマーク（LEN = 10M、Q = 10M）、これが結果です：私自身の整形と数の解析インラインを実装することにより
Activity time accumulated
Read text: 0.004 0.004
Read numbers: 0.146 0.150
Parse numbers: 0.200 0.350
Calc answers: 0.001 0.351
Format output: 0.037 0.388
Print output: 0.143 0.531
私は得ることができましたprintfとscanfを使用した場合、時間の1/3まで減少します。
私のソリューションをコンペティションのウェブページにアップロードしたとき、私のソリューションは1.88秒かかりました（22データセットを超える合計時間だと思います）。高得点を見ると、0.05秒で完了したいくつかの実装（C++で）が、私より約40倍速いです！そんなことがあるものか？
私は2スレッドを使用して速度を上げることができたと思いますが、stdoutから読み込みながら、計算とstdoutへの書き込みを開始できます。しかし、私の大規模なデータセットの理論的な最良のケースでは、min(0.150, 0.143)に時間が短縮されます。私はまだ最高得点には至っていません。
以下の画像では、消費時間の統計を見ることができます。
プログラムは、このオプションを使用してウェブサイトでコンパイルさ：
gcc -g -O2 -std=gnu99 -static my_file.c -lm
と、次のようにタイミング：
time ./a.out <sample.in> sample.out
私のコードは次のようになります。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN (100000 + 1)
#define ROW_LEN (6 + 1)
#define DOUBLE_ROW_LEN (2*ROW_LEN)
int main(int argc, char *argv[])
{
int ret = 1;
// Set custom buffers for stdin and out
char stdout_buf[16384];
setvbuf(stdout, stdout_buf, _IOFBF, 16384);
char stdin_buf[16384];
setvbuf(stdin, stdin_buf, _IOFBF, 16384);
// Read stdin to buffer
char *buf = malloc(MAX_LEN);
if (!buf) {
printf("Failed to allocate buffer");
return 1;
}
if (!fgets(buf, MAX_LEN, stdin))
goto EXIT_A;
// Get the num tests
int m ;
scanf("%d\n", &m);
char *num_buf = malloc(DOUBLE_ROW_LEN);
if (!num_buf) {
printf("Failed to allocate num_buffer");
goto EXIT_A;
}
int *nn;
int *start = calloc(m, sizeof(int));
int *stop = calloc(m, sizeof(int));
int *staptr = start;
int *stpptr = stop;
char *cptr;
for(int i=0; i<m; i++) {
fgets(num_buf, DOUBLE_ROW_LEN, stdin);
nn = staptr++;
cptr = num_buf-1;
while(*(++cptr) > '\n') {
if (*cptr == ' ')
nn = stpptr++;
else
*nn = *nn*10 + *cptr-'0';
}
}
// Count for each test
char *buf_end = strchr(buf, '\0');
int len, shift;
char outbuf[ROW_LEN];
char *ptr_l, *ptr_r, *out;
for(int i=0; i<m; i++) {
ptr_l = buf + start[i];
ptr_r = buf + stop[i];
while(ptr_r < buf_end && *ptr_l == *ptr_r) {
++ptr_l;
++ptr_r;
}
// Print length of same sequence
shift = len = (int)(ptr_l - (buf + start[i]));
out = outbuf;
do {
out++;
shift /= 10;
} while (shift);
*out = '\0';
do {
*(--out) = ""[len%10];
len /= 10;
} while(len);
puts(outbuf);
}
ret = 0;
free(start);
free(stop);
EXIT_A:
free(buf);
return ret;
}
なぜ個々のintにメモリを割り当てていますか？あなたはどんなシステムにいますか？ Linuxでは、stdioはWindows上ではiostreamsより速く高速ですが、Windowsではiostreamがstdioをoutpeformします。 POSIXではstdioが呼び出しに対して再帰的ロックを使用する必要があるため、iostream（AFAIK）にはそのような要件は存在しないため、IO関数のロック解除されたバリアント（putsの代わりにputs_unlockedなど）を使用すると、stdioをいくぶん高速にすることができます。 – PSkocik
ループのたびに出力をしているようです。高速化のためにメモリを交換し、より大きなバッファを割り当ててから、出力全体を一度に印刷するとどうなりますか？また、実行可能な出力が多すぎる場合でも、実質的にバッファリングによって出力を統合することができます。 'puts'が実際にあなたのボトルネックになっていれば、これは問題を解決します。私はそれらの時代に到着するためにどのように測定しているのか分かりません。すべての操作は、例えば「印刷出力」の測定に含まれていますか？ –
マイナー： 'cptr = num_buf-1;'は未定義の振る舞いです。 – chux