* * *

In programming minimizing the runtime of your program is very necessary as the time limit of  problems is very strict.

Many times I have come across the warning – “Be Careful! Large Input Output".

In such problems the optimization in the input/output method really helps in giving a better runtime.

After surfing a lot on the web and reading about the different methods, I made a template for myself, which I use in all my problems and sometimes it help me in getting on the 1st page of best solutions ;)

 You can check all the Fast I/O methods on -

 www.spoj.pl/problems/INTEST (Input test)
 www.spoj.pl/problems/INOUTEST (Input + Output Test)

Due to simplicity most of C++ programmers use cin/cout for the Input/Output.
But when the testcases are large cin/cout doesn't work. You can try it on the above problems.
A solution with cin/cout will time out.

So one of the alternate is the scanf/printf which is nearly 3 times faster than the cin/cout.
An Accepted solution of the problem INTEST is

__________________________________________________________________________________

#include<stdio.h>
int main()
{
 int n,k;
 scanf("%d%d",&n,&k);
 int cnt=0;
 while(n--)
 {
  int num;
  scanf("%d",&num);
  if(num%k==0)cnt++; 
 }    
 printf("%d",cnt);
 return 0;
}

__________________________________________________________________________________
But its runtime is 5.52 seconds which is not very good.
So we search for other alternates.

Another faster input handling method is the getchar_unlocked().
getchar_unlocked is thread unsafe as it locks the screen while getting the input. But using it on the spoj server will not harm your screen :D.
It is easy to implement and is very fast.
We can use getchar_unlocked to handle integers and strings faster.

An Implementation of getting integer input through getchar_unlocked() -
Accepted INTEST Solution 
 _______________________________________________________________________________


#include<iostream>
#include<cstdio>
#define gc getchar_unlocked

void scanint(int &x)
{
    register int c = gc();
    x = 0;
    for(;(c<48 || c>57);c = gc());
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}

int main()
{   

    int n,k;
    scanint(n);
    scanint(k);
    int cnt=0;
    while(n--)
    {
     int num;
     scanint(num);
     if(num%k==0)cnt++; 
    }    
    printf("%d",cnt);
    return 0;             
}

__________________________________________________________________________________

And the runtime of this solution is  0.90 secs. which is much faster than the scanf.

Registers are faster than memory to access, so the variables which are most frequently used in a C program can be put in registers using register keyword.

This implementation was for positive integers. Similarly you can make one for the +/- integers.

___________________________________________________________________________________ 

void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}

___________________________________________________________________________________

So this is a very easy way to implement fast Input handling method.

We have another fast Input method that is - fread or fread_unlocked.
There isn't much difference between fread and fread_unlocked as in both the whole input file is first taken in an input buffer and then processed. Main difference is the locking of screen in fread_unlocked.

Implementaion of fread in INTEST ...
 __________________________________________________________________________________

#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
#define size 65536
int main()
{
    
    char b[size];
    int t=0,n,k,cnt=0;
    int c,j;
    scanf("%d %d ",&n,&k);
    while((c = fread(b,1,size,stdin))>0)
    {
               for(j=0;j<c;j++)
               {
                if(b[j]==' ')
                {
                              if(t%k==0)cnt++;
                              t = 0;
                }
                else
                {
                              t = (t*10) + (b[j]-'0');                
                }              
               }
     }
    printf("%d ",cnt);    
    return 0;
}

__________________________________________________________________________________

Now this method is  faster as the runtime of this one is 0.65 secs.
Using fread_unlocked increased the runtime to 0.78 secs.
So better use fread().

But I found getchar_unlocked() much easier to manipulate and code.. So that's my choice.
These were few Input methods that I found useful.. For string handling gets() and fgets() are also good.

 

Rajesh Kumar (IPG-2010) is currently working as forward deployed software engineer at Palantir Technologies and is a great programmer.