Faster Decimal Number I/O In C

(Comments)

Today I was playing (never competing, please!) on a CodeChef 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 CodeChef 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?

By Flavio de Sousa

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 on my code improved its speed down to 0.07 secs! All techniques together amounted to near 10x improvement!

Currently unrated

Comments