How can this code be improved to avoid timeout with large numbers of data entries?

Question

My solution to a HackerRank problem works but times out when very large amounts of data are used, such as the following: https://hr-testcases-us-east-1.s3.amazonaws.com/9403/input11.txt?AWSAccessKeyId=AKIAJ4WZFDFQTZRGO3QA&Expires=1565703339&Signature=JcuoWT7wKxpU3GWudO4wLNWK6Dg%3D&response-content-type=text%2Fplain

I'm quite aware that the code is far from ideal, and will probably make experienced software developers cringe... so I'm hoping it can be improved.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int N;
    cin >> N;
    vector<int> v;
    vector<string> s;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    } 
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int a;
        int b = 0;
        cin >> a;
        for (int j = 0; j < v.size(); j++) {
            if(v[j]==a) {
                s.push_back("Yes " + to_string(j+1));
                b++;
                j=v.size();
            }
        }
        if (b==0) {
            vector<int>::iterator low;
            low = std::lower_bound(v.begin(), v.end(), a);
            int d = low-v.begin();
            d++;
            s.push_back("No " + to_string(d));
        }
    }
    for (int i = 0; i < s.size(); i++) {
        cout << s[i] <<"\n";
        }
    return 0;
}

The problem statement is: Ideally, I'd rather not have a completely new solution, but rather get some help making this one better.

This code style is awful, you can define functions in C++, you know? Modularize your code, do IO only in one place, and then pass it to a function. Also questions without a clear question statement are off topic. Post the task. And no not the link to it. — Superlokkus, Aug 13 '19 at 11:47
I'll post the task. I had to link to the data causing the timeout because it's so much that it would distract immensely from the question. — John Arg, Aug 13 '19 at 11:51
Thing is your question won"t solve an original problem but would answer the problems specific to your code, which probably has either rather architecture specific, c++ specific performance issues, or algorithmic complexity of your general abstraction or your abstract solution is problematic. Thing is your IMHO extrem sloppy code, makes it extra diffucult to find out which. If you would post it on code review (another stack exchange site), first thing would be: Clean up your code! After that the issues will submerge which are probably already solved and easy to be found. — Superlokkus, Aug 13 '19 at 11:59
I'll post it on Code Review, but I'm not sure how to modularize it. Everything does something different as far as I can see. I just started programming a few days ago. — John Arg, Aug 13 '19 at 12:10
I recommend reading "C++ primer" by Stanley B. Lippman. Putting your code out for critique is good and more programmers should do it, but I believe you should put more effort in learning the basics first. — Superlokkus, Aug 13 '19 at 12:15

score 1 · Answer 1 · answered Aug 13 '19 at 12:03

1

First of all, it is always useful to analyze the performance of a software by profiling it with the adeguate tool, see here.

With just taking a look at is, there are a few points which you could optimize:

the s list is useless. You push back data on it and then print in order. Just print directly. You would save memory and the last for loop.
inside your second loop you first perform a linear search and then, if nothing is found, you use std::lower_bound which has logarithmic complexity. You could reduce the time by just looping once and looking for the element or the smallest one at the same time, reducing the amount of looping you need. You can also take advantage of the fact that the N integers are sorted to stop the search earlier.

answered Aug 13 '19 at 12:03

bracco23

2,181
10
28

I am supposed to have everything print at the end though. Whereas if I print directly it gives an answer, and then asks for another input, then gives the answer for this input, etc. I need all the inputs to be given at once, and then all the answers. Is there any other way to do that? As for ```std::lower_bound```, I am required to use it as it is the main point of the challenge. – John Arg Aug 13 '19 at 12:08
I can't see that requirement in the problem statement. – bracco23 Aug 13 '19 at 12:10
Sorry, it's not part of the statement, but it's the name of the problem: Lower Bound – STL. – John Arg Aug 13 '19 at 12:11
I was referring to the "print everything at the end" part. About `lower_bound`, if you read carefully at the [documentation](https://en.cppreference.com/w/cpp/algorithm/lower_bound), sounds like it should give already the same element if it is part of the list, so you should be able to drop your first loop and just use that. – bracco23 Aug 13 '19 at 12:14
Oh thanks, I'll change that. As for printing everything at the end, it marks the test cases as false if I don't.... it's what I did at first. – John Arg Aug 13 '19 at 12:15

How can this code be improved to avoid timeout with large numbers of data entries?

1 Answers1