CODEWITHSUNDEEP
c++algorithmrecursioniterationunion-find
shin
shin

Reputation: 681

Union-find method performance, iterative vs recursive

The problem is essentially that I found the recursive version of union-find method is faster than the iterative version.

// the union find method - recursive
int find(int k) {
    if(f[k] != k) f[k] = find(f[k]);
    return f[k];
}

// the union find method - iterative
int find(int k){
    while(f[k] != k) k = f[k];
    return f[k];
}

The context of the problem is here: good or bad balance.

The problem says we have a balance but we don't know it's good or bad. We have two kind of items in different weight, the same kind of item share the same weight. We index all the items to 1,2,3..n. And we randomly pick two of them and weigh on the balance. Each weighing result is represented in the form x,u,v, in which x is a bit indicator, 0 for balance, 1 for imbalance while u and v is the index of two items.

If the balance is bad, there will be contradictions, like if we have weighing results like:

0 1 2
1 1 2

item 1 and item 2 have different relation in two measures, so the balance is bad. I need to write a program to tell the earliest measure that can determine the balance is bad or the balance is good.

Basically, this is the variation of classic union-find problem. I expect iterative union-find method could lead to better performance, but I got Time Limit Exceeded on it while the recursive version got accepted. I want to ask why is this???

And this is the whole version of my algorithm.

#include <iostream>
#include <vector>

using namespace std;

#define N 10009

int n, m;
int x,u,v;
vector<int> f(2*N+1,0);

// iterative
int find(int k) {
    if(k!=f[k]) f[k] = find(f[k]);
    return f[k];
}

// recursive
// int find(int k) {
//     while(k!=f[k]) k=f[k];
//     return f[k];
// }

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int T; // T is number of test cases
    cin >> T;
    while(T--){
        // n is number of items, m is number of measurements
        cin >> n >> m;
        f.resize(2*n+1);
        for(int i = 0 ; i < 2*n+1; ++i){
            f[i] =i;
        }

        bool flag = false;
        int ans = 0;
        int r1, r2;
        for(int i = 1 ; i <= m ; ++i){
            // x is weighing result, u and v are item id.
            cin >> x >> u >> v;
            if(flag) continue;
            if(x == 0) {
                // two items are balance
                if(find(u) == find(v+n) || find(v) == find(u+n)){
                    flag = true;
                    ans = i;
                    continue;
                }
                r1 = find(u); r2 = find(v);f[r2] = r1;
                r1 = find(u+n); r2= find(v+n); f[r2] = r1;
            } else {
                // two items are imbalance
                if(find(u) == find(v)){
                    flag = true;
                    ans = i;
                    continue;
                }
                r1 = find(u); r2= find(v+n);f[r2]=r1;
                r1 = find(v); r2 = find(u+n);f[r2]=r1;
            }               
        }
        if(flag){
            cout << "sad" << endl;
            cout << ans << endl;
        } else
            cout << "great" << endl;
    }


    return 0;
}

A sample test case is 

2
4 5
0 1 3
1 2 4
0 1 4
0 3 4
0 1 2
2 2
0 1 2
1 1 2

Upvotes: 1

Views: 1319

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

The recursive and iterative versions do not do the same thing. The recursive version will update f[k] with the result, so that on ensuing calls with the same k value the answer will be found with at most one recursive call. The effect could be observed even on initial calls if one of the intermediate values was already found.

The iterative version does not update the f array, so subsequent calls will have to do the full loop until the answer is found.

It is also possible that the optimizer can inline some of the recursion so it isn't as recursive as it might first appear.

Upvotes: 3

Related Questions