Возникли проблемы с взвешенными и невзвешенными быстрыми профсоюзными находками

Question

TLDR внизу

В школе мне поручили проект программирования по созданию модели перколяции, и я столкнулся с проблемой, которая привела меня в замешательство. Во-первых, мы должны были построить API для запуска перколяционного моделирования.

public class Percolation{
private int grid[][];
public int size;
QuickFindUF unionFind;
//WeightedQuickUnionUF unionFind;


public Percolation(int n)
{

    if(n<1){
        throw new IllegalArgumentException ("grid must be larger than 0");
    }

    grid=new int[n][n];
    size=n;
    unionFind=new QuickFindUF(size*size);
    //unionFind=new WeightedQuickUnionUF(size*size);
    //initially set all to blocked
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            grid[i][j]=1;
        }
    }
}

public void open(int x, int y)
{
    grid[x][y]=0;

            //Check below to see if you can
            //if you are not on the bottom row
            if(y>0)
            {
                if(grid[x][y]==0 && grid[x][y-1]==0){unionFind.union(x+y*size,x+(y-1)*size);}
            }
            //check to see to the right (x->)
            if(x<size-1){
                if(grid[x][y]==0 && grid[x+1][y]==0){unionFind.union(x+y*size,x+1+y*size);}
            }
            //check if can union to the left
            if(x>0)
            {
                if(grid[x][y]==0 && grid[x-1][y]==0){unionFind.union(x+y*size,x-1+y*size);}

            }
            //check for above 
            if(y<size-1){
                if(grid[x][y]==0 && grid[x][y+1]==0){unionFind.union(x+y*size,x+(y+1)*size);}
            }

}

public boolean isOpen(int x, int y)
{
    if(x>=size || y>=size){return false;}
    if(grid[x][y]==0){return true;}
    return false;
}

public boolean isFull(int x, int y)
{
    if(x>=size || y>=size){return false;}//if input is out of bounds


    for(int i=0;i<size;i++){
        if(unionFind.connected(x+y*size,i+((size-1)*size)))
            return true;
    }


    return false;
}

public boolean percolates()
{
    for(int i=0;i<size;i++){
        for(int j=0;j<size;j++){
            if(unionFind.connected(i,(size-1)*size+j)){
                //System.out.println(i+" "+((size-1)*size+j));

                return true;
            }
        }
    }
    return false;
}
}

Теперь книга любезно предоставляет quickfindUF и WeightedQuickUnionUF. Все одноклассники, с которыми я разговаривал, получили ожидаемые результаты при синхронизации с классом PercolationStats, который нам поручили сделать, но мои результаты очень велики. Вот класс

class PercolationStats{

private Percolation perc;
private double[] array;
private int expCount;

public PercolationStats(int gridSize, int numOfExperiments){
    if(gridSize <= 0 || numOfExperiments <=0)
        throw new IllegalArgumentException("gridSize and numOfExperiments needs to be more than 0");
    array=new double[numOfExperiments];
    expCount=numOfExperiments;

    for(int i=0;i<numOfExperiments;i++){
        perc=new Percolation(gridSize);
        int count=0;
        while(!perc.percolates()){
            int x=StdRandom.uniform(gridSize),y=StdRandom.uniform(gridSize);
            if(!perc.isOpen(x,y)){
                perc.open(x,y);
                count++;
            }
        }
        array[i]=(double) count/(gridSize*gridSize);
    }

}

public double mean(){
    return StdStats.mean(array);
}

public double stddev(){
    return StdStats.stddev(array);
}

public double confidenceLo(){
    return mean() - ((1.96 * stddev()) / Math.sqrt(expCount));
}

public double confidenceHi(){
    return mean()+((1.96 * stddev()) / Math.sqrt(expCount));
}

public static void main(String[] args){
    Stopwatch timer=new Stopwatch();
    PercolationStats percStats=new PercolationStats(200,100);
    System.out.println("mean: "+ percStats.mean() +"stddev: "+percStats.stddev()+" confidence Lo: "+percStats.confidenceLo()+" confidence hi: "+percStats.confidenceHi());
    System.out.println(timer.elapsedTime());
    percStats=new PercolationStats(200,100);
    System.out.println("mean: "+ percStats.mean() +"stddev: "+percStats.stddev()+" confidence Lo: "+percStats.confidenceLo()+" confidence hi: "+percStats.confidenceHi());
    percStats=new PercolationStats(2,100000);
    System.out.println("mean: "+ percStats.mean() +"stddev: "+percStats.stddev()+" confidence Lo: "+percStats.confidenceLo()+" confidence hi: "+percStats.confidenceHi());
}

}

Когда я запускаю это с QuickFindUF на percStats(200 100), это занимает у меня около 7 секунд, а если я запускаю его на тех же 200 100 с WeightedQuickUnionUF, это занимает около 50+ секунд?? Я был совершенно уверен, что взвешенное быстрое объединение должно было быть быстрее, и дело не только в том, что мне не повезло с моим ужасным генератором случайных чисел в худшем случае. Я запускал его довольно много раз, и все же результаты были примерно одинаковыми, и я довольно долго смотрел на код и не могу понять, почему мой код настолько неправильный...

TLDR

Правильные результаты, неправильные сроки. Более медленный API по некоторым причинам быстрее, и я не могу понять, почему. QuickFindUF быстрее, чем WeightedQuickUnionUF. (примерно в 7-8 раз быстрее). Что я делаю неправильно?

Answer 1

Хаха, я тупой Я видел в Интернете, что другие используют виртуальный топ, поэтому я добавил один, и теперь он отлично работает:P