[I/O 優化] C++ 篇

[I/O 優化] PYTHON 篇

在 $OJ$ 解題時，
常常遇到 $TLE(Time \ Limit \ Exceed)$ 的問題，
有些時候並不是因為方法錯誤，
而是在「輸入/輸出」花上太多的時間了，
以下介紹幾種基本的 $I/O$ 優化方法。


< $Method \ 1.$ >
在主程式裡面加上以下這兩行：

ios::sync_with_stdio(false);
cin.tie(nullptr);

基本上就是把原本預設與 $cstdio$ 的同步關掉，
還有解除 $cin$ 的綁定。
並且把原本的 $endl$ 換成 '\n' (換行字元)，
詳細的解釋可以參考 這篇。


< $Method \ 2.$ >
把原本的 $cin, \ cout$ 換成 $scanf(), \ printf()$，
根據在 $OJ$ 解題的經驗，
$scanf(), \ printf()$ 在測資檔小的時候，
會比 < $Method \ 1.$ > 快，
但是相對在寫程式時就比較不方便些，
格式也比較嚴謹，
撰寫相對麻煩，
斟酌使用。


< $Method \ 3.$ >
用字元讀取、字元輸出的方式，
用 $getchar(), \ putchar()$ 函式，
可以達到更好的執行效率。

程式碼如下：

template <typename T>
inline bool rit(T& re) {
    re = 0; bool neg = 0; char c = getchar();
    while (!isdigit(c)) {
        if (c == EOF) return 0;
        if (c == '-') neg = 1;
        c = getchar();
    }
    while (isdigit(c)) re = re * 10 + c - '0', c = getchar();
    re = (neg ? -re : re);
    return 1;
}

template <typename T>
inline void wit(T x) {
    if (x < 0) {
        putchar('-'); x = -x;
    }
    char tmp[20]; size_t len = 0;
    do tmp[len++] = x % 10 + 48; while (x /= 10);
    while (len) putchar(tmp[--len]);
    // putchar('\n');
}

要注意的是，
這邊只處理「整數」的部分
如果傳入的是浮點數、字串等，
可能會發生預期以外的錯誤。

另外還有 $getchar\_unlocked(), \ putchar\_unlocked()$ 兩個讀取字元的函式，
在部分系統和 $OJ$ 可能無法使用，斟酌使用。
用法和 $getchar(), \ putchar()$ 是一樣的，
但是速度可以差到非常多哦(約十幾倍 ~ 幾十倍)！

*最快的「讀入」函式  $fread()$
簡單來說，就是讀取檔案。
程式碼如下：

const size_t size = 200000; char buf[size], *p1 = buf, *p2 = buf;
inline char getc() {
 return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, size, stdin), p1 == p2) ? EOF : *p1++;
}

把原本的 $getchar()$ 改成 $getc()$ 就好了。
$fread()$ 有 $4$ 個參數，
第 $1$ 個是「讀入空間」，在上例中是字元陣列 $buf$ ，
第 $2$ 個是「讀入的單一元素記憶體大小」，在上例中是因為 $sizeof(char) = 1$，故直接用 $1$ 即可，
第 $3$ 個是「一次要讀入的數量」，在上例中以 $size$ 表示，
第 $4$ 個是「讀入的檔案名稱」，$OJ$ 基本上都是 $stdin$。
最後會回傳「讀取的數量」。

當然也有 $fwrite()$，但是很多 $OJ$ 都禁止使用 $fwrite()$，這邊就不多介紹了。


< $Method \ 4.$ >
$streambuf$，
用法與 < $Method \ 3.$ > 的概念類似，
只是用的方法不一樣。
程式碼如下：

template <typename T>
inline bool rit(T& re) {
    re = 0; bool neg = 0; char c = cin.rdbuf()->sbumpc();
    while (!isdigit(c)) {
        if (c == EOF) return 0;
        if (c == '-') neg = 1;
        c = cin.rdbuf()->sbumpc();
    }
    while (isdigit(c)) re = re * 10 + c - '0', c = cin.rdbuf()->sbumpc();
    re = neg ? -re : re;
    return 1;
}

template <typename T>
inline void wit(T x) {
    if (x < 0) {
        cout.rdbuf()->sputc('-');
        x = -x;
    }
    char tmp[20];
    size_t len = 0;
    do tmp[len++] = x % 10 + 48; while (x /= 10);
    while (len) cout.rdbuf()->sputc(tmp[--len]);
    // cout.rdbuf()->sputc('\n');
}

一樣，只處理「整數」部分，
但是 $streambuf$ 的方法要加上 < $Method \ 1.$ > 才會達到非常快哦！


總結：
以上幾個方法，

$I/O$ 優化後，
時間都差非常多，
但是仍然有些差距，
這幾個方法的速度排名大約如下：

1. $fread() + putchar\_unlocked()$
2. $streambuf$ 和 $getchar\_unlocked() + putchar\_unlocked()$
3. $scanf() + printf()$ 和 $ios::sync\_with\_stdio(false), \ cin.tie(nullptr);$

雖然在 $zerojudge$ 這個 $OJ$ 上，
很多題目就算演算法錯誤，
但加上了 $I/O$ 優化，
仍然可以 $AC$，
但不要一昧的學 $I/O$ 優化而不學習演算法，
這樣根本是本末倒置，
失去學習程式設計的意義了，
真的遇到有些題目卡 $I/O$ 優化時再使用就好了。

另外，可以再把以上 $I/O$ 優化的程式碼包裝，
程式碼如下：

struct _istream {
// #define getchar getc
    bool eof; char buf[200000], *p1 , *p2;
    inline operator bool() {
        return !eof;
    }
    inline char getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 200000, stdin), p1 == p2) ? EOF : *p1++;
    }
    template <typename T>
    inline _istream& operator>>(T& re) {
        re = 0; char c = getchar(); bool neg = 0;
        while (!isdigit(c)) {
            if (c == EOF) {
                eof = 1;
                return *this;
            }
            if (c == '-') neg = 1;
            c = getchar();
        }
        while (isdigit(c)) {
            re = re * 10 + c - '0';
            c = getchar();
        }
        re = (neg ? -re : re);
        return *this;
    }
    _istream(): eof(0) {
        p1 = p2 = buf;
    }
} rit;
 
struct _ostream {
// #define putchar putchar_unlocked
    inline _ostream& operator<<(const char c) {
        putchar(c); return *this;
    }
    inline _ostream& operator<<(const char* s) {
        while (*s != '\0') putchar(*s++);
        return *this;
    }
    inline _ostream& operator<<(const string s) {
        for (const auto& i : s)
            putchar(i);
        return *this;
    }
    template <typename T>
    inline _ostream& operator<<(T x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        char s[25];
        size_t len = 0;
        do s[len++] = x % 10 + 48; while (x /= 10);
        while (len) putchar(s[--len]);
        return *this;
    }
} wit;
#define cin rit
#define cout wit
#define endl '\n'
#define istream _istream
#define ostream _ostream

把這一串貼程式碼在最上面，等確定執行 $OK$ 之後，在把 $struct$ 裡面 // #$define$ 的斜線拿掉即可。
這樣可以支援基本的 $operator$，
使用時只要 $cin >> tmp, \ cout << tmp$ 就好，

相對用函式的方法方便。

一樣只適用於「整數」，
但也只支援基本的輸入、輸出的動作，
其他的成員函數是無法使用的。
以上，

若有更好的想法歡迎提出哦！