Again, low-level i/o C++.

Правка en6, от xsc, 2017-01-26 18:07:25

I decided to rewrite this post, previously has been deleted.

I know there a many of posts low-level i/o.

scanf/printf solves slowly i/o, partially, but not always.

Most generic usage i/o — is read and write integers, so I'll write about it without a hundred lines of source code.

1. Read integers.

For simplicity, all input file content loaded to a big buffer, and it will be parsed.


char in[1<<23] ; // a big buffer char const* o ; // pointer to buffer.

And for detecting end of buffer, put '\0' — terminating symbol to end of buffer ( as plain c-string).

Now loading the file:

void load(){  o = in;   in [   fread(in,  1,  sizeof(in ) - 4 ,  stdin ) ] = 0; }

fread - returns number of reading symbols, we just use this for put '\0' terminating symbol to end of buffer.

Reading a unsigned integer:

unsigned readUInt(){
      unsigned u = 0;
      
      while( *o && *o <= 32) ++o ; //  skip spaces
    
      while ( *o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ -'0');
      return u;
}

By default most implementations used u = u * 10 + (*o++ - '0'),
but u * 10 = u * 8 + u * 2 = (u << 3) + (u <<1) I don't know it gives speed, but with shifting the code become happy :)

Reading signed integer.

Some theory of signed integer representation, in most situation see here

-u == ~u + 1

There ~ — bitwise inverting.

And ~u == u ^ 0xFFFFFFFF or ~u == u ^ ~0

Let start writing method

    int readInt()
    {
         unsigned u = 0, s = 0; // s = 0, if integer positive, s = ~0 - if integer negative
         while(*o && *o <= 32)++o; // skip spaces
         
         if (*o == '-')s = ~0, ++o; else if (*o == '+') ++o; // determine sign
         while( *o >='0' && *o <= '9') u = (u << 3) + (u << 1) + (*o ++ - '0');

         return (u^s) + !!s; // ??????? : s = 0 :  (u^s) + !!s = (u^0) + !!0 = u + 0 = u, and
                             //           s = ~0:  (u^s) + !!s = (u ^ ~0) + !! ~0 = (u^0xFFFFFFFF) + 1 = ~u + 1 = -u
         
    }

How to use this complete?

#include <cstdio>

char const * o;
char in[1<<23];

void load(){ o = in ;  in [ fread(in,1,sizeof(in)-4,stdin)] = 0; }
unsigned readUInt(){
     unsigned u = 0;
     while(*o && *o <= 32)++o;
     while(*o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ -'0');
     return u;
}
int readInt(){
    unsigned u = 0, s = 0;
    while(*o && *o <= 32)++o;
    if (*o == '-') s = ~0, ++o; else if(*o == '+') ++o;
    while(*o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ - '0');

    return (u ^ s) + !!s;
}

int main()
{
     load();
     int n = readInt();
     int s = 0;
     for(int i= 0; i < n; ++i)s += readInt();

     printf("summa = %d\n", s);
     
     return 0;
}

Compare low-level i/o: 24139587 with std::cin , std::cout 24133798

Benchmark: read and write 10^6 numbers took 120~150 milliseconds where scanf/printf ~650 milliseconds.

for competetive programming this single method is enough for reading integers:

   typedef long long ll;
   typedef unsigned long long ull;

    ll  readInt(){
          ull u = 0 , s = 0;
          while(*o && *o <= 32)++o;
          if (*o == '-') s = ~s, ++o; else if (*o == '+') ++o;
          while(*o >='0' && *o<='9') u = (u << 3) + (u << 1) + (*o++ -'0');

          return (u ^ s) +!!s; 
    }

2. Writing integers.

There are need a big buffer and pointer, again.

typedef long long ll;
char out[1<<23];
char * w = out; // initialize with &out[0] - beginning of the buffer.

There a single writeInt method, arguments: integer u and serarator c .

// need to implement this method.
void writeInt( ll u, char separator); // u - integer, separator - will printed after the integer, most situations is space, or '\n'.

AND flush method, which we must call at the end of all operations.

// flush - must be called before end of program.
void flush(){  fwrite(out, 1, w - out, stdout); }

For implementing writeInt need temporary buffer :

void writeInt(ll u, char separator)
{
     char tmpbuf[20]; int i;
     if ( u < 0 ){ *w ++ = '-'; u = - u ; }
     i = 20;
     do tmpbuf[--i] = u % 10 + '0'; while(u/=10); // write last digits of u to tmpbuf from end to begin.
     
     // now write tmpbuf to out[] buffer from w pointer.
     do *w++ = tmpbuf[i++]; while(i < 20);

    // and separator
     *w++ = separator;
}

It's all.

------------------------------------------------------------------------------------------------------

UPD: Wrapper classes.

Let simplify all above codes.

typedef long long ll;
typedef unsigned long long ull;

char in[1<<23];
char out[1<<23];

//wrapper to reader
struct scanner
{
    char const* o;
    scanner(): o(in){ load(); }
    void load(){ in[ fread(in , 1, sizeof(in)- 4, stdin)] = 0; }
    ll readInt(){
        ull u = 0, s = 0;
        while(*o && *o <= 32)++o;
        if (*o == '-')s = ~s, ++o; else if (*o == '+')++o;
        while(*o >='0' && *o <='9') u = (u << 3) + (u << 1) + (*o++ - '0');
        return (u^s) + !!s;
    }
};

//wrapper to writer
struct writer
{
    char * w;
    writer(): w(out){}
   ~writer(){ flush();}
   void flush(){ if (w!=out){ fwrite(out,1,w-out,stdout); w = out; } } 
   void writeInt(ll u, char c){
        char t[20]; int i = 20; 
         if (u < 0){ *w++ = '-'; u = -u;}
        do t[--i] = u % 10 + '0'; while(u/=10);
        do *w++ = t[i++]; while(i < 20);
        *w++ = c;
   }
};


//A+B
int main()
{
    scanner sc;
    writer pw;
    pw.writeInt(sc.readInt() + sc.readInt(), '\n');
}

GOoD lUck!

Теги c++, fast i/o

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский xsc 2017-01-27 13:15:50 2 Tiny change: 'push_back(a); g[b].pu' -> 'push_back(b); g[b].pu'
en7 Английский xsc 2017-01-27 13:10:33 1700
en6 Английский xsc 2017-01-26 18:07:25 1254 Added wrapper classes
en5 Английский xsc 2017-01-26 03:26:19 95
en4 Английский xsc 2017-01-26 03:06:55 1321
en3 Английский xsc 2017-01-26 02:29:45 504
en2 Английский xsc 2017-01-26 02:19:17 6 Tiny change: 'a hundred of source' -> 'a hundred lines of source'
en1 Английский xsc 2017-01-26 02:14:27 3226 Initial revision (published)