### dario-dsa's blog

By dario-dsa, 7 years ago, ,

Can someone give me the code for fast IO in c++? Thanks very much.

• -14

 » 7 years ago, # |   0
•  » » 7 years ago, # ^ |   0 faster then that
•  » » » 7 years ago, # ^ |   +12 Maybe faster than velocity of light?
•  » » » » 4 years ago, # ^ |   +6 Isn't it speed of light?
 » 7 years ago, # |   +2 reads integers fast long long int read_int(){ char r; bool start=false,neg=false; long long int ret=0; while(true){ r=getchar(); if((r-'0'<0 || r-'0'>9) && r!='-' && !start){ continue; } if((r-'0'<0 || r-'0'>9) && r!='-' && start){ break; } if(start)ret*=10; start=true; if(r=='-')neg=true; else ret+=r-'0'; } if(!neg) return ret; else return -ret; } 
•  » » 7 years ago, # ^ |   +7 I've compared reading 10^7 integers ([-10^9; 10^9]) in your way and scanf. Your: 2.45s. Scanf: 1.98s. This works a bit faster than scanf: int readInt () { bool minus = false; int result = 0; char ch; ch = getchar(); while (true) { if (ch == '-') break; if (ch >= '0' && ch <= '9') break; ch = getchar(); } if (ch == '-') minus = true; else result = ch-'0'; while (true) { ch = getchar(); if (ch < '0' || ch > '9') break; result = result*10 + (ch - '0'); } if (minus) return -result; else return result; } 
•  » » » 4 years ago, # ^ |   0 Its really faster than scanf, Thanks a lot.I was able to solve the problem which has not previously held a scanf
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 That is maybe because he was reading long long integers,it probably would have been faster if function was of int type.Btw your code helped me on one task on SPOJ so thank you!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -8 After reading your comment i wonder why dario-dsa got so many down-votes even though the question is totally right (like, everybody could understand what he was asking), is it because he is cyan ?, please, don't tell me that's the reason, because i saw the first guy proVIDec be like : (Oh, a "new bie", better troll him a little bit)btw, i know this post is 3-years old
•  » » » » 3 years ago, # ^ |   +14 is it because he is cyan ? No, he surely wasn't cyan 3 years ago.
•  » » » 5 days ago, # ^ |   -10 how to use this method?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Using buffered io very fast: char in[1<<21]; // sizeof in varied in problem char const*o; void init_in() { o = in; in[ fread(in,1,sizeof(in)-4,stdin)]=0;//set 0 at the end of buffer. } int readInt(){ unsigned u = 0, s = 0; while(*o && *o <= 32)++o; //skip whitespaces... if (*o == '-')s = ~s, ++o; else if (*o == '+')++o; // skip sign while(*o>='0' && *o<='9')u = (u<<3) + (u << 1) + (*o++ - '0'); // u * 10 = u * 8 + u * 2 :) return static_cast( (u^s) + !!s) ; } 
 » 7 years ago, # |   +15 Go to Codechef. Find a problem with a huge amount of input. Look at the fastest submit. Profit.
 » 7 years ago, # |   -6 You can use fast cin/cout by writing "ios::sync_with_stdio(false);" on the top of your programm!
 » 7 years ago, # | ← Rev. 2 →   0 another approach is to read and store the entire input in a buffer before you begin processing it. Fastest functions are fread and fwrite (they are technically C functions, but should work fine in C++).
 » 7 years ago, # |   -9 Это не в тему блога, но мне нужна помощь) гляньте пож. Привет. http://codeforces.ru/blog/entry/8082
 » 7 years ago, # | ← Rev. 2 →   +8 I did some benchmarks couple of days ago while trying to find the fastest method for reading integers from stdin. I used input that had 200000 lines and two integers on each line. The results were like this (MinGW 4.8, Intel 3770K): cin with operator>> : 540ms cin with operator>> (with sync_with_stdio(false)): 100ms scanf (two ints at a time): 330ms reading each line to buffer with fgets and then parsing ints with atoi: 110ms same as above but using hand written version atoi: 50ms hand written int parser that uses getchar() to directly read the input: 170ms reading entire input to char array with fread and using my own int parser: 30ms reading blocks of 1kB to char array with fread and using my own int parser: 30ms So it's important to minimize the number of calls to standard library functions. The only type of IO that standard library does fast is transferring large chunks of data. I ended up with the last option because it's almost as fast as buffering the entire input but uses much less memory. Here's the code (it has some flaws but for contests it's good enough): static char stdinBuffer[1024]; static char* stdinDataEnd = stdinBuffer + sizeof (stdinBuffer); static const char* stdinPos = stdinDataEnd; void readAhead(size_t amount) { size_t remaining = stdinDataEnd - stdinPos; if (remaining < amount) { memmove(stdinBuffer, stdinPos, remaining); size_t sz = fread(stdinBuffer + remaining, 1, sizeof (stdinBuffer) - remaining, stdin); stdinPos = stdinBuffer; stdinDataEnd = stdinBuffer + remaining + sz; if (stdinDataEnd != stdinBuffer + sizeof (stdinBuffer)) *stdinDataEnd = 0; } } int readInt() { readAhead(16); int x = 0; bool neg = false; if (*stdinPos == '-') { ++stdinPos; neg = true; } while (*stdinPos >= '0' && *stdinPos <= '9') { x *= 10; x += *stdinPos - '0'; ++stdinPos; } return neg ? -x : x; } edit: this version requires manually skipping whitespace (stdinPos++), but it could easily be added to the function itself.
•  » » 7 years ago, # ^ |   0 You might also be interested in this article I wrote a while ago; I performed some similar I/O benchmarks: http://codeforces.com/blog/entry/5217
•  » » 4 years ago, # ^ |   +3 Interesting results! A minor detail: readInt has a bug. It will not work with the min value of int, e.g. –2,147,483,648 for 4-byte ints. Since 2,147,483,647 is the maxvalue of int, x will be 2,147,483,640 + 8, which is not 2,147,483,648 (since that cannot be represented in an int) and thus -x will not become -2,147,483,648 in the result. If you instead use x -= *stdinPos — '0'; and return neg ? x : -x; it should work.
•  » » » 3 years ago, # ^ |   0 It is actually correct. 2,147,483,640 + 8 overflows and becomes -2,147,483,648. When this is multiplied by -1 it becomes -2,147,483,648 again.
•  » » » » 3 years ago, # ^ |   +8 2,147,483,640 + 8 overflows and becomes -2,147,483,648. It doesn't
•  » » » » » 3 years ago, # ^ |   0 On most machines it works just fine. I have used mod 2^32 overflow in many competitions and it hasn't failed me once.
•  » » » » » » 3 years ago, # ^ |   +8 On most machines it works just fine. It doesn't depend on the machine, it depends on compiler, your code and memory layout, moon phase etc. I have used mod 2^32 overflow in many competitions and it hasn't failed me once. You got lucky. You can search Codeforces for 'undefined behavior', 'integer overflow' etc. (But then again, the chances of getting both bad optimization and MIN_INT edge case are minuscule.)
•  » » » » » » » 3 years ago, # ^ |   -12 I often, practically always implement, for example, the Rabin-Karp algorithm (and other rolling hash algorithms) using modulo 2^64 and long longs (even on 32-bit machines!). I simply let all the multiplications / additions overflow....Never had a single issue.Lucky? I don't think so.
•  » » » » » » » » 3 years ago, # ^ |   +5 Well, you may suppose that this will always work, but I suggest you to meditate on this code and its output a bit: http://ideone.com/JEITIH
•  » » » » » » » » » 3 years ago, # ^ |   -25 What does that have to do with anything? This is clearly a compiler bug.
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   -15 I know, I know, undefined behavior, this program could set the computer on fire and that would be just fine according to the C++ standard.However, on MOST architectures, multiplying/adding two numbers about which the compiler cannot know anything (they have something to do with user input, for example), works just fine almost always, because the compiler doesn't bother "optimizing" it.In this case, you're multiplying numbers about which the compiler knows about and it's a lot easier for the compiler to detect undefined behavior and go haywire (for example, by setting the computer on fire like in your example)
 » 3 years ago, # | ← Rev. 4 →   0 Slightly irrelevant, but since the topic was brought up: I've never seen contests that give contestant choice to perform IO using either: formatted input/output (human readable, slower for integer IO, most contests use this) binary input/output (less readabale, faster for reading huge arrays of integers, I've seen this only once or twice in OpenCup). Of course, this "ability to choose" has cons: is harder to maintain (e.g. in CodeForces you use only stdin/stdout, what do you use as 3rd/4th stream?) could provoke "silly" mistakes (forgeting to switch between formatted <--> binary) in participants code what do you do in interactive problems (most likely, this isn't a problem, because interaction is blocking anyway...) Could this idea be used (at least) for problems that have big input/output files? By that, I mean — in the description of a task don't add comment that goes like this:"oh yeah, input's huge, don't use slow IO, like C++ cin/cout, use printf/scanf",but provide an option to read from "input.txt" or "binary.in", and write to "output.txt" or "binary.out".
 » 3 years ago, # | ← Rev. 2 →   0 fast IO from Burunduk1
 » 3 years ago, # |   0 Premature optimization is the root of all evil. Strict to cin/cout or scanf/printf.
•  » » 2 years ago, # ^ |   0 I was looking for a "real C++" fast Input solution. So I thought about std::cin.readsome() and tried to substitute it to fread(), but even if it's fine on my terminal it is not working on judging servers... namespace FI { const int L = 1 << 15 | 1; char buf[L], *front, *back; void nextChar(char &); template void nextNumber(T &); } void FI::nextChar(char &c) { if(front == back) std::cin.readsome(buf, L), back = (front=buf) + std::cin.gcount(); c = !std::cin.gcount() ? (char)EOF : *front++; } templatevoid FI::nextNumber(T &x) { char c; int f = 1; for(nextChar(c); c>'9'||c<'0'; nextChar(c)) if(c == '-') f = -1; for(x=0; c>='0'&& c<='9'; nextChar(c)) x = x*10+c-'0'; x *= f; } `