CODEWITHSUNDEEP
java
cmcdaniels
cmcdaniels

Reputation: 145

Weighted Quick Union with Path Compression

According to the Princeton booksite, the Weighted Quick Union with Path Compression reduces the time of 10^9 union operations on 10^9 objects from a year to ~6 seconds. How is this number derived? When I run the following code at 10^8 operations I have a runtime of 61s. 

public class MainWQUPC{
    public static void main(String[] args){
        int p, q; 
        Scanner s = new Scanner(System.in);

        long N = s.nextLong();

        WQUPC uf = new WQUPC((int) N);

        for(int x = 0; x < N; x++){
            p = (int) (Math.random() * N);
            q = (int) (Math.random() * N);

            if(!uf.connected(p, q))
                uf.union(p, q);
        }
    }
}

public class WQUPC{
    private int[] id;
    private int[] sz;

    public WQUPC(int N){
        id = new int[N];
        sz = new int[N];
        for(int i = 0; i < N; i++){
            id[i] = i;
            sz[i] = 1;
        }
    }

    int root(int i){
        while(i != id[i]){
            id[i] = id[id[i]];
            i = id[i];
        }

        return i;
    }

    boolean connected(int p, int q){
        return root(p) == root(q);
    }

    void union(int p, int q){
        int i = root(p);
        int j = root(q);

        if(sz[i] < sz[j]){          
            id[i] = j;
            sz[j] += sz[i];
        }else{
            id[j] = i;
            sz[i] += sz[j];
        }
    }   
}

Upvotes: 0

Views: 1330

Answers (1)

Kuchi
Kuchi

Reputation: 4674

You can't directly compare this since the runtime depends on many different factors mostly in this case on your CPU performance.

Let's say a year has about 31556952 seconds on average (60*60*24*365.2425) And with Path Compression it takes ~6 seconds

This means that the Quick Union with path Compression is about 5259492 (31556952/6) times faster than without.

So the number given just show how incredible good the performance boost is when you "just" improve the algorithm a bit.

Upvotes: 1

Related Questions