Thread: Enormous Input Test

Would read()/pread() help? (unportable, but assuming it is Linux or at least POSIX) Reading blocks of, say, 10MB at a time.

Do they work on stdin?

Originally Posted by iMalc

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.

Well, that is the result it gives, though I get your point.
Replacing it with if (v % k == 0) ++count; gives more or less the same result. The point is to augment count when it is divisible and not always as you do with count += v % k == 0;. But all these codes give more or less the same result so it doesn't really matter....

This:

Code:

#include <stdio.h>

int main()
{
    const int ENDF = EOF - '0';
    const char ENDL = '\n' - '0';
    char b[11];
    unsigned int i, v, n, k, count = 0;

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

    while ((b[0] = getchar() - '0') != ENDF) {
        v = b[0];
        for (n = 1; (b[n] = getchar() - '0') != ENDL; ++n) v = 10 * v + b[n];
        if (v % k == 0) ++count;
    }
    printf("%u", count);
    return 0;
}

which seems to be an optimization runs at 3.13...

I'm not sure why everyone's trying to optimize the divisibility test. (...) I'd hardly expect the time spent in the division to dominate the time spent reading values from disk.

That's right. 0.90 using buffered input...

Code:

#include <stdio.h>

#define N 0x80000

unsigned char inputv[N];

int main(void)
{
    size_t nread;
    unsigned int j, v, n, k, count = 0;

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

    do {
        nread = fread(inputv, 1, N, stdin);

        for (j = 0; j < nread; ++j) {
            unsigned char c = inputv[j];

            if (c != '\n')
                v = v * 10 + (c - '0');
            else {
                count += (v % k) == 0;
                v = 0;
            }
        }
    } while (nread == N);

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

Originally Posted by rpet

That's right. 0.90 using buffered input...

Code:

#include <stdio.h>

#define N 0x80000

unsigned char inputv[N];

int main(void)
{
    size_t nread;
    unsigned int j, v, n, k, count = 0;

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

    do {
        nread = fread(inputv, 1, N, stdin);

        for (j = 0; j < nread; ++j) {
            unsigned char c = inputv[j];

            if (c != '\n')
                v = v * 10 + (c - '0');
            else {
                count += (v % k) == 0;
                v = 0;
            }
        }
    } while (nread == N);

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

Cool way of doing buffered input. I tried to do it by dynamic allocation but failed miserably :-), I guess I learn something new every day. Thanks.

Well a small optimization (no big deal) gives 0.88:

Code:

#include <stdio.h>

#define N 0x80000

unsigned char inputv[N];

int main(void)
{
    size_t nread;
    unsigned int j, v, n, k, count = 0;

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

    do {
        nread = fread(inputv, 1, N, stdin);

        for (j = 0; j < nread; ++j) {
            unsigned char c = inputv[j];

            if (c != '\n') {
                v = v * 10 + (c - '0');
            } else if (v % k == 0) {
                ++count;
                v = 0;
            } else {
                v = 0;
            }
        }
    } while (nread == N);

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