什么是backwash?
如上图，使用一个WeightedQuickUnionUF对象，带有virtual top site和virtual bottom site。当渗透时，bottom row上可能存在连通virtual bottom site，但是没有连通virtual top site的site。比如上图红色圈内的site，调用isFull()时返回true，因为会通过红色箭头连通到virtual top site，这就产生了backwash问题。
可以使用两个WeightedQuickUnionUF对象避免backwash问题，其中一个只带有virtual top site。
存在的问题：使用两个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 1114424
=> passed 512 4456760
=> passed 1024 17826104
==> 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;
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;
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() + "]");
}
}
