fast I/O in C/C++
There many ways to do input/output in C/C++. Some are slow, some are fast and some can be very fast. Here I’ll be discussing some of these methods.
Many a times during competetive programming you come across the warning “Careful – large input/output“. Now what exactly does this means?
This basically means that you have to use an optimized code for your reading/writing to the standard input/output to stay inside the tighter time constraints of the problem. So let’s get going and explore the different methods to optimize your I/O in C/C++.
All the code can be found here: GitHub.
First one is the basic method that you guys must already be using. This is based on cin/cout methods of the iostream library. It is the most basic method and does not require you to specify the type of input you are expecting, but, is extremely slow.
01 02 03 04 05 06 07 08 09 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 | #include <iostream> #include <string> #include <sstream> using namespace std; int main() { /* integer or any integer like */ int integer; cin>>integer; cout<<integer<<endl; /* character string */ char charstring[100]; cin>>charstring; // stops input after a "space" cout<<charstring<<endl; cin.getline(charstring, 100); // stops after 100 character or eof whichever comes first cout<<charstring<<endl; string strstring; cin>>strstring; // stops input after a "space" cout<<strstring<<endl; getline(cin, strstring); // stops after eof or '\n', whichever comes first cout<<strstring<<endl; /* safest way to get an integer (but very slow) - taken from cpluspls.com */ int number = 0; string input; while ( true ) { getline(cin, input); stringstream myStream(input); if (myStream>>number) break ; } /* Safest way to get a single character */ char singlechar = {0}; while ( true ) { getline(cin, input); if (input.length() == 1){ singlechar = input[0]; break ; } } } |
The second method is based on the simple printf/scanf functions of stdio.h library for C. These are much faster than the above method and can be easily used in competetive programming for a decent time limit. These are multi-thread safe as they lock the file before writing.
Detailed description of the stdio.h library you can refer to here.
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <cstdio> #include <string> int main() { /* integer I/O */ int a; scanf ( "%d" , &a); printf ( "%d\n" , a); /* Other format specifiers. %d, %i = signed integer %u = unsigned integer %l = prefix for long %f = signed floating point %e = signed scientific %c = single character */ /* sting I/O */ char charstring[100]; scanf ( "%s" , charstring); // only till the first white space is stored printf ( "%s\n" , charstring); scanf ( "%[^\n]s" , charstring); // sets th delimeter to be "new line" printf ( "%s\n" , charstring); // thus whole line is read until a \n is observed // does not eliminate \n from the input stream gets (charstring); printf ( "%s\n" , charstring); } |
This method is very fast than the last method and used unlocked versions of the above functions used. I have written the code to scan integer and a string. For others you can easily write your function referring the below code. These are NOT multi-thread safe. Should be used in caution. But, in competetive programming plateforms, one program is already separated from others, so can easilt be used for better I/O in competetive programming which have even tighter time constraints.
01 02 03 04 05 06 07 08 09 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 | #include <cstdio> inline void fastRead_int( int &x) { register int c = getchar_unlocked(); x = 0; int neg = 0; for (; ((c<48 || c>57) && c != '-' ); c = getchar_unlocked()); if (c== '-' ) { neg = 1; c = getchar_unlocked(); } for (; c>47 && c<58 ; c = getchar_unlocked()) { x = (x<<1) + (x<<3) + c - 48; } if (neg) x = -x; } inline void fastRead_string( char *str) { register char c = 0; register int i = 0; while (c < 33) c = getchar_unlocked(); while (c != '\n' ) { str[i] = c; c = getchar_unlocked(); i = i + 1; } str[i] = '\0' ; } int main() { int n; char s[100]; fastRead_int(n); printf ( "%d\n" , n); fastRead_string(s); printf ( "%s\n" , s); return 0; } |
There is another method I came across a solution in one of the problems on codechef. I haven’t tested it’s performance, but, his solution had the lowest timing with the same logic for the actual problem. So, I am assuming this gives a better performance for I/O. You can download the code here.
The solution referrenced is this.
I’ll come up with more updates on the same topic.
Hi, what’s the point of doing bitwise shift here: x = (x<<1) + (x<<3) + c – 48;
x=x*2^1+x*2^3+c-48…
Now you can understand what it does.
It multiplies the current value with 10 and then add the incoming character.
lets say x=0,c=’5′;
x=0+0+53-48;
x=5;
now c=’6′;
x=5*(2^1)+5*(2^3)+54-48;
=10+40+54-48—>56;
This is multiplying by 10
x = x * 10 + c
Hey Chirag,
Great site you got here. I’m not too familiar with C++ but thank you for providing the source to this fix. I also check out GitHub when I’m stuck.
Thanks for the resource.
Dennis
Thanks so much for the blog post. Awesome.
Which header file to include ?
The required header files are given in the code itself.
For the first one you need: iostream , string and sstream
second part: cstdio and string
For the third code you only need: cstdio
Thank you, btw awesome post. Great help.