Thread: Enormous Input Test

Elysia, gets() is dangerous and atoi() may fail. You're correct on this. I know that. But this discussion is about to find the fastest solution for a given problem. So let's concentrate on that and try to improve the work of the people that posted solutions before.

You may call it evil, but after all, my replacements of scanf() and atoi() are the most significant improvements that were made yet, aren't they?

No, fgets is fine. If you use fgets instead of gets, there will be no problem. So fgets was one of the most significant improvements.

Originally Posted by C_ntua

This code runs as fast as the already posted code (2.18 vs 2.17, the times vary a bit for every test)

I believe that there is an edge case bug in the code: in the case where the input is 1000000000, the fgets() will read 10 characters in and then insert the null character. However, that leaves the newline in the buffer, thus causing the next read to end prematurely. Ironically, this edge case bug is not present with the gets() version since the newline would be read and discarded.

I'd try multithreading. The only thing I could see that would slow it down is sharing the same vector (i.e. having to wait for the other process to finish its job).

Again with the gets. How about fgets version?

Now, the question is if bitshifting is not faster unless the compiler optimizes it?

OK I am REALLY puzzled here.........

I test the program with the example input given on the site... which should output 4.
Why the heck does it give me 4 when I uncomment the commented printf, and gives me 5 when I comment it out?????////

Code:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    unsigned int i, v, n, k, chunk_read,  elements_read = 0, bm = 1, count = 0;
    const unsigned int chunk_size = 1024 * 1024;
    const unsigned int buffer_size = 1024 *1024 * 60; // 60MB
    char *buffer = NULL;
    
    // init buffer
    buffer = (char *)malloc(sizeof(char) * buffer_size);

    scanf("%u %u", &n, &k);
    while (getchar() != '\n');

    // read the input and store to the buffer
    while((chunk_read = fread(buffer, sizeof(char), chunk_size, stdin))) {
        elements_read += chunk_read;
        
    	// if the buffer is running out of space...
        if(elements_read >= buffer_size * bm - 2) {
            ++bm;
            buffer = (char *)realloc(buffer, buffer_size * bm);
        }
    }

    // cap with NULL
    buffer[elements_read] = '\0';
    
    for(i = 0; buffer[i] !='\0'; i++) {
        if(buffer[i] == '\n') {
            if((v / k) * k == v) {
                //printf("%u\n", v);
                count++;
            }
            v = 0;
            continue;
        }

        v = 10 * v + (buffer[i] - '0');
    }

    printf("%u", count);
    return 0;
}

Edit: with the printf commented out, it gives wrong answer in .07 seconds.

Originally Posted by C_ntua

This gives 2.10

Code:

#include <stdio.h>

int main()
{
    char b[11];
    unsigned int i, v, n, k, count = 0;

    scanf("%u %u", &n, &k);
    while (getchar() != '\n');

    while (gets(b)) {
        for (v = 0, i = 0; b[i]; ++i)
            v = 10 * v + (b[i] - '0');

        if ((v / k) * k == v) ++count;
    }

    printf("%u", count);
    return 0;
}

Okay that can't be right. Division and Mod aren't just the same speed, they're the same asm operation as it produces both results at once. So what you've done is add an extra multiply, compare against something non-zero, and you've brought back the if-statement meaning an unpredictable branch again.
Obviously what I posted didn't have as much effect as I thoguht it would. Maybe the compiler was already eliminating the branch.

I'm not sure why everyone's trying to optimize the divisibility test. The claimed purpose of this challenge was to see how fast you can perform I/O. I'd hardly expect the time spent in the division to dominate the time spent reading values from disk.

Anyone for some extreme loop unrolling?:

Code:

#include <stdio.h>

int main()
{
    char b[11];
    unsigned int v, n, k, count = 0;

    scanf("%u %u", &n, &k);
    while (getchar() != '\n');

    while (gets(b)) {
		if (!b[0]) v = 0;
		else if (!b[1]) v = (b[0]-'0');
		else if (!b[2]) v = (10*b[1]+b[0] - (10*'0'+'0')); 
		else if (!b[3]) v = (10*(10*b[2]+b[1])+b[0] - (10*(10*'0'+'0')+'0')); 
		else if (!b[4]) v = (10*(10*(10*b[3]+b[2])+b[1])+b[0] - (10*(10*(10*
			'0'+'0')+'0')+'0')); 
		else if (!b[5]) v = (10*(10*(10*(10*b[4]+b[3])+b[2])+b[1])+b[0] - (10
			*(10*(10*(10*'0'+'0')+'0')+'0')+'0')); 
		else if (!b[6]) v = (10*(10*(10*(10*(10*b[5]+b[4])+b[3])+b[2])+b[1])+
			b[0] - (10*(10*(10*(10*(10*'0'+'0')+'0')+'0')+'0')+'0')); 
		else if (!b[7]) v = (10*(10*(10*(10*(10*(10*b[6]+b[5])+b[4])+b[3])+b[2])
			+b[1])+b[0] - (10*(10*(10*(10*(10*(10*'0'+'0')+'0')+'0')+'0')+'0')+'0')); 
		else if (!b[8]) v = (10*(10*(10*(10*(10*(10*(10*b[7]+b[6])+b[5])+b[4])
			+b[3])+b[2])+b[1])+b[0] - (10*(10*(10*(10*(10*(10*(10*'0'+'0')+'0')
			+'0')+'0')+'0')+'0')+'0')); 
		else if (!b[9]) v = (10*(10*(10*(10*(10*(10*(10*(10*(b[8]-'0')+b[7])+
			b[6])+b[5])+b[4])+b[3])+b[2])+b[1])+b[0] - (10*(10*(10*(10*(10*(
			10*(10*'0'+'0')+'0')+'0')+'0')+'0')+'0')+'0')); 
		else if (!b[10])v = (10*(10*(10*(10*(10*(10*(10*(10*(10*(b[9]-'0')+
			b[8]-'0')+b[7])+b[6])+b[5])+b[4])+b[3])+b[2])+b[1])+b[0] - (10*
			(10*(10*(10*(10*(10*(10*'0'+'0')+'0')+'0')+'0')+'0')+'0')+'0')); 
        count += (v % k) == 0;
    }

    printf("%u", count);
    return 0;
}

Yeah okay so that was a dumb idea.