0
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倍）。我究竟做錯了什麼？