Input 300 000 sets of numbers with cin or scanf

Question

Hi,

I am participating in programming contest. My algorithm is fine with number of sets to 5000. Sets of values are consist of three integers. But I enter 300 000 sets of numbers, it takes too long.

Limit of running program: 14s. Fetching data: 576s. (Way too long)

My formatted input is:

300000
a b c

300000 - number of sets a, b, c - elements of the set

My algorithm (dont judge about the code):

#include <iostream>

using namespace std;
int min_replacements(int n, int *ds, int *ps, int *rs);
int max(int a, int b, int c);
bool ot(int a, int b, int c);
bool ooo(int a, int b, int c);
bool to(int a, int b, int c);
int main()
{
    int n = 0;
    cin >> n;
    int *ds, *ps, *rs;
    ds = new int[n];
    ps = new int[n];
    rs = new int[n];
    int d{}, p{}, r{};
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d %d", &ds[i], &ps[i], &rs[i]);
        printf("%d", i);
    }
    int t = min_replacements(n, ds, ps, rs);
    printf("%d\n", t);
    delete[] ds;
    delete[] ps;
    delete[] rs;
}
bool ot(int a, int b, int c)
{
    return (a != 0 && b == 0 && c == 0);
}
bool ooo(int a, int b, int c)
{
    return (a == 0 && b != 0 && c == 0);
}
bool to(int a, int b, int c)
{
    return (a == 0 && b == 0 && c != 0);
}
int max(int a, int b, int c)
{
    int m = 0;
    if (a == b && c < a)
    {
        m = a;
    }
    if (b == c && a < b)
    {
        m = b;
    }
    if (a == c && b < c)
    {
        m = c;
    }
    if (b < a && c < a)
    {
        m = a;
    }
    if (a < b && c < b)
    {
        m = b;
    }
    if (a < c && b < c)
    {
        m = c;
    }
    if (a == b && b == c)
    {
        m = a;
    }
    return m;
}
int min_replacements(int n, int *ds, int *ps, int *rs)
{
    int t = 0;
    if (ds[0] == ps[0] && ps[0] == rs[0] && ds[0] == rs[0])
    {
        return (n + ps[0]) * rs[0];
    }
    bool loop = true;
    while (loop)
    {
        for (int i = 0; i < n - 1; ++i)
        {
            if (ot(*(ds + i), *(ps + i), *(rs + i)) || ooo(*(ds + i), *(ps + i), *(rs + i)) || to(*(ds + i), *(ps + i), *(rs + i)))
            {
                continue;
            }
            int m = max(*(ds + i), *(ps + i), *(rs + i));
            if (m == *(ds + i))
            {
                *(ps + i + 1) += *(ps + i);
                *(rs + i + 1) += *(rs + i);
                *(ps + i) = *(rs + i) = 0;
                t += 2;
            }
            if (m == *(ps + i))
            {
                *(ds + i + 1) += *(ds + i);
                *(rs + i + 1) += *(rs + i);
                *(ds + i) = *(rs + i) = 0;
                t += 2;
            }
            if (m == *(rs + i))
            {
                *(ds + i + 1) += *(ds + i);
                *(ps + i + 1) += *(ps + i);
                *(ps + i) = *(ds + i) = 0;
                t += 2;
            }
        }
        for (int i = 0; i < n; ++i)
        {
            if (ot(*(ds + i), *(ps + i), *(rs + i)) || ooo(*(ds + i), *(ps + i), *(rs + i)) || to(*(ds + i), *(ps + i), *(rs + i)))
            {
                loop = false;
            }
            else
            {
                loop = true;
            }
        }
        if (loop)
        {
            *ds += *(ds + n - 1);
            *ps += *(ps + n - 1);
            *rs += *(rs + n - 1);
            *(ds + n - 1) = *(ps + n - 1) = *(rs + n - 1) = 0;
            t -= 2;
        }
    }
    if (t == 0)
        return 0;
    return t + 1;
}

I used a cin in this algorithm Can you help me? Thank you so much.

I think `min_replacements` has the fault about your slowness — santo, Oct 29 '20 at 09:15
Removing the `printf("%d", i);` would probably be a good first step to reduce the time — UnholySheep, Oct 29 '20 at 09:15
Would you _please_ drop the habit of writing `*(ds + i)` and just write `ds[i]`? Thanks. — paddy, Oct 29 '20 at 09:16
@Peter I mean, it's a O(n^2) function. In the worst case the computation is O(300000^2) — santo, Oct 29 '20 at 09:17
What is the purpose of all this manual memory management? Use `std::vector ds(n);` etc. would make this a lot easier. Also, name your functions properly. It's extremely hard to read code with no comments when the function names are totally anonymous. — Ted Lyngmo, Oct 29 '20 at 09:18
Your `max` function looks ... odd. `std::max({a,b,c});` would probably be quicker. — Ted Lyngmo, Oct 29 '20 at 09:21
> scanf("%d %d %d", &ds[i], &ps[i], &rs[i]); You mean you used cin here? — balki, Oct 29 '20 at 09:21
I don't think the issue is `cin`, May be you need to use a better algorithm — balki, Oct 29 '20 at 09:26
I suggest you describe [by editing your question](https://stackoverflow.com/posts/64588022/edit) the exact problem that you're trying to solve. Clearly your algorithm is substandard, and it is written in a way that is not helpful to anyone who wants to understand what it's trying to achieve. It is far easier to help you if we know what the program is supposed to do. — paddy, Oct 29 '20 at 09:28
Also, give an example of a small input data set and the expected output. If I input `2 1 2 3 4 5 6` I'd expect it to return a value, but your code just keeps going in the loop. Clearly I entered an invalid sequence since you claim that your program is working for small data set. — Ted Lyngmo, Oct 29 '20 at 11:29

AVH · Accepted Answer · 2020-10-29T12:35:52.430

4

How do you know the std::cin part is the problem? Did you profile your code? If not, I suggest doing that, it's often surprising which part of the code is taking up most time. See e.g. How can I profile C++ code running on Linux?.

You're doing a lot of unnecessary work in various parts of the code. For example, your max function does at least 7 comparissons, and looks extremely error prone to write. You could simply replace the whole function by:

std::max({ a, b, c })

I would also take a look at your min_replacements function and see if it can be simplified. Unfortunately, you're using variable names which are super vague, so it's pretty much impossible to understand what the code should be doing. I suggest using much more descriptive variable names. That way the code will become much easier to reason about. The way it's currently written, there's a very good change even you yourself won't be able to make sense of it in a month's time.

Just glacing over the min_replacements function though, there's definitely a lot more work going on than necessary. E.g. the last for-loop:

   for (int i = 0; i < n; ++i)
    {
        if (ot(*(ds + i), *(ps + i), *(rs + i)) || ooo(*(ds + i), *(ps + i), *(rs + i)) || to(*(ds + i), *(ps + i), *(rs + i)))
        {
            loop = false;
        }
        else
        {
            loop = true;
        }
    }

Each loop iterator sets the loop variable. Assuming this code is correct, you don't need the loop at all, just do the check only once for i = n - 1. That's already O(n) changed to O(1).

edited Oct 29 '20 at 12:35

answered Oct 29 '20 at 09:22

AVH

11,349
4
34
43

1. This code was written on Windows 2. I testes this code for small sets of data, for example 1000 sets of numbers or 5 sets of various numbers and its time of execution is very good. I only have problem with fetching a big amount of data – Oct 29 '20 at 09:34
1

@Peter Fine, but the advice given in this answer still applies. Although you said don't judge the code, it the code that is the problem, not your single use of cin (which is trivially replaced anyway). Above all if you want to improve the speed of your code you need to start doing some timings. There's no simple generally applicable way to make code go faster. Otherwise we'd all do it. – john Oct 29 '20 at 09:41
2

@Peter I don't know what that's supposed to mean. Clearly the performance is not good for a big amount of data. I'm trying to give you hints on how to improve the performance. In fact, I'm telling you you can throw out one of the two for-loops in your `min_replacements` function. What about my answer does not help you improve your code...? – AVH Oct 29 '20 at 09:41
1

@Peter Another important point is that if you want others to help with your code then don't use obscure variable names. Difficult to help with code that is hard to understand. – john Oct 29 '20 at 09:46
Sorry, i didn't looked to code and i remembered with cin. I would paste the exercise prompt, but it's in Polish and it will be hard to translate. – Oct 29 '20 at 09:51
You don't have to translate it. You have to _describe what the program is supposed to calculate_ in your own words. If you can't do that in a few simple sentences, then you have no hope of actually writing a program to do it. – paddy Oct 29 '20 at 09:56
1

@Peter The problem is not that we don't know the exercise prompt (although that would also help of course). It's that variable names like `ds`, `ps`, and `rs` don't mean anything. If you look at that code in 2 months time, you probably won't remember either what they mean. – AVH Oct 29 '20 at 09:57

Input 300 000 sets of numbers with cin or scanf

1 Answers1