在一些算法題目中中,有的程式會被卡常數,就是說,程式雖然時間複雜度可以接受,但因為算法本身的時間常數過大,導緻程式在一些算法競賽中逾時。這是,快讀就顯得尤為重要了。
當然,如果程式算法本身就不高效,快讀就更加重要了,可以讓一些暴力程式獲得更多的測試點分數,如果資料不大甚至能AC,此時快讀就是“得分法寶”.
在預設情況下, std::cin/std::cout 是極為遲緩的讀入/輸出方式,而 scanf/printf 比 std::cin/std::cout 快得多。
可是為什麼會這樣呢?有沒有什麼辦法解決讀入輸出緩慢的問題呢?
關閉同步/解除綁定
這個函數是一個“是否相容 stdio”的開關,C++ 為了相容 C,保證程式在使用了 printf 和 std::cout 的時候不發生混亂,将輸出流綁到了一起。
這其實是 C++ 為了相容而采取的保守措施。我們可以在進行 IO 操作之前将 stdio 解除綁定,但是在這樣做之後要注意不能同時使用 std::cin/std::cout 和 scanf/printf 。
tie
tie 是将兩個 stream 綁定的函數,空參數的話傳回目前的輸出流指針。
在預設的情況下 std::cin 綁定的是 std::cout ,每次執行 << 操作符的時候都要調用 flush() ,這樣會增加 IO 負擔。可以通過 std::cin.tie(0) (0 表示 NULL)來解除 std::cin 與 std::cout 的綁定,進一步加快執行效率。
代碼實作
#include<iostream>
#include<algorithm>
using namespace std;
int x[1000005];
int main()
{
//關閉同步流
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//
int t;
cin >> t;
while( t-- ){
int n;
cin >> n;
for( int i = 0 ; i < n ; i++ ) cin >> x[i];
sort( x , x + n );
for( int i = 0 ; i < n ; i++ ){
if( i == n - 1 ) cout << x[i] << endl;
else cout << x[i] << " ";
}
}
}
如果編譯開啟了 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’
代碼實作
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)取出的是數字末位,是以要倒序輸出
代碼實作
void write(int x) {
if (x < 0) { // 判負 + 輸出負号 + 變原數為正數
x = -x;
putchar('-');
}
if (x > 9) write(x / 10); // 遞歸,将除最後一位外的其他部分放到遞歸中輸出
putchar(x % 10 + '0'); // 已經輸出(遞歸)完 x 末位前的所有數字,輸出末位
}
但是遞歸實作常數是較大的,我們可以寫一個棧來實作這個過程
inline 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 可以實作更快的讀入。其本質為一次性将輸入檔案讀入一個巨大的緩存區,如此比逐個字元讀入要快的多 ( getchar , putchar )。因為硬碟的多次讀寫速度是要慢于記憶體的,是以先一次性讀到緩存區裡再從緩存區讀入要快的多。
更通用的是 fread ,因為 mmap 不能在 Windows 環境下使用。
fread 類似于參數為 “%s” 的 scanf ,不過它更為快速,而且可以一次性讀入若幹個字元(包括空格換行等制表符),如果緩存區足夠大,甚至可以一次性讀入整個檔案。
對于輸出,我們還有對應的 fwrite 函數
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,也就是頭指針向後移動一位。
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 輸出。
參考代碼:
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++)
inline 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;
inline void push(const char &c) {
if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
*pp++ = c;
}
inline 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 是有緩沖區的。這也就是為什麼,如果輸入函數緊跟在輸出函數之後/輸出函數緊跟在輸入函數之後可能導緻錯誤。
重新整理緩沖區
- 程式結束
- 關閉檔案
- printf 輸出 \r 或者 \n 到終端的時候(注:如果是輸出到檔案,則不會重新整理緩沖區)
- 手動 fflush()
- 緩沖區滿自動重新整理
- cout 輸出 endl
使輸入輸出優化更為通用
如果你的程式使用多個類型的變量,那麼可能需要寫多個輸入輸出優化的函數。下面給出的代碼使用 C++ 中的 template 實作了對于所有整數類型的輸入輸出優化。
template <typename T>
inline T
read() { // 聲明 template 類,要求提供輸入的類型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,那麼可以寫成
a = read<int>();
b = read<long long>();
c = read<__int128>();
完整帶調試版
關閉調試開關時使用 fread() , fwrite() ,退出時自動析構執行 fwrite() 。
開啟調試開關時使用 getchar() , putchar() ,便于調試。
若要開啟檔案讀寫時,請在所有讀寫之前加入 freopen() 。
// #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
inline char gc() {
#if DEBUG // 調試,可顯示字元
return getchar();
#endif
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
return p1 == p2 ? ' ' : *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
template <class T>
inline void read(T &x) {
register double tmp = 1;
register bool sign = 0;
x = 0;
register 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;
}
inline void read(char *s) {
register char ch = gc();
for (; blank(ch); ch = gc())
;
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
}
inline void read(char &c) {
for (c = gc(); blank(c); c = gc())
;
}
inline 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>
inline 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>
inline void write(T x, char lastChar) {
write(x), push(lastChar);
}
} io;
舉例:
#include <cstdio>
#include <ctime>
#include <iostream>
#define LOOP 2 //循環次數
#define DATA 100000 //資料規模
struct dat{
int i,s,c;dat(int a=0,int b=0,int k=0){i=a,s=b,c=k;}
}dats[100+1];
inline int Readi(){//快讀
int x;
int fh=1;
char a=getchar();
while('0'>a || '9'<a){//首先過濾掉非數字字元(注意符号的處理)
if(a=='-') fh=-1;
a=getchar();
}
while('0'<=a && a<='9'){//小技巧:x=x*10 可以進位
x=x*10+a-'0';
a=getchar();
}
return x*fh;
}
void TryPrint(){
FILE* fp=fopen("in.txt","w");//輸出資料
for(int i=1;i<=DATA;++i)fprintf(fp,"%d ",i);
fclose(fp);//關閉檔案
//一定要注意,不關閉檔案,資料會寫到緩沖區裡,可能會丢資料)
}
void TryReadi(){
int t;for(int i=1;i<=DATA;++i)t=Readi();
}
void TryReads(){
int t;for(int i=1;i<=DATA;++i)scanf("%d",&t);
}
void TryReadc(){
int t;for(int i=1;i<=DATA;++i)std::cin>>t;
}
int main(){
freopen("out.txt","a",stdout);
printf("資料規模:%d 循環次數:%d 機關:msn",DATA,LOOP);
freopen("in.txt","r",stdin);//讀入資料檔案(隻讀)
for(int k=1;k<=LOOP;++k){
freopen("out.txt","a",stdout);
freopen("in.txt","r",stdin);//讀入資料檔案(隻讀)
TryPrint();clock_t p=clock();
TryReadi();clock_t i=clock();
TryReads();clock_t s=clock();
printf("快讀:%un",i-p);
printf("scanf輸入:%un",s-i);
dats[k]=dat(i-p,s-i,0);
}
double sum=0.0;for(int k=1;k<=LOOP;++k)sum+=dats[k].i;printf("快讀平均:%.0fn",sum/LOOP);
sum=0.0;for(int k=1;k<=LOOP;++k)sum+=dats[k].s;printf("scanf平均:%.0f",sum/LOOP);
return 0;
}
測試結果
資料規模:1000000 循環次數:5 機關:ms
快讀:50
scanf輸入:1113
快讀:50
scanf輸入:1130
快讀:58
scanf輸入:1116
快讀:52
scanf輸入:1168
快讀:51
scanf輸入:1130
快讀平均:52
scanf平均:1131
由此得,快讀比scanf快了很多。是以大家在讀入較大資料規模時,應嘗試快讀。
參考:https://article.itxueyuan.com/rdyEdp
https://oi-wiki.org/contest/io/入門ACM的極簡教程而且很有深度,個人覺得很好