Enormous Input Test

This is a discussion on Enormous Input Test within the C++ Programming forums, part of the General Programming Boards category; Would read()/pread() help? (unportable, but assuming it is Linux or at least POSIX) Reading blocks of, say, 10MB at a ...

  1. #46
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,146
    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?

  2. #47
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by iMalc View Post
    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....

  3. #48
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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...

  4. #49
    Registered User
    Join Date
    Oct 2001
    Posts
    62
    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;
    }

  5. #50
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Quote Originally Posted by rpet View Post
    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.

  6. #51
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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;
    }

  7. #52
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,981
    Apparently the large buffer is not an advantage since testing with BUFSIZ instead of 0x80000 gave timings of 0.81, 0.75 and 0.85:
    Code:
    #include <stdio.h>
    
    #define N BUFSIZ
    
    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;
                }
            }
        } while (nread == N);
    
        printf("%u", count);
        return 0;
    }
    So, what's next? Try something platform dependent as cyberfish proposed?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 4 of 4 FirstFirst 1234
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Integer Emulation
    By Elysia in forum C++ Programming
    Replies: 31
    Last Post: 03-18-2008, 01:03 PM
  2. For loop problems, input please.
    By xIcyx in forum C Programming
    Replies: 2
    Last Post: 04-22-2007, 03:54 AM
  3. MSVC Template Constructor/Assignment Errors
    By LuckY in forum Windows Programming
    Replies: 3
    Last Post: 07-22-2005, 02:57 PM
  4. input files in C
    By LWisne in forum C Programming
    Replies: 4
    Last Post: 09-30-2002, 06:24 AM
  5. Segmentation fault with input test file
    By bentles in forum C Programming
    Replies: 20
    Last Post: 04-28-2002, 08:58 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21