什么是backwash?

讯享网

存在的问题：使用两个WeightedQuickUnionUF对象，存在内存占用问题。

 * MEMORY Analyzing memory of Percolation *----------------------------------------------------------- Running 4 total tests. Test 1a-1d: check that total memory <= 17 n^2 + 128 n + 1024 bytes n bytes -------------------------------------------- => passed 64 69944 => passed 256  => passed 512  => passed 1024  ==> 4/4 tests passed Estimated student memory = 17.00 n^2 + 0.00 n + 312.00 (R^2 = 1.000) Test 2 (bonus): check that total memory <= 11 n^2 + 128 n + 1024 bytes - failed memory test for n = 64 ==> FAILED Total: 4/4 tests passed! 

Percolation.java

讯享网 import edu.princeton.cs.algs4.WeightedQuickUnionUF; / * $ClassName Percolation * $Description TODO * $Author Freedom Wen * $Date 2022/8/7 22:47 */ public class Percolation { 
    private final int n; // n阶 private int openSiteNum; // 已经open的数量 private final boolean[] site; private final WeightedQuickUnionUF wquWithTopAndBottom; // 带两个虚拟结点的model private final WeightedQuickUnionUF wquWithTop; // 带两个虚拟结点的model private final int virtualTop; // 虚拟头部结点 private final int virtualBottom; // 虚拟底部结点 // creates n-by-n grid, with all sites initially blocked public Percolation(int n) { 
    if (n < 1) { 
    throw new IllegalArgumentException("param is not valid!"); } this.n = n; openSiteNum = 0; virtualTop = 0; // virtualBottom = n * n + 1; site = new boolean[n * n + 2]; site[virtualTop] = true; site[virtualBottom] = true; for (int i = 1; i < n*n; i++) { 
    site[i] = false; } wquWithTopAndBottom = new WeightedQuickUnionUF(n * n + 2); // with top and bottom wquWithTop = new WeightedQuickUnionUF(n * n + 1); // only with top } private void checkParams(int row, int col) { 
    if (row < 1 || row > n || col < 1 || col > n) { 
    throw new IllegalArgumentException("params are not valid!"); } } private int getSitePos(int row, int col) { 
    return (row - 1) * n + col; } // opens the site (row, col) if it is not open already public void open(int row, int col) { 
    checkParams(row, col); if (isOpen(row, col)) { 
    return; } int sitePos = getSitePos(row, col); site[sitePos] = true; openSiteNum++; // 每打开一个结点，openSiteNum+1 // 连通周围已经打开的结点 connectSite(row, col, sitePos); } private void connectSite(int row, int col, int sitePos) { 
    // 当row==1时，连接结点到virtualTop if (row == 1) { 
    wquWithTopAndBottom.union(sitePos, virtualTop); wquWithTop.union(sitePos, virtualTop); } // 当row==n时，连接结点到virtualBottom if (row == n) { 
    wquWithTopAndBottom.union(sitePos, virtualBottom); } if (row > 1 && isOpen(row - 1, col)) { 
    wquWithTopAndBottom.union(sitePos, getSitePos(row - 1, col)); wquWithTop.union(sitePos, getSitePos(row - 1, col)); } if (row < n && isOpen(row + 1, col)) { 
    wquWithTopAndBottom.union(sitePos, getSitePos(row + 1, col)); wquWithTop.union(sitePos, getSitePos(row + 1, col)); } if (col > 1 && isOpen(row, col - 1)) { 
    wquWithTopAndBottom.union(sitePos, getSitePos(row, col - 1)); wquWithTop.union(sitePos, getSitePos(row, col - 1)); } if (col < n && isOpen(row, col + 1)) { 
    wquWithTopAndBottom.union(sitePos, getSitePos(row, col + 1)); wquWithTop.union(sitePos, getSitePos(row, col + 1)); } } // is the site (row, col) open? public boolean isOpen(int row, int col) { 
    checkParams(row, col); int sitePos = getSitePos(row, col); return site[sitePos]; } // is the site (row, col) full? public boolean isFull(int row, int col) { 
    checkParams(row, col); return wquWithTop.find(getSitePos(row, col)) == wquWithTop.find(virtualTop); } // returns the number of open sites public int numberOfOpenSites() { 
    return openSiteNum; } // does the system percolate? public boolean percolates() { 
    return wquWithTopAndBottom.find(virtualTop) == wquWithTopAndBottom.find(virtualBottom); } // test client (optional) // public static void main(String[] args) { 
    // } } 

PercolationStats.java

 import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; import edu.princeton.cs.algs4.StdStats; / * $ClassName PercolationStats * $Description TODO * $Author Freedom Wen * $Date 2022/8/7 22:47 */ public class PercolationStats { 
    private static final double CONFIDENCE_95 = 1.96; private final double[] threshold; private final int trials; // perform independent trials on an n-by-n grid public PercolationStats(int n, int trials) { 
    if (n <= 0 || trials <= 0) { 
    throw new IllegalArgumentException("illegal args exception!"); } this.trials = trials; threshold = new double[trials]; for (int i = 0; i < trials; i++) { 
    Percolation percolation = new Percolation(n); while (!percolation.percolates()) { 
    int row = StdRandom.uniform(1, n + 1); int col = StdRandom.uniform(1, n + 1); percolation.open(row, col); } int openSites = percolation.numberOfOpenSites(); threshold[i] = (double) openSites / (n * n); } } // sample mean of percolation threshold public double mean() { 
    return StdStats.mean(threshold); } // sample standard deviation of percolation threshold public double stddev() { 
    return StdStats.stddev(threshold); } // low endpoint of 95% confidence interval public double confidenceLo() { 
    return mean() - CONFIDENCE_95 * stddev() / Math.sqrt(trials); } // high endpoint of 95% confidence interval public double confidenceHi() { 
    return mean() + CONFIDENCE_95 * stddev() / Math.sqrt(trials); } // test client (see below) public static void main(String[] args) { 
    PercolationStats percolationStats = new PercolationStats(Integer.parseInt(args[0]), Integer.parseInt(args[1])); StdOut.println("mean = " + percolationStats.mean()); StdOut.println("stddev = " + percolationStats.stddev()); StdOut.println("95% confidence interval = [" + percolationStats.confidenceLo() + "," + percolationStats.confidenceHi() + "]"); } }