0
\$\begingroup\$

I'm trying to solve the sorting problem but I always get TLE(Time Limit Exceeded/ 1s) so... can you guys suggest a more efficient way to solve this problem? (i can't link the exercise because it is on the closed server)

code reads test count t , <int, string> pairs then sorts by integer in ascending order and prints median

#include <bits/stdc++.h>
using namespace std;
 int main(int argc, char *argv[]) {
   vector< pair <int,string> > median;
   int t;  cin >> t;
   int num; string name;
   for(int i=0;i<t;i++) {
     cin>>name; cin>>num;
     median.push_back( make_pair(num,name));
   }
  sort(median.begin(), median.end());

    if(t%2!=0){
      cout << median[t/2].second << " " << median[t/2+1].first << endl;
    }else{
      cout << median[t/2-1].second << " " << median[t/2+1].first << endl;
      cout << median[t/2].second << " " << median[t/2+1].first << endl;

        }
 }

input:

Gilbert 35
Anna 35
Anna 15
Mary 15
Joseph 40

output:

Anna 35
\$\endgroup\$
3
  • \$\begingroup\$ sort depends only on integer/ it is working as expected but getting very slow on high count test cases \$\endgroup\$
    – Blue339
    Mar 9 at 16:39
  • \$\begingroup\$ cout << median[t/2].second << " " << median[t/2+1].first << endl; kid me. \$\endgroup\$
    – greybeard
    Mar 9 at 20:04
  • \$\begingroup\$ code does X Your code does not document the problem to solve. Your post does not describe the problem to solve. \$\endgroup\$
    – greybeard
    Mar 9 at 20:07
4
\$\begingroup\$

I don’t do programming challenges, so my review will be more from the point of view of actually writing decent C++ rather than the programming challenge mindset (which, in my humble opinion, encourages terrible coding practices). Nevertheless, if it’s performance you want, I can give you some tips on how to get some huge speed increases.

So let’s dive in.

#include <bits/stdc++.h>

I’ve heard this is standard practice in programming challenge circles. Nevertheless, it is terrible practice in real life. Instead, look at all the standard library components you use, and include the headers for them. In your case, you use cin/cout, vectors, strings, pairs, and the sort function, so you’ll need their headers. Including only those headers should speed up compilation measurably, but I don’t know if compilation time is counted in total time, so I don’t know how much that will help.

using namespace std;

Never do this, even in a programming challenge. It’s just a terrible habit that will eventually bite you in the ass. Just put std:: where needed. Just get used to it.

int main(int argc, char *argv[]) {

Since you don’t actually read the command line, you can just use the simpler form of main().

Now you’ve packed your entire program into main(). That’s okay for this very trivial program, but you should really get in the habit of writing better code. Isn’t that what programming challenges are for, after all?

Break the program into logical steps, and put each major step into its own function. It costs nothing; even the most basic level of optimization will eliminate all the overhead (and anything it doesn’t isn’t worth eliminating).

The first step is to read the number of pairs in the data set… so it should be a function called read_dataset_size(), or something like that. It could look something like this:

auto read_dataset_size() -> int;

Or, even better, take the input stream as a parameter:

auto read_dataset_size(std::istream&) -> int;

Why would you do that? Because it makes the function easier to test. You should always program with testing in mind, even for off-the-cuff code like this. Because if something doesn’t work—and we all make stupid mistakes—you want to be able to do tests to figure out what the problem is. With the function written like above, you can read the input from a file, or even directly from memory, and see whether you get the expected result.

So, refactored that way, the read_dataset_size() function looks like this:

auto read_dataset_size(std::istream& in) -> int
{
    int t;  in >> t;

    return t;
}

(This is just your code exactly as you’ve written it, except I replaced cin with in. And of course, added the return statement.)

Now, you should never write two statements on a single line. Space costs nothing, but being able to read code clearly is the difference between having silly hidden bugs or not. So:

auto read_dataset_size(std::istream& in) -> int
{
    int t;
    in >> t;

    return t;
}

Even better would be to give clear names to the variables:

auto read_dataset_size(std::istream& in) -> int
{
    int size;
    in >> size;

    return size;
}

Normally you’d do error checking to make sure you actually read a proper number and all… but okay, I get this is just challenge code. So we’ll skip the error checking.

That’ll do for this bit.

Your next function should be something like read_data_pairs() or something. It should look something like this:

auto read_data_pairs(std::istream&, int) -> std::vector<std::pair<int, std::string>>;

And with your code refactored into it:

auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
    std::vector< std::pair <int,std::string> > median;

    int num; std::string name;
    for(int i=0;i<size;i++) {
        in>>name; in>>num;
        median.push_back( std::make_pair(num,name));
    }

    return median;
}

(Note this is exactly your code with the std::s added, cin replaced with in, and t replaced with size, and of course the return statement added.)

Alright, now let’s talk performance.

Here’s the problem: vector automatically resizes to accommodate more data. When it does, it has to allocate a new chunk of memory (usually twice the size of the existing capacity), and then copy all the old data into the new memory. If there are 1,000 pairs in the vector, then the vector would have to allocate space for 2,000 pairs, and then do 1,000 copies (technically, moves). In modern C++, that all happens very quickly… but it’s still not free; there’s still a cost. And if you’ve got millions of pairs….

Even worse, it will probably happen many, many times as you read in the data. Your vector will start empty, and then have to allocate space for a couple elements. You’ll read in a couple elements, then run out of space again… so the vector will have to allocate a new block of memory, and copy everything over. Now you’ll read in a few more elements… but soon run out of space again. So the vector will have to reallocate and copy again. And it will have to do it over and over and over. And as the number of elements becomes huge, all that allocating and copying will add up quickly.

Here’s the key to fixing that problem. You already know the size of the input data. So you can just pre-allocate all the space you need, and avoid the need for all that reallocation and copying. The technically correct way would be to do this:

auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
    std::vector< std::pair <int,std::string> > median;  // median probably
                                                        // isn't a great name
                                                        // for this variable,
                                                        // because it isn't
                                                        // the median... it's
                                                        // all the input data
                                                        //
                                                        // maybe call it
                                                        // "pairs" instead?

    median.reserve(size); // this is the magical line that will probably fix
                          // all your performance problems

    int num;
    std::string name;
    for(int i=0; i < size; ++i)
    {
        in >> name;
        in >> num;

        median.push_back( std::make_pair(num,name));
    }

    return median;
}

That one line alone will probably fix your timeout errors.

But we can do even better.

Although we’re reserving all the memory we’re going to need, we’re still pushing elements on to the vector. Now it is going be very quick… but, again, still not free.

So instead of just reserving space and then pushing elements in to the vector over and over… why not create the elements right away, and then read the data directly into them? No extra copies needed.

This is technically not good practice in general… but it is a valid hack for efficiency. And efficiency is what you’re gunning for.

So:

auto read_data_pairs(std::istream& in, int size) -> std::vector<std::pair<int, std::string>>
{
    std::vector<std::pair<int,std::string>> median;

    median.resize(size);    // note: reSIZE, not reSERVE
                            // this will fill the entire vector with the
                            // right number of pairs in a single shot

    // note: no more need for temporaries to read input!
    // we'll be reading *directly* into the proper place

    // note: we can use the much safer range-for loop now
    for (auto&& element : median)
    {
        in >> element.first;
        in >> element.second;
    }

    return median;
}

That’s about as fast as that can be, I think.

The sorting is just a call to std::sort()… not much we can do to improve that, or speed that up.

Now, the way the output is printed is a bit weird. Why do you do median[t/2].second and then median[t/2+1].first? Are you sure that’s correct? Have you tested it with more data than what is shown? (Seriously, TEST YOUR CODE!!! That’s the biggest thing that separates the shitty coders from the good ones. You should test your code with multiple data sets, including edge cases likely to cause problems (like a 1-element data set, for example).)

I have a hunch you have a bug, but can’t be sure because you haven’t given the actual program requirements. So I’m just going to assume your code isn’t broken (but I think it is!).

Now, the output could be slightly faster. Instead of:

cout << median[t/2].second << " " << median[t/2+1].first << endl;

You could do:

std::cout << median[t / 2].second << ' ' << median[(t / 2) + 1].first << '\n';

There are two things I changed (other than the spacing to make it more readable, and adding the std::):

  1. The space is now a single character, rather than a string. In theory, this should be much faster, because a single character is a single character… while a string requires reading multiple characters with a loop and a conditional (to search for the NUL). (In reality, the compiler probably optimizes this for you anyway.)
  2. Don’t use std::endl. std::endl prints a newline… and then flushes the stream, which is expensive. The stream is going to be flushed automatically anyway, so there’s no sense paying for it multiple times.

There’s one final trick I can think of that might gain you a bit more speed: std::ios::sync_with_stdio(false);. This is a high-level trick, but with a cost: if you do this, you cannot use any of the C stdio library. That means no printf(), no fopen(), none of that. What’s going on is that, by default, the C++ I/O streams will synchronize with the C stdio streams. This is a handy convenience that allows you to mix std::cout and printf(). BUT! That comes with a heavy cost. It slows down std::cin and std::cout a LOT. If you never use any C stdio stuff, then you can turn that synchronization off, and get a huge performance boost. It might make a difference for you, or it might not. Either way, just stick std::ios::sync_with_stdio(false); right after the beginning of main().

Okay, in summary, I think the reason you’re getting timeouts is all due to the way you’re reading the input. By not pre-allocating the vector, it is forced to constantly re-allocate and copy (move) all of its contents, over and over and over. Just be pre-allocating the vector with reserve(), you will spare yourself all that wastage by doing one single allocation, and avoiding all the copying (moving) entirely. Even better, you can just size the vector one time up front, and then read the data directly into its elements, so now you don’t even need to read into temporaries then copy into the vector.

Adding std::ios::sync_with_stdio(false); may help, too.

But most importantly: TEST YOUR CODE!!! I think you have a bug. You say your code works, so I assume you know what you’re doing… but I’m still skeptical. TEST YOUR CODE!!! See for yourself whether it really works the way you think it does. You just need simple tests, like this (using the Catch2 test framework):

TEST_CASE("dataset size is read correctly")
{
    auto const test_data = R"(
3
1 Alice
2 Bob
3 Carol
)";

    auto iss = std::istringstream{test_data};

    CHECK(read_dataset_size(iss) == 3);
}

TEST_CASE("simple data is read correctly")
{
    auto const test_data = R"(
3
1 Alice
2 Bob
3 Carol
)";

    auto iss = std::istringstream{test_data};

    // just assume this works and throw the result away, because it is tested
    // in the other test case
    [[maybe_unusued]] auto const data_size = read_dataset_size(iss);

    auto const data = read_data_pairs(iss, 3);

    CHECK(data.size() == 3);

    CHECK(data.at(0) == "Alice");
    CHECK(data.at(1) == "Bob");
    CHECK(data.at(2) == "Carol");
}

Then you just need a couple more tests to make sure sorting produces the right result, and that you print the right output for the median. After that, you could add more tests with different test data to test different potential problems. Get in the habit of testing your code. You may even find benefits with this very program….

\$\endgroup\$
1
\$\begingroup\$

In your post, you write

code reads test count t , <int, string> pairs then sorts by integer in ascending order and prints median.

However, the call to sort the std::vector does not do that. It sorts by using both the first (an int) and second (a string) of the elements of the vector. If you want to sort by just the first of the elements, use a custom comparator.

std::sort(median.begin(), median.end(), [](std::pair<int, std::string> const& item1,
                                           std::pair<int, std::string> const& item2) -> bool
                                           { return item1.first < item2.first});

That change will improve performance too -- you are comparing just ints for sorting not ints plus std::strings.

\$\endgroup\$
1
  • \$\begingroup\$ If you do that, you might not get the expected output. Instead of Anna 35 you might get Gilbert 35. \$\endgroup\$
    – indi
    Mar 10 at 20:38
1
\$\begingroup\$

In addition to the other answers:

Use std::nth_element() instead of std::sort()

std::sort() will completely sort the input. However, you are only interested in the middle (two) element(s). The standard library has a function for that, which will do only a partial sort until it guarantees that the element at a given position has the value you would expect if the input was sorted: std::nth_element().

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.