Thread: Enormous Input Test

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    182

    Enormous Input Test

    I haven't been in these forums for a while... I've been learning much about Linux and about Perl and PHP :-)

    I do know a lot of C, but not much C++, and I found a cool website that has an online judge and I've been working on some problems there.

    Enormous Input Test

    Code:
    The purpose of this problem is to verify whether the method you are using to read input
    data is sufficiently fast to handle problems branded with the enormous Input/Output
    warning. You are expected to be able to process at least 2.5MB of input data per
    second at runtime.
    
    Input:
    The input begins with two positive integers n k (n, k<=107). The next n lines of input
    contain one positive integer ti, not greater than 109, each.
    
    Output:
    Write a single integer to output, denoting how many integers ti are divisible by k.
    
    Example:
    Input:
    7 3
    1
    51
    966369
    7
    9
    999996
    11
    
    Output:
    4
    My program failed twice because of exceeded time limit. Here is my code:
    Code:
    #include <iostream>
    
    using namespace std;
    
    int main() {
        long n, k, count = 0;
    
        cin >> n >> k;
        long *ti = new long[n];
    
        for(int i = 0; i < n; i++) {
            cin >> ti[i];
        }
    
        for(int i = 0; i < n; i++) {
            if(ti[i] % k == 0)
                count++;
        }
    
        cout << count;
    }
    What would be a better way to read all the input faster? I also tried reading from cin and testing for division on the same loop, but that was not fast enough either.

    Thanks!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    It does not look like dynamic memory allocation is actually needed.
    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. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Quote Originally Posted by laserlight View Post
    It does not look like dynamic memory allocation is actually needed.
    My other variation, which does not use dynamic memory allocation and also failed because of expired time limit.
    Code:
    #include <iostream>
    
    using namespace std;
    
    int main() {
        long n, k, count = 0;
    
        cin >> n >> k;
    
        for(int i = 0; i < n; i++) {
            long ti;
            cin >> ti;
    
            if(ti % k == 0)
                count++;
        }
    
        cout << count;
    }
    Oh and on the original post, the max numbers are supposed to be 10^7 and 10^9, not 107 or 109.
    Last edited by samus250; 12-30-2008 at 02:32 PM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by samus250
    My other variation, which does not use dynamic memory allocation and also failed because of expired time limit.
    In that case, consider switching to C-style input to see if it makes any difference.
    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

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Quote Originally Posted by laserlight View Post
    In that case, consider switching to C-style input to see if it makes any difference.
    by using scanf("%ld", &x)? ... let's try that.

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Quote Originally Posted by laserlight View Post
    In that case, consider switching to C-style input to see if it makes any difference.
    Holy crap it worked!

    Though there are people who do it even faster. Mine took 5.36 seconds (8 seconds is the time limit) and some people do it in about 3 seconds (others in less than 1...)

    Let's combine dynamic memory allocation with that and see what happens.

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Almost no difference with dynamic allocation, just .05 seconds faster.
    Without dynamic allocation, the program takes 2.5M, with it the program takes 9.9M so storing all the input to memory first is not the way to go.

    Thanks a lot laserlight! Any other ideas on how I can make it run faster?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by samus250
    Almost no difference with dynamic allocation, just .05 seconds faster.
    Without dynamic allocation, the program takes 2.5M, with it the program takes 9.9M so storing all the input to memory first is not the way to go.
    That is interesting. You mean that using dynamic memory allocation is an improvement? I do not see a space-time trade-off benefit here, so that is puzzling.
    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

  9. #9
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Quote Originally Posted by laserlight View Post
    That is interesting. You mean that using dynamic memory allocation is an improvement? I do not see a space-time trade-off benefit here, so that is puzzling.
    Well, the judge told me it took .05 seconds less...

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by samus250
    Well, the judge told me it took .05 seconds less...
    Well, that is an example of why we should measure when we want to determine performance
    Nonetheless, why not show the source code of both the programs involved?
    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

  11. #11
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by samus250 View Post
    Well, the judge told me it took .05 seconds less...
    It's just random jitter.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #12
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Quote Originally Posted by laserlight View Post
    Well, that is an example of why we should measure when we want to determine performance
    Nonetheless, why not show the source code of both the programs involved?
    I will, thing is that I modified it, so I'll make it again.

    Also... any idea why is this code giving me a runtime error? (it's C)
    Code:
    #include <stdio.h>
    
    int main() {
        long n, k, i, ti, count = 0;
    
        scanf("%ld", &n);
        scanf("%ld", &k);
    
        for(i = 0; i < n; i++) {
            scanf("%ld", &ti);
    
            if(ti % k == 0)
                count++;
        }
    
        printf("%ld", count);
    }
    Last edited by samus250; 12-30-2008 at 03:26 PM.

  13. #13
    Registered User
    Join Date
    Jan 2008
    Posts
    182
    Quote Originally Posted by brewbuck View Post
    It's just random jitter.
    That's what I was thinking too.

  14. #14
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    My naive first simple implementation did it in 5.39 seconds.

    Will try to tweak it further.

    Code:
    #include <cstdio>
    
    int main() {
        unsigned int n, k, t;
        unsigned int count = 0;
        
        scanf("%u %u", &n, &k);
        
        for (unsigned int i = 0; i < n; ++i) {
            scanf("%d", &t);
            if (!(t % k)) {
                ++count;
            }
        }
        printf("%d", count);
    }

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    My naive first simple implementation did it in 5.39 seconds.
    Naive? Straightforward is more like it , and it is similiar to what samus250 did, hence the similiar timing. Incidentally, scanf and printf belong to the std namespace. Actually, with this particular implementation the initial value n does not seem useful to me (maybe that is a hint), so it seems simpler to write:
    Code:
    #include <cstdio>
    
    int main() {
        using namespace std;
    
        unsigned int n, k;
        scanf("%u %u", &n, &k);
    
        unsigned int count = 0;
        while (scanf("%u", &n) == 1) {
            if (n % k == 0) {
                ++count;
            }
        }
        printf("%u", count);
    }
    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

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