如何看待在 OI / ACM 賽事廣為使用的快速讀入整數？
在我看一些ACM訓練人員的代碼風格的一些總結，這對以後的職業發展好嗎？ - C / C++中該題主已經說了 OI / ACMer 對於 cin 完全無愛，即使是 C++ 也要使用 scanf 的行為，但尤其是在 OI 界，選手們經常使用一種快速讀入整數的方法（代碼如下，以 hzwer 版為例），其含義是逐位以字元的形式讀入並壓入整數中，這種方法比 scanf 都快，但是似乎會有莫名其妙的 bug，比如本人就有一道題寫快速讀入整數 WA，scanf 卻 AC 的情況。想問這種方法值得提倡嗎？
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch&<"0"||ch&>"9"){if(ch=="-")f=-1;ch=getchar();}
while(ch&>="0"ch&<="9"){x=x*10+ch-"0";ch=getchar();} return x*f; }--------------------------------------2016-8-4更新---------------------------------------------
應某些同學的要求，補上奇怪字元的判斷，更改處理負數的部分。
ACM題嘛……怎麼快怎麼寫。
看到前邊一幫人討論 「不能處理負數」，「不能x=GetInt()而要GetInt(x)」 我也是挺醉的。
人家只是以這段 「能通過這道題」 的代碼為例描述一種現象而已。其實我覺得演算法競賽的Coding和工程領域的Coding完全是兩個模式。
雖然我現在搞Engineering，在工程模式下自動切換成注重代碼風格和魯棒性模式。但作為一名ACM未退役選手，回去寫ACM題自動切換成快糙猛模式，怎麼方便怎麼寫。比如，從不用指針，有效率問題用引用，內存一律全局開好大數組——指針簡直降低編碼效率。比如，從不在變數前加const浪費coding時間，變數名能短則短（一律一個單詞以內），行能縮就縮（能一句話說清，能逗號絕不用大括弧）。比如，從不用class，用個struct就不錯了，類型強轉/變數重複利用是技巧的一部分，輸入當然寫到main()里，多寫個init()函數多浪費時間。——這沒什麼不好的。ACM選手就是能搞清自己在做什麼，而且選手之間也互相知道對方在幹什麼。總體來說，快糙猛在某些領域是很好的編程方式，玩的就是速度、大腦和心跳。當然。。。進了Engineering不能這麼干。。。這題寫了好久，複雜度都對，但是一直tle，好煩躁。
題解：用isap，dinic會超時。-「我qnmlgb。」這題寫了好久，複雜度都對，但是一直tle，好煩躁。
題解：用樹狀數組，線段樹會超時。-「我qnmlgb。」這題寫了好久，複雜度都對，但是一直tle，好煩躁。
題解：用劃分樹，主席樹會超時。-「我qnmlgb。」這題寫了好久，複雜度都對，但是一直tle，好煩躁。
題解：用快速讀入，scanf會超時。
-「我qnmlgb。」某日接到通知，出幾道xx聯合賽的題，要稍微有質量有難度的。
於是嘴角浮現出邪魅的笑。或曰：得饒人處且饒人。冤冤相報何時了？放下屠刀，立地成佛。
樓上的各位大俠，大概都是殺人的能手。諸位互相炫耀自己的屠人利器，怡然自得的樣子令我等弱雞不禁毛骨悚然。
原答案：n^3的演算法，就算把常數優化一個1/6，也a不了n^2*logn的題，除非出題人的數據出得很蠢。出題人可以把數據出得有多蠢呢？打個比方，去年長春站（霧這一行
F = F == 1 ? -1 : 1
有一種「我和我老婆意見一致就聽我的，否則聽我老婆的」的氣質
問題是 getchar還是不夠快！
以前刷 timus 時候的文件頭（針對 Windows OJ 環境），那時喜歡刷最小內存（基礎大小 4K左右），最快速度（答案排行榜上能排在第一個）：#pragma comment(linker, "/defaultlib:kernel32.lib")
#pragma comment(linker, "/OPT:NOWIN98")
#pragma comment(linker, "/SECTION:.text,REW")
#pragma comment(linker, "/merge:.data=.text")
#pragma comment(linker, "/merge:.rdata=.text")
#pragma comment(linker, "/ALIGN:0x200")
#pragma comment(linker, "/STACK:64")
#pragma comment(linker, "/nodefaultlib:libc.lib")
#pragma comment(linker, "/nodefaultlib:libcmt.lib")
#pragma comment(linker, "/ENTRY:main")
#pragma optimize("gsy", on)
#ifdef __cplusplus
#define EXTERN extern "C"
#else
#define EXTERN extern
#endif
EXTERN void* __stdcall GetStdHandle(unsigned long);
EXTERN void* __stdcall CreateFileA(const char*, unsigned, unsigned, void*, unsigned, unsigned, void*);
EXTERN int __stdcall ReadFile(void*, void*, unsigned long, unsigned long*, void*);
EXTERN int __stdcall WriteFile(void*, const void*, unsigned, unsigned *, void*);
int mwrite(void *handle, const void* caBuffer, unsigned int unToWrite)
{
if (WriteFile(handle, caBuffer, unToWrite, (unsigned*)unToWrite, 0) == 0) return -1;
return unToWrite;
}
int getcc(void *handle)
{
unsigned long len = 1;
int c = 0;
if (ReadFile(handle, c, len, len, 0) == 0) return -1;
if (len &< 1) return -1;
return c;
}
int getnum(void *handle)
{
int c = " ", n = 0, s = 1;
while ((c&<"0"||c&>"9") c&>0 c!="-" c!="+") c = getcc(handle);
if (c &< 0) return 0;
if (c == "-") { s = -1; c = getcc(handle); }
if (c == "+") c = getcc(handle);
for (; c &>= "0" c &<= "9"; ) {
n = n * 10 + c - "0";
c = getcc(handle);
}
return n * s;
}
char*putnum(char *str, unsigned n, int pp)
{
char c = "-", p = pp;
unsigned d;
for (d = 10000000; d &> 0; d /= 10) {
c = "0" + n / d;
n = n % d;
if (c == "0" !p d &> 1) continue;
p = " ";
*str++ = c;
}
return str;
}
使用的時候，先 GetStdHandle 返回一個 handler，然後 getnum 的時候傳遞進去，注意棧尺寸需要根據題目針對性修改。
不少題目測試數據量是很大的，解法相同的時候，這類代碼能讓你速度更快，內存更小（libc.lib都沒要）。。。張地主AKF：「你們啊，too naive！」
char B[1&<&<26],*S=B;int F(){for(;*S&<"-";S++);register int x=*S++-"0";for(;*S&>="0";x=(x&<&<3)+(x&<&<1)+*S++-"0");return x;}
或者下面這個帶符號的：char B[1&<&<26],*S=B;int F(){register int x,b;for(;*S&<"-";S++);for(*S!="-"?x=*S++-"0",b=1:(S++,x=b=0);*S&>="0";x=(x&<&<3)+(x&<&<1)+*S++-"0");return b?x:-x;}char U[1&<&<26],*O=U,stk[20];
#define PuT(b) register int i=0;for(;b;stk[++i]=x%10+"0",x/=10);for(;i;*O++=stk[i--]);void pri(register int x){if(!x)*O++="0";else{PuT(x)};}void pr9(register int x){PuT(i&<9);}#define MoD 1000000000#define pr(x,c) (x&<0?*O++="-",x=-x:1,x&>=MoD?pri(x/MoD),pr9(x%MoD):pri(x),*O++=c)最後在main裡面調用：
fread(B,1,1&<&<26,stdin); n=F(); ... pr(ans,""); fwrite(U,1,O-U,stdout);不要不服Noip2015D2T3的std用的就是這個成功卡進0.5s，原來時限是2s，於是就被改成了1s
一般情況下沒有必要用，感覺可能會被卡才用而且這麼寫簡直低效，杯水車薪
要這麼寫：
namespace IStream{
const int L=1&<&<15;
char buffer[L],*S,*T;
inline char Get_Char()
{
if(S==T)
{
T=(S=buffer)+fread(buffer,1,L,stdin);
if(S==T) return EOF;
}
return *S++;
}
inline int Get_Int()
{
char c;
int re=0;
for(c=Get_Char();c&<"0"||c&>"9";c=Get_Char());
while(c&>="0"c&<="9")
re=(re&<&<1)+(re&<&<3)+(c-"0"),c=Get_Char();
return re;
}
}
你們的回答好像都沒有 get 到重點
addEdge(GetInt(), GetInt(), GetInt());
然後輸入 1 2 3 發現調用的是 addEdge(3, 2, 1)
這個代碼非！常！危！險！
c 和 c++ 的語言標準都規定，參數的求值順序是不！確！定！的！也就是說，假設你的程序輸入 1 2 3，今天調用 addEdge(1, 2, 3)，明天調用 addEdge(2, 3, 1)，這樣一個編譯器是符合規範的。
實際使用中，一般是按照調用棧順序從右往左執行，所以會出現讀入反序的情況。
注意：我極其不推薦大家利用這個反序特性。從來沒有人規定編譯器必須反序。
所以要使用這段代碼必須
int x, y, z;
x = GetInt(); y = GetInt(); z = GetInt();addEdge(x, y, z);但是一個好用的代碼的 *設計理由* 不應該是背下來的，應該是真實的印在腦子裡的。我希望大家不要以被坑的方式記住這個設計理由。。
所以要問我支持不支持你這段代碼的話。。不支持。第一行就是錯的，應該改為
void GetInt(int * x);
內部也得改改，然後
int x, y, z;
GetInt(x); GetInt(y); GetInt(z);addEdge(x, y, z);想用引用也是可以的。
另外從快速讀入的角度來說，這段代碼手動解析一個整數，我非常不支持。如果卡讀入的話，我認為一般內存不會卡的太緊，至少把全輸入文件讀進來是可行的。
直接 fread 進來 strtol 不就完事了。這個快速讀入掛有點脆……
我們還是拿http://blog.csdn.net/shahdza/article/details/6317011 這個博客里的來討論吧。首先你得知道這個寫法的時間效率是從哪裡擠出來的。
Byvoid之前寫過探尋C++最快的讀取文件的方案，其中的結論是，取消同步的cin和scanf一樣快。其實現在更多人的嘗試結果是，取消同步的cin比scanf還要快出一點。為什麼？注意到scanf()的第一個參數，格式化字元串。這個參數不是編譯的時候解析的，而是運行的時候……讀取遍數少還沒感覺，當你邊數特別多的時候，這時間就多的起飛了……類似的（這裡是printf()）經典例子是http://acm.hdu.edu.cn/showproblem.php?pid=5718
出題人的本意是，卡掉O(nlogn)的直接排序，只讓O(n)的計數排序通過。（所以n這麼大）你知道這個題的時限為什麼是4秒嗎？因為第一個版本的標程運行時間長達2.5秒。（為了保證1001的送分本質，強制時限是2倍，4秒。）之後我發現，對一組數據，最壞情況下，標程使用了1000萬遍的printf()……不慢就怪了！然後我自己寫了一發，1000萬遍printf()變成，先在一個char[]數組裡準備好，然後一次printf()輸出。結果呢？550ms就跑完了！然後試著改成使用sort()，還是飛快啊！850ms啊！事實證明：
1、sort沒你想的那麼慢，以後想卡這個log的可以去歇歇了。2、解析O(n)遍格式化字元串的時間遠長於你的O(n)計算+O(n)輸出時間（4~5倍？）用讀入掛，你就沒有解析格式化字元串的時間代價了，多好（時間省下來了，姿勢丑點能過了o yeah！）但是為什麼會WA呢？1、沒仔細讀題，可能輸入負數，你的讀入掛不認識負號，可能超過int，你的讀入掛又不支持。方案：換一個正確的實現。2、輸入格式不嚴謹。不要笑，輸入格式不嚴謹/不按照自己輸入描述來的題真是多的滿天飛……今年百度之星就來了個，平時練習賽更是常客……你還得和標程用一樣的輸入方法才能過……（更常見的，scanf("%s")與gets()的A能過，B不行的尷尬/scanf("%s")來讀一個char的無奈……）辦法：這有什麼辦法？確定演算法正確以後，多換幾種輸入方式，找一個能過的……過了以後，對這個出題人，隨你吐槽。本人是一名OIer。CCF的正式OI比賽儘管有的題輸入輸出規模大，但不卡輸入輸出的。比如NOIP2016的D1T2，輸入規模達百萬級別，本人考場上寫scanf和printf也沒啥壓力地過掉了。所以正式比賽，會做的題沒有用輸入優化的必要。不過，一些非正式的比賽（比如某些垃圾省選）可能會卡輸入輸出，可能用Windows測導致輸入輸出特別慢，甚至可能標程開了輸入優化才卡過去（有一種婊出題人的衝動）。另外如果你只會複雜度不對（比如多一個log）的做法，然後在TLE的邊緣，那麼為了保險起見還是寫輸入輸出優化吧。
人家問怎麼看待輸入外掛，一群人跑來說人家外掛不行也是醉了。
拋結論:工程學上這種東西意義不大。演算法競賽里比的是演算法，如果需要輸入外掛才能ac，證明題目有問題。然而沒辦法，比賽比的就是ac題數。C/C++的輸入輸出外掛看過很多，其實java也是有輸入輸出外掛的。14年的網賽好像就是有道題當時用java寫的，然後加了外掛過得。。。
然後有這幾種寫法：Aimport java.io.*;
import java.util.*;
import java.math.*;
public class Main {
static BigInteger EIGHT = new BigInteger("8");
static BigInteger SEVEN = new BigInteger("7");
static BigInteger ONE = new BigInteger("1");
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner cin = new Scanner(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int t = 0, tt = 0;
t = cin.nextInt();
while (t-- != 0)
{
BigInteger n = cin.nextBigInteger();
BigInteger tmp = n.multiply(EIGHT).subtract(SEVEN);
BigInteger res = n.multiply(tmp).add(ONE);
out.println("Case #" + (++tt) + ": " + res);
}
out.close();
}
}
恩，其實就是用PrintWriter...
B/*
ID: your_id_here
LANG: JAVA
TASK: test
*/
import java.io.*;
import java.util.*;
class test {
public static void main (String [] args) throws IOException {
// Use BufferedReader rather than RandomAccessFile; it"s much faster
BufferedReader f = new BufferedReader(new FileReader("test.in"));
// input file name goes above
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("test.out")));
// Use StringTokenizer vs. readLine/split -- lots faster
StringTokenizer st = new StringTokenizer(f.readLine());
// Get line, break into tokens
int i1 = Integer.parseInt(st.nextToken()); // first integer
int i2 = Integer.parseInt(st.nextToken()); // second integer
out.println(i1+i2); // output result
out.close(); // close the output file
System.exit(0); // don"t omit this!
}
}
這個是USACO給的，簡單地說(chao)：
Important: BufferedReader and StringTokenizer are far more efficient than many other schemes for reading input. They can make a huge difference in the efficiency of your program! Use them!Cpublic class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
InputReader cin = new InputReader(System.in);
PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
cout.flush();
}
private static class InputReader {
public BufferedReader rea;
public StringTokenizer tok;
public InputReader(InputStream stream) {
rea = new BufferedReader(new InputStreamReader(stream), 32768);
tok = null;
}
public String next() {
while (tok == null || !tok.hasMoreTokens()) {
try {
tok = new StringTokenizer(rea.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tok.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}
這個就是，輸出的時候用PrintWriter，然後用BufferReader和StringTokenizer寫了一個InputReader...
你這個快速讀入寫得有問題啊。
問題描述里的代碼int GetInt() {
int x = 0, F = 1; char C = getchar();
while (C &<= "0" || C &>= "9") { if (C == "-") F = -F; C = getchar(); }
while (C &>= "0" C &<= "9") { x = x * 10 - "0" + C, C = getchar(); }
return x * F;
}
不是卡的太厲害的話可以setvbuf
最快的讀入優化不是fread
是mmap
發一個我自己用的 scan()
template&
T _scan() {
T ch; bool seg = false;
while (!isdigit(ch = getchar())) {
if (ch == -1) {
eof = true;
return 0;
}
seg |= (ch == "-");
}
T x = ch - "0";
while (isdigit(ch = getchar())) {
x = x * 10 + ch - "0";
}
if (seg) {
x = -x;
}
return x;
}
auto const scan = _scan& 可以讀入整數，會忽略讀入前的非數字字元，並吃掉數字後的一個字元。如果不需要判定 eof 可以把上面 eof 相關的代碼刪掉。從沒遇到過因為這個scan導致WA的情況（前提是你清楚這個scan的行為）
auto const scan_ll = _scan&
大多數卡讀入的題，毫無意義。
WA的原因一般是因為數據比較特別 getint() 不夠完善但是在演算法比賽中這種讀入方式確實非常有優勢 有時候能生生的讓一個低效演算法AC我聽過很多noi選手(不下5個 但也不少了)推薦這種讀入方式 所以為了防止WA最好根據輸入數據進行適當更改
如何看待在OI/ACM賽事不常使用的快速輸出整數？
用scanf不用cin
主要的原因是scanf比cin快很多以及scanf控制讀入格式的能力比cin強至於GetInt什麼的我是從來沒用過因為只要出題的人腦子每毛病那麼把演算法速度提上去的效果肯定比這個明顯快速讀入是靠自己理解的而不是死記硬背的。wa了只能怪自己學藝不精咯。
一直覺得這種讀入掛沒什麼意義，比正常讀快不了多少，真的遇到大量輸入scanf不行的話，只能fread了。
已知缺點：1、如果文件提前結束，程序會死循環2、你這個版本又不支持前面有奇怪字元，又不能處理負數，一點也不好用！
貼上我用的...
int Int()
{
char c;
bool neg=false;
while((c=getchar())&<"0"||c&>"9")neg=c=="-";
int a=c-"0";
while((c=getchar())&>="0"c&<="9")a=a*10+c-"0";
return neg?-a:a;
}
推薦閱讀：
※如何在完全不會使用CFD軟體的情況下裝作很了解CFD的樣子？
※微軟為什麼可以這麼蠢？
※大部分重點大學計算機專業學生上大學前對計算機了解多少？
※軟體工程專業讀研985名校所和直接就業，哪個好，怎麼選擇？
※設計、更新一門通用編程語言的一般流程是怎樣的？