Faster Decimal Number I/O in C
Today I was playing (never competing, please!) in a Code Chef programming contest and was dismayed when comparing my timings with some other competitors. Theirs were way shorter, and I saw no way to improve my O(N) solution because I HAD to read an array of values. My processing was taking place while reading the data, using no loops, only simple calculations.
Where was the problem? Where? The I/O?
I was using the C Standard Library for I/O, scanf("%d", &var)
for reading numbers and printf("%d",var)
for writing. Those "%d"
needed to be parsed and THEN processed. Every time! So they surely were one of the culprits of my slight slowness.
My timings using scanf()
and printf()
were around 0.65 seconds.
So I decided to write my own specialized I/O for the problems:
#include <stdio.h>
int getint()
{
int r = 0, i = 0;
int c;
for (;;) {
c = getchar();
if (c < 0) return i;
if (c >= '0' && c <= '9') {
if(!r) r = 1;
i = i * 10 + c - '0';
} else {
if (r) return i;
}
}
}
void putlonglong(long long v)
{
if (v > 9) {
putlonglong(v / 10);
}
putchar('0' + v % 10);
}
And now by timings improved considerably: 0.30 seconds!
But there are still some people doing it in 0.01 seconds! Man, what are they doing? Anything better than getchar()
/putchar()
? C++ streams?
Update: Contest finished, and I was able to check the winners' submissions. Turned out my approach was widely adopted among them, but with a little improvement: using getchar_unlocked()
instead of getchar()
. Doing this change to my code improved its speed down to 0.07 secs. All techniques together amounted to a near 10x improvement.