Thread: Enormous Input Test

  1. #16
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    4.67 with this
    Code:
    #include <cstdio>
    
    int main() {
        unsigned int n, k;
        unsigned int count = 0;
        
        unsigned int t[8];
        
        scanf("%u %u", &n, &k);
        
        while (n >= 8) { //first do it in blocks of 8
            
            scanf("%u %u %u %u %u %u %u %u",
                   &t[0], &t[1], &t[2], &t[3], &t[4], &t[5], &t[6], &t[7]);
                   
            for (int i = 0; i < 8; ++i) {
                if (!(t[i] % k)) {
                    ++count;
                }
            }
            
            n -= 8;
        }
        
        //do the rest one at a time
        for (int i = 0; i < n; ++i) {
            scanf("%u", &t[0]);
            if (!(t[0] % k)) {
                ++count;
            }
        }
        
        printf("%u", count);
    }
    Out of ideas .

  2. #17
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by cyberfish
    4.67 with this
    Yes, I finally decided to let the site do the benchmarking for me, and finished with about the same timing with a similiar approach, since it was the next obvious implementation that actually made use of n.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #18
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Using laserlight's idea of ignoring n -

    Code:
    #include <cstdio>
    
    int main() {
        unsigned int dummy, k;
        unsigned int count = 0;
        
        unsigned int t[8];
        
        unsigned int n_read;
        
        scanf("%u %u", &dummy, &k);
        
        while ((n_read = scanf("%u %u %u %u %u %u %u %u",
                   &t[0], &t[1], &t[2], &t[3], &t[4], &t[5], &t[6], &t[7]))) { 
                    //first do it in blocks of 8
            
            for (int i = 0; i < n_read; ++i) {
                if (!(t[i] % k)) {
                    ++count;
                }
            }
            
            if (feof(stdin)) break;
        }
        
        printf("%u", count);
    }
    Similar time at 4.76.

    Will try to vary the "block size" and see if it changes anything...

  4. #19
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Doubling the "block size" to 16 doesn't change anything (4.70).

  5. #20
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Naive? Straightforward is more like it
    hehe. "Naive" because I thought it's got to be harder than this...

  6. #21
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Try eliminating the most likely often-mispredicted-branch entirely:
    Code:
            for (int i = 0; i < n_read; ++i) {
                count += (t[i] % k) == 0;
            }
    That should probably give a decent speed boost.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #22
    Registered User
    Join Date
    Oct 2001
    Posts
    62
    scanf() contains some sort of (slow) parser, that we do not need here. Replacing scanf() by gets() and atoi() results in 3.4 (s?) instead of 5.4.

    Code:
    #include <stdio.h>
    
    int main()
    {
        char b[11];
        unsigned int n, k, count = 0;
    
        scanf("%u %u", &n, &k);
        while (getchar() != '\n');
    
        while (gets(b))
            count += (atoi(b) % k) == 0;
    
        printf("%u", count);
        return 0;
    }
    I believe the key to a really fast solution is to combine the functions "ascii to int" and "is divisible by" but I have no idea how to do this yet.

  8. #23
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Never ever use gets!
    http://cpwiki.sf.net/gets
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #24
    Registered User
    Join Date
    Oct 2001
    Posts
    62
    The next n lines of input contain one positive integer ti, not greater than 10^9, each.
    Nothing's wrong with gets() in this special case!

  10. #25
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    No, everything is wrong with it. I is irrelevant if it is faster. It is irrelevant if it safe in this case. Gets is never to be used.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #26
    Registered User
    Join Date
    Oct 2001
    Posts
    62
    2.14, using an atoi() replacement

    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');
    
            count += (v % k) == 0;
        }
    
        printf("%u", count);
        return 0;
    }

  12. #27
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    The gets version 3.35
    The fgets version 3.39
    So there is really not a big difference.
    It would be interesting if there was an algorithm that is faster than the %. That just decides if a number is divisible or not without calculating the remainder. But personally I don't know any such algorithm

  13. #28
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Elysia
    No, everything is wrong with it. I is irrelevant if it is faster. It is irrelevant if it safe in this case. Gets is never to be used.
    To be fair, the rules in a "competition" are different from the normal rules of programming/software engineering, so I would accept gets() in this case since the input is guaranteed to be correct. Likewise, atoi() is acceptable even though there is no way to check for a parse error.

    EDIT:
    Quote Originally Posted by C_ntua
    The gets version 3.35
    The fgets version 3.39
    So there is really not a big difference.
    Yes, if empirical evidence shows that they are effectively equivalent in timing then one might as well use fgets().

    Quote Originally Posted by C_ntua
    It would be interesting if there was an algorithm that is faster than the %. That just decides if a number is divisible or not without calculating the remainder. But personally I don't know any such algorithm
    There are many such algorithms, but I believe there is none for the general case other than by computing the remainder.
    Last edited by laserlight; 12-31-2008 at 07:38 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #29
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by rpet View Post
    2.14, using an atoi() replacement

    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');
    
            count += (v % k) == 0;
        }
    
        printf("%u", count);
        return 0;
    }
    Drop the gets!
    You can also use fgets + two strtol to parse and get the numbers instead of scanf.
    It saves clearing the input buffer.
    But is it faster? That is the question.

    And no one has tried std::getline?

    Quote Originally Posted by laserlight View Post
    To be fair, the rules in a "competition" are different from the normal rules of programming/software engineering, so I would accept gets() in this case since the input is guaranteed to be correct. Likewise, atoi() is acceptable even though there is no way to check for a parse error.

    EDIT:

    Yes, if empirical evidence shows that they are effectively equivalent in timing then one might as well use fgets().


    There are many such algorithms, but I believe there is none for the general case other than by computing the remainder.
    Perhaps there might be; but as gets is dangerous (and as I thought, not much faster than fgets), there is never a reason for it. It is also bad to use it in case someone peeks in the thread and gets it in their heads to use it. Competition or not, I would never consider gets. It is such an evil that should not exist.
    atoi is another story, however, since it does not pose such dangers as gets, but can cause problems in the execution of code. But if it is a simple program, this is acceptable.
    Last edited by Elysia; 12-31-2008 at 07:41 AM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  15. #30
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    This code runs as fast as the already posted code (2.18 vs 2.17, the times vary a bit for every test)
    Code:
    #include <stdio.h>
    
    int main()
    {
        char b[11], a[22]; char* end;
        unsigned int i, v, n, k, count = 0;
        fgets(a, 22, stdin);
        n = strtol(a, &end, 10);
        k = strtol(end, NULL, 10);
    
        while (fgets(b, 11, stdin)) {
            for (v = 0, i = 0; b[i]; ++i)
                v = 10 * v + (b[i] - '0');
    
            count += (v % k) == 0;
        }
    
        printf("%u", count);
        return 0;
    }

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