dario-dsa's blog

By dario-dsa, 11 years ago, In English

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

  • Vote: I like it
  • -14
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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;
}
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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;
    }
    
    
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It`s really faster than scanf, Thanks a lot.I was able to solve the problem which has not previously held a scanf

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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!

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        is it because he is cyan ?

        No, he surely wasn't cyan 3 years ago.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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<int>( (u^s) + !!s) ;
    }
    
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Go to Codechef. Find a problem with a huge amount of input. Look at the fastest submit. Profit.

»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

You can use fast cin/cout by writing "ios::sync_with_stdio(false);" on the top of your programm!

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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++).

»
11 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You might also be interested in this article I wrote a while ago; I performed some similar I/O benchmarks: http://codeforces.me/blog/entry/5217

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        2,147,483,640 + 8 overflows and becomes -2,147,483,648.

        It doesn't

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          On most machines it works just fine. I have used mod 2^32 overflow in many competitions and it hasn't failed me once.

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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.)

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it -12 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                    Vote: I like it -25 Vote: I do not like it

                  What does that have to do with anything? This is clearly a compiler bug.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  Rev. 2   Vote: I like it -15 Vote: I do not like it

                  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)

»
8 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Slightly irrelevant, but since the topic was brought up: I've never seen contests that give contestant choice to perform IO using either:

  1. formatted input/output (human readable, slower for integer IO, most contests use this)
  2. 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:

  1. is harder to maintain (e.g. in CodeForces you use only stdin/stdout, what do you use as 3rd/4th stream?)
  2. could provoke "silly" mistakes (forgeting to switch between formatted <--> binary) in participants code
  3. 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".

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Premature optimization is the root of all evil. Strict to cin/cout or scanf/printf.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 <typename T>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++;
    }
    
    template<typename T>void 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;
    }