跳转至

讀入、輸出優化

在默認情況下，std::cin/std::cout 是極為遲緩的讀入/輸出方式，而 scanf/printf 比 std::cin/std::cout 快得多。

注意

cin/cout 與 scanf/printf 的實際速度差會隨編譯器和操作系統的不同發生一定的改變。如果想要進行詳細對比，請以實際測試結果為準。

下文將詳細介紹讀入輸出的優化方法。

關閉同步/解除綁定

std::ios::sync_with_stdio(false)

這個函數是一個「是否兼容 stdio」的開關，C++ 為了兼容 C，保證程序在使用了 printf 和 std::cout 的時候不發生混亂，將輸出流綁到了一起。同步的輸出流是線程安全的。

這其實是 C++ 為了兼容而採取的保守措施，也是使 cin/cout 速度較慢的主要原因。我們可以在進行 IO 操作之前將 stdio 解除綁定，但是在這樣做之後要注意不能同時使用 std::cin 和 scanf，也不能同時使用 std::cout 和 printf，但是可以同時使用 std::cin 和 printf，也可以同時使用 scanf 和 std::cout。

tie

tie 是將兩個 stream 綁定的函數，空參數的話返回當前的輸出流指針。

在默認的情況下 std::cin 綁定的是 std::cout，每次執行 << 操作符的時候都要調用 flush() 來清理 stream buffer，這樣會增加 IO 負擔。可以通過 std::cin.tie(0)（0 表示 NULL）來解除 std::cin 與 std::cout 的綁定，進一步加快執行效率。

但需要注意的是，在解除了 std::cin 和 std::cout 的綁定後，程序中必須手動 flush 才能確保每次 std::cout 展現的內容可以在 std::cin 前出現。這是因為 std::cout 被 buffer 為默認設置。例如：

1
2
3
4
5
6
std::cout
    << "Please input your name: "
    << std::flush;  // 或者: std::endl;
                    // 因為每次調用std::endl都會flush輸出緩衝區，而 \n 則不會。
// 但請謹慎使用，過多的flush會影響程序效率
std::cin >> name;

代碼實現

1
2
3
std::ios::sync_with_stdio(false);
std::cin.tie(0);
// 如果編譯開啓了 C++11 或更高版本，建議使用 std::cin.tie(nullptr);

讀入優化

scanf 和 printf 依然有優化的空間，這就是本章所介紹的內容——讀入和輸出優化。

  • 注意，本頁面中介紹的讀入和輸出優化均針對整型數據，若要支持其他類型的數據（如浮點數），可自行按照本頁面介紹的優化原理來編寫代碼。

原理

眾所周知，getchar 是用來讀入 1 byte 的數據並將其轉換為 char 類型的函數，且速度很快，故可以用「讀入字符——轉換為整型」來代替緩慢的讀入

每個整數由兩部分組成——符號和數字

整數的 '+' 通常是省略的，且不會對後面數字所代表的值產生影響，而 '-' 不可省略，因此要進行判定

10 進制整數中是不含空格或除 0~9 和正負號外的其他字符的，因此在讀入不應存在於整數中的字符（通常為空格）時，就可以判定已經讀入結束

C 和 C++ 語言分別在 ctype.h 和 cctype 頭文件中，提供了函數 isdigit, 這個函數會檢查傳入的參數是否為十進制數字字符，是則返回 true，否則返回 false。對應的，在下面的代碼中，可以使用 isdigit(ch) 代替 ch >= '0' && ch <= '9'，也可以使用 !isdigit(ch) 代替 ch <'0' || ch> '9'

代碼實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {  // ch 不是數字時
    if (ch == '-') w = -1;        // 判斷是否為負
    ch = getchar();               // 繼續讀入
  }
  while (ch >= '0' && ch <= '9') {  // ch 是數字時
    x = x * 10 + (ch - '0');  // 將新讀入的數字「加」在 x 的後面
    // x 是 int 類型，char 類型的 ch 和 '0' 會被自動轉為其對應的
    // ASCII 碼，相當於將 ch 轉化為對應數字
    // 此處也可以使用 (x<<3)+(x<<1) 的寫法來代替 x*10
    ch = getchar();  // 繼續讀入
  }
  return x * w;  // 數字 * 正負號 = 實際數值
}
  • 舉例

讀入 num 可寫為 num=read();

輸出優化

原理

同樣是眾所周知，putchar 是用來輸出單個字符的函數

因此將數字的每一位轉化為字符輸出以加速

要注意的是，負號要單獨判斷輸出，並且每次 %（mod）取出的是數字末位，因此要倒序輸出

代碼實現

1
2
3
4
5
6
7
8
void write(int x) {
  if (x < 0) {  // 判負 + 輸出負號 + 變原數為正數
    x = -x;
    putchar('-');
  }
  if (x > 9) write(x / 10);  // 遞歸，將除最後一位外的其他部分放到遞歸中輸出
  putchar(x % 10 + '0');  // 已經輸出（遞歸）完 x 末位前的所有數字，輸出末位
}

但是遞歸實現常數是較大的，我們可以寫一個棧來實現這個過程

1
2
3
4
5
6
7
8
void write(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + 48);  // 48 是 '0'
}
  • 舉例

輸出 num 可寫為 write(num);

更快的讀入/輸出優化

通過 fread 或者 mmap 可以實現更快的讀入。

fread 能將需要的文件部分讀入內存緩衝區。mmap 則會調度內核級函數，將文件一次性地映射到內存中，類似於可以指針引用的內存區域。所以在日常程序讀寫時，只需要重複讀取部分文件可以使用 fread，因為如果用 mmap 反覆讀取一小塊文件，做一次性內存映射並且內核處理 page fault 的花費會遠比使用 fread 的內核級函數調度大。

一次性讀入緩衝區的操作比逐個字符讀入（getchar,putchar）要快的多。因為硬盤的多次讀寫速度是要慢於直接讀取內存的，所以先一次性讀到緩存區裏再從緩存區讀入要快的多。並且 mmap 確保了進程間自動共享，存儲區如果可以也會與內核緩存分享信息，確保了更少的拷貝操作。

更通用的是 fread，因為 mmap 不能在 Windows 環境下使用（例如 CodeForces 的 tester）。

fread 類似於參數為 "%s" 的 scanf，不過它更為快速，而且可以一次性讀入若干個字符（包括空格換行等製表符），如果緩存區足夠大，甚至可以一次性讀入整個文件。

對於輸出，我們還有對應的 fwrite 函數

1
2
3
4
std::size_t fread(void* buffer, std::size_t size, std::size_t count,
                  std::FILE* stream);
std::size_t fwrite(const void* buffer, std::size_t size, std::size_t count,
                   std::FILE* stream);

使用示例：fread(Buf, 1, SIZE, stdin)，表示從 stdin 文件流中讀入 SIZE 個大小為 1 byte 的數據塊到 Buf 中。

讀入之後的使用就跟普通的讀入優化相似了，只需要重定義一下 getchar。它原來是從文件中讀入一個 char，現在變成從 Buf 中讀入一個 char，也就是頭指針向後移動一位。

1
2
3
4
5
char buf[1 << 20], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)

fwrite 也是類似的，先放入一個 OutBuf[MAXSIZE] 中，最後通過 fwrite 一次性將 OutBuf 輸出。

參考代碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)

int rd() {
  int x = 0, f = 1;
  char c = gc();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = gc();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
  return x * f;
}

char pbuf[1 << 20], *pp = pbuf;

void push(const char &c) {
  if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
  *pp++ = c;
}

void write(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) push(sta[--top] + '0');
}
}  // namespace IO

輸入輸出的緩衝

printf 和 scanf 是有緩衝區的。這也就是為什麼，如果輸入函數緊跟在輸出函數之後/輸出函數緊跟在輸入函數之後可能導致錯誤。

刷新緩衝區

  1. 程序結束
  2. 關閉文件
  3. printf 輸出 \r 或者 \n 到終端的時候（注：如果是輸出到文件，則不會刷新緩衝區）
  4. 手動 fflush()
  5. 緩衝區滿自動刷新
  6. cout 輸出 endl

使輸入輸出優化更為通用

如果你的程序使用多個類型的變量，那麼可能需要寫多個輸入輸出優化的函數。下面給出的代碼使用 C++ 中的 template 實現了對於所有整數類型的輸入輸出優化。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 聲明 template 類,要求提供輸入的類型T,並以此類型定義內聯函數 read()
template <typename T>
T read() {
  T sum = 0, fl = 1;  // 將 sum,fl 和 ch 以輸入的類型定義
  int ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fl = -1;
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
  return sum * fl;
}

如果要分別輸入 int 類型的變量 a，long long 類型的變量 b 和 __int128 類型的變量 c，那麼可以寫成

1
2
3
a = read<int>();
b = read<long long>();
c = read<__int128>();

完整帶調試版

關閉調試開關時使用 fread(),fwrite()，退出時自動析構執行 fwrite()。

開啓調試開關時使用 getchar(),putchar()，便於調試。

若要開啓文件讀寫時，請在所有讀寫之前加入 freopen()。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// #define DEBUG 1  // 調試開關
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
  IO() : p1(buf), p2(buf), pp(pbuf) {}

  ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
  char gc() {
#if DEBUG  // 調試，可顯示字符
    return getchar();
#endif
    if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
    return p1 == p2 ? ' ' : *p1++;
  }

  bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  }

  template <class T>
  void read(T &x) {
    double tmp = 1;
    bool sign = 0;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
      if (ch == '-') sign = 1;
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
    if (ch == '.')
      for (ch = gc(); isdigit(ch); ch = gc())
        tmp /= 10.0, x += tmp * (ch - '0');
    if (sign) x = -x;
  }

  void read(char *s) {
    char ch = gc();
    for (; blank(ch); ch = gc())
      ;
    for (; !blank(ch); ch = gc()) *s++ = ch;
    *s = 0;
  }

  void read(char &c) {
    for (c = gc(); blank(c); c = gc())
      ;
  }

  void push(const char &c) {
#if DEBUG  // 調試，可顯示字符
    putchar(c);
#else
    if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
#endif
  }

  template <class T>
  void write(T x) {
    if (x < 0) x = -x, push('-');  // 負數輸出
    static T sta[35];
    T top = 0;
    do {
      sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) push(sta[--top] + '0');
  }

  template <class T>
  void write(T x, char lastChar) {
    write(x), push(lastChar);
  }
} io;

參考

http://www.hankcs.com/program/cpp/cin-tie-with-sync_with_stdio-acceleration-input-and-output.html

http://meme.biology.tohoku.ac.jp/students/iwasaki/cxx/speed.html

https://marc.info/？l=linux-kernel&m=95496636207616&w=2

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Marcythm, YZircon, Chaigidel, Tiger3018, voidge, H-J-Granger, ouuan, Enter-tainer, lcfsih, Xeonacid, Ir1d
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用