Question: How much do function calls affect running time?

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

I was trying to solve the following problem: 1106B - Lunar New Year and Food Ordering and I noticed something interesting. Below are two solutions:

Solution [1]

Submission Link: 49774574

Solution in plain text:

#include <bits/stdc++.h>

using namespace std;

typedef priority_queue< pair<int, int>, 
                        vector< pair<int, int> >, 
                        greater< pair<int, int> > > PQ;

int findCheapest(vector<int> a, PQ &pq) {
    while (!pq.empty() && a[pq.top().second] == 0)
        pq.pop();
    return (pq.empty()) ? 0 : pq.top().second;
}

void foodOrdering(int n, int m, vector<int> &a, vector<int> c) {
    int t, d, pos;
    long long cost;
    PQ pq;

    for (int i = 1; i <= n; i++)
        pq.push(make_pair(c[i], i));
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &t, &d);
        if (d <= a[t]) {
            a[t] -= d;
            cost = (long long) d * c[t];
            printf("%lld\n", cost);
        } else {
            d -= a[t];
            cost = (long long) a[t] * c[t];
            a[t] = 0;
            pos = findCheapest(a, pq);
            while (pos != 0 && d != 0) {
                if (d <= a[pos]) {
                    a[pos] -= d;
                    cost += (long long) d * c[pos];
                    d = 0;
                    printf("%lld\n", cost);
                } else {
                    d -= a[pos];
                    cost += (long long) a[pos] * c[pos];
                    a[pos] = 0;
                    pos = findCheapest(a, pq);
                }
            }
            if (d != 0)
                puts("0");
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<int> a(n + 1), c(n + 1);
    vector<long long> cost;
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    
    foodOrdering(n, m, a, c);
    return 0;
}

Solution [2]

Submission Link: 49774627

Solution in plain text:

#include <bits/stdc++.h>

using namespace std;

typedef priority_queue< pair<int, int>, 
                        vector< pair<int, int> >, 
                        greater< pair<int, int> > > PQ;

int findCheapest(vector<int> a, PQ &pq) {
    while (!pq.empty() && a[pq.top().second] == 0)
        pq.pop();
    return (pq.empty()) ? 0 : pq.top().second;
}

void foodOrdering(int n, int m, vector<int> &a, vector<int> c) {
    int t, d, pos;
    long long cost;
    PQ pq;

    for (int i = 1; i <= n; i++)
        pq.push(make_pair(c[i], i));
    
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &t, &d);
        if (d <= a[t]) {
            a[t] -= d;
            cost = (long long) d * c[t];
            printf("%lld\n", cost);
        } else {
            d -= a[t];
            cost = (long long) a[t] * c[t];
            a[t] = 0;
            while (!pq.empty() && a[pq.top().second] == 0)
                pq.pop();
            pos = (pq.empty()) ? 0 : pq.top().second;
            while (pos != 0 && d != 0) {
                if (d <= a[pos]) {
                    a[pos] -= d;
                    cost += (long long) d * c[pos];
                    d = 0;
                    printf("%lld\n", cost);
                } else {
                    d -= a[pos];
                    cost += (long long) a[pos] * c[pos];
                    a[pos] = 0;
                    while (!pq.empty() && a[pq.top().second] == 0)
                        pq.pop();
                    pos = (pq.empty()) ? 0 : pq.top().second;
                }
            }
            if (d != 0)
                puts("0");
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<int> a(n + 1), c(n + 1);
    vector<long long> cost;
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    
    foodOrdering(n, m, a, c);
    return 0;
}

Both the solutions are pretty much the same except Solution [1] uses a function call findCheapest and Solution [2] has the raw code replacing the function call. However, Solution [1] causes a TLE on test 9 taking 2000 ms whereas Solution [2] gets accepted and takes 140 ms. This means Solution [2] is atleast 14× faster than Solution [1].

At first I thought the priority_queue might be causing some issues. But I am passing the address as you can see, so the function should be modifying the same location.

I always thought function calls do not affect the running time much. Does this mean function calls play a big role in the running time? Could someone explain to me why this could have happened?

P.S. I am pretty much a noob so please feel free to correct anything and sorry for any stupid mistakes.

Комментарии (2)

Написать комментарий?

yassin_

6 лет назад, # |

+23

It's not directly the function calls, you are passing a by value, pass it by (const) reference instead (https://codeforces.net/contest/1106/submission/49777019)

→ Ответить

Mohammed-Shoaib

6 лет назад, # ^ |

Oh wow, I mean I know passing by value would mean it ends up creating a copy of the variable but I did not expect it to cause a TLE because of that. Thank you for your reply!

Блог пользователя Mohammed-Shoaib