input integers
cin を使った入力がものすごく遅いので、ICPC系の問題を解く時に問題になってくることがあります。
普通はscanfを使っておけば問題ないのですが、まだ改善の余地があるので整数入力に特化した関数を自作してみました。
// integer (10進, 非負, 桁あふれしないこと前提) // を標準入力から読み込む bool geti(int &n) { bool flag = false; // 読み込みに成功したか int m = 0, ch; while ((ch = getchar()) != EOF) { if ('0' <= ch && ch <= '9') { flag = true; m = m * 10 + ch - '0'; } else if (flag) break; } n = m; return flag; }
- 数字以外は切り捨てるので、入力として数字以外の文字も使うときは ungetc とかで戻す必要がある。
- 符号を扱うなどの処理は入力形式に合わせて適宜補完。
- C互換にしたければ bool → int , 参照渡し→ポインタ渡しに。
↓のようなループで、scanf, cin と読み込む時間を比較。
while (geti(n)) ; while (scanf("%d",&n) == 1) ; while (cin >> n) ;
手元の計算機で 30,000,000 個ぐらいの整数を読み込ませてみたところ、結果は次の通り。
# geti
real 0m4.513s
user 0m4.396s
sys 0m0.116s
# scanf
real 0m7.680s
user 0m7.516s
sys 0m0.164s
# cin
real 0m29.542s
user 0m29.434s
sys 0m0.112s
やはり cin(というか operator>> )が遅い遅い。
追記:
出力関数も作りました。