C++ 與 Python 的輸入輸出優化

2020-12-10 15:24:46 by Akira

一件很多程式解題的新手甚至中手都不知道卻又很重要的事情就是... 預設情況下，C++ 的 cin 速度非常的慢，慢到可以讓人光是讀 input 就已經超時的地步！

而解決這個問題的方法就是在使用 cin 之前先執行 ios::sync_with_stdio(false) 這個命令，並且不再使用任何 C 的 I/O 函式 (例如：scanf)。

事實上，C++ 除了 cin 之外，endl 也是一個速度超慢的東西，可以使用 '\n' 代替。不過 endl 以及預設情況下的 cin 到底有多慢呢？我們不妨來做些實驗看看。除了 C++ 以外，我們也可以順便比較一下 Python 的 print/write 與 input/readline。

實驗環境

OS: Ubuntu 16.04
CPU: Intel(R) Core(TM) i5-7400T CPU @ 2.40GHz
g++ 5.4.0
Python 3.5.2

實驗項目

輸入

程式行為

讀入 \(N = 10^7\) 個 int 並輸出它們全部 XOR 起來的結果，以 EOF 代表輸入完結。

為避免磁碟讀取速度的影響，輸入資料檔會放在 tmpfs。

比較對象

C
- in-c
C++
- in-cpp
- in-cpp +NS
- in-cpp +NT
- in-cpp +NS +NT
Python
- in-py3-input
- in-py3-input-no_try
- in-py3-readline

in-c 使用 scanf，in-cpp 使用 cin，in-py3-input 使用 input，in-py3-readline 使用 sys.stdin.readline。
+NS 代表啟用 ios::sync_with_stdio(false)，+NT 代表啟用 cin.tie(NULL)。
in-py3-input 使用 EOFError 來偵測 EOF，in-py3-input-no_try 則使用 for 跑 \(N\) 圈來取代 EOF 偵測。

輸出

程式行為

依序印出 \([0, 10^7)\)，每個數字單獨一行。

為避免磁碟存取速度的影響，輸出均導向到 /dev/null。

比較對象

C
- out-c
C++
- out-cpp
- out-cpp +NS
- out-cpp +NT
- out-cpp +NS +NT
- out-cpp +LF
- out-cpp +LF +NS
- out-cpp +LF +NT
- out-cpp +LF +NS +NT
Python
- out-py3-print
- out-py3-write

out-c 使用 printf，out-cpp 使用 cout 與 endl，out-py3-print 使用 print，out-py3-write 使用 sys.stdout.write。
+LF 代表用 '\n' 代替 endl，+NS 與 +NT 的意思與輸入時相同。

實驗結果

以下各項執行時間均為重複實驗 10 次後的平均值(單位：秒)。
C/C++ 程式編譯時均不開啟編譯優化。
數據僅供參考。

輸入

 0.983  in-cpp +NS +NT
 1.036  in-cpp +NS
 1.765  in-c
 3.743  in-cpp +NT
 3.818  in-cpp
 5.297  in-py3-readline
16.087  in-py3-input
16.552  in-py3-input-no_try

輸出

 0.629  out-cpp +LF +NS
 0.637  out-cpp +LF +NS +NT
 0.685  out-c
 0.765  out-cpp +LF
 0.774  out-cpp +LF +NT
 4.792  out-py3-write
 5.762  out-py3-print
 6.148  out-cpp +NS
 6.163  out-cpp +NS +NT
 6.292  out-cpp +NT
 6.327  out-cpp

結論

C++ 輸入

輸入資料量大時應使用 ios::sync_with_stdio(false)，能加速到只需 27% 時間。
cin.tie(NULL) 影響不大。

C++ 輸出

輸出資料量大時應使用 ios::sync_with_stdio(false) 並用 '\n' 代替 endl，能加速到只需 10% 時間。
cin.tie(NULL) 無影響 (因只有輸出沒有輸入，符合預期)。
使用 endl 甚至會導致 C++ 程式比 Python 還慢，非常誇張。

Python 輸入

sys.stdin.readline 比 input 快，只需 33% 時間。
in-py3-input-no_try 比 in-py3-input 還慢一些，跟我的預期不一致。

Python 輸出

sys.stdout.write 比 print 快，只需 83% 時間。

附件

附上實驗用的程式碼

in-c

#include <stdio.h>

int main() {
  int s = 0;
  for (int x; scanf("%d", &x) != EOF; ) {
    s ^= x;
  }
  printf("%d\n", s);
  return 0;
}

in-cpp

#include <iostream>
using namespace std;

int main() {
#ifdef NS
  ios::sync_with_stdio(false); // no sync
#endif
#ifdef NT
  cin.tie(NULL); // no tie
#endif
  int s = 0;
  for (int x; cin >> x; ) {
    s ^= x;
  }
  cout << s << endl;
  return 0;
}

in-py3-input

s = 0
while True:
  try:
    x = int(input())
  except EOFError:
    break
  s ^= x
print(s)

in-py3-input-no_try

s = 0
for i in range(10000000):
  x = int(input())
  s ^= x
print(s)

in-py3-readline

import sys

s = 0
while True:
  t = sys.stdin.readline()
  if t == '':
    break
  x = int(t)
  s ^= x
print(s)

out-c

#include <stdio.h>

int main() {
  for (int i = 0; i < 10000000; i++) {
    printf("%d\n", i);
  }
  return 0;
}

out-cpp

#include <iostream>
using namespace std;

int main() {
#ifdef NS
  ios::sync_with_stdio(false);
#endif
#ifdef NT
  cin.tie(NULL);
#endif
  for (int i = 0; i < 10000000; i++) {
#ifdef LF
    cout << i << '\n';
#else
    cout << i << endl;
#endif
  }
  return 0;
}

out-py3-print

for i in range(10000000):
  print(i)

out-py3-write

import sys

for i in range(10000000):
  sys.stdout.write(str(i) + '\n')

[C/C++] [Python]