目录页：我的algs4之旅
Union-Find是Algorithms, Part I第一周的第二部分。
该部分的编程作业是：编程作业: Percolation
其详细要求为：Programming Assignment 1: Percolation
据详细要求中所言，需要完成：
安装Java编程环境
此步详见：Java开发环境搭建完成Percolation数据结构
基于WeightedQuickUnionUF完成该数据结构，该数据结构用于后面蒙特卡罗模拟完成蒙特卡罗模拟所需的PercolationStats数据结构
17.4.21 星期五 首次提交 结果如下：
17.4.21首次提交作业结果
后面我会放上带注释的两个.java文件以及提交后的评价内容。以及此次提交的问题和改进思路。
Percolation.java完整文件内容如下：
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
//要使用WeightedQuickUnionUF数据结构
public class Percolation
{
private final int n;
//保存构造函数传入的n参数
private boolean[] isOpenSites;
//用boolean类型数组保存各个site的打开/关闭情况
private int numberOfOpenSites;
//打开的site总数
private WeightedQuickUnionUF percolationUF;
//一个UF对应一个Percolation，
//UF中的节点对应Percolation中的site，
//利用UF来判断site是否full等情况
public Percolation(int n)
{
//依据要求，参数不当时抛出异常
if(n <= 0)
{
throw new IllegalArgumentException();
}
this.n = n;
isOpenSites = new boolean[n*n+1];
/*
对于原始数据类型boolean数组，
未初始化值则自动初始化为false。
为与WeightedQuickUnionUF中节点相对应，
多使用了一个，总数为n*n+1
即实际使用中isOpenSites[0]无实际意义
*/
numberOfOpenSites = 0;
percolationUF = new WeightedQuickUnionUF(n*n+2);
/*
多出的两个，第一个用于连接第一排，第二个用于连接最后一排
*/
}
/*
对于传入的二维坐标row和col，
转换为数组isOpenSites和percolationUF所需的一维坐标
以及依据题目要求判断传入参数是否合法
*/
private int index(int row, int col)
{
if((row >=1 && row <= n) && (col >=1 && col <= n))
{
return (row - 1) * n + col;
}
else
{
throw new IndexOutOfBoundsException();
}
}
//如果site(row, col)未打开，打开它
public void open(int row, int col)
{
//检查输入参数是否合法
int index = index(row, col);
//若site(row, col)未打开，打开它
if(isOpenSites[index] == false)
{
//如果整个系统只有一个site
if(n == 1)
{
isOpenSites[index] = true;
//将该site标记为打开
numberOfOpenSites++;
//打开site总数增加
//设置对应percolationUF节点的连接状态
percolationUF.union(0, index);
percolationUF.union(index, 2);
return;
}
//从这里开始，n至少为2，即系统至少2行
isOpenSites[index] = true;
//将该site标记为打开
numberOfOpenSites++;
//打开site总数增加
//设置对应percolationUF节点的连接状态
//若要开启第一行的site
if(row == 1)
{
percolationUF.union(0, index);
/*
第一行site所对应节点必须和第0节点连接
同样最后一行site所对应节点必须和第n*n+1节点连接
这样在判断系统是否渗透时，
只需比较第0节点和第n*n+1节点，
且第一排与最后一排各site无需与其左右site比较相连
*/
//如果该site下方的site已打开，连接这两个site
int underIndex = index(row+1, col);
if(isOpenSites[underIndex] == true)
{
percolationUF.union(index, underIndex);
}
}
//若开启最后一行的site
else if(row == n)
{
percolationUF.union(index, n*n+1);
/*理由同上*/
//如果该site上方的site已打开，连接这两个site
int upIndex = index(row-1, col);
if(isOpenSites[upIndex] == true)
{
percolationUF.union(index, upIndex);
}
}
//若开启中间行的site，且到此系统定为至少三行
else
{
/*若该site上方和下方的site是打开状态，则连接*/
int upIndex = index(row-1, col);
if(isOpenSites[upIndex] == true)
{
percolationUF.union(index, upIndex);
}
int underIndex = index(row+1, col);
if(isOpenSites[underIndex] == true)
{
percolationUF.union(index, underIndex);
}
/*
判断该site的左右site是否需要连接
对处于第一列和最后一列的site特别对待
*/
//若为第一列
if(col == 1)
{
//只需判断其右侧site是否需要连接
int rightIndex = index(row, col+1);
if(isOpenSites[rightIndex] == true)
{
percolationUF.union(index, rightIndex);
}
}
//若为最后一列
else if(col == n)
{
//只需判断其左侧site是否需要连接
int leftIndex = index(row, col-1);
if(isOpenSites[leftIndex] == true)
{
percolationUF.union(index, leftIndex);
}
}
//若为一行中处于中间列的site
else
{
//分别判断左右site是否需要连接
int rightIndex = index(row, col+1);
if(isOpenSites[rightIndex] == true)
{
percolationUF.union(index, rightIndex);
}
int leftIndex = index(row, col-1);
if(isOpenSites[leftIndex] == true)
{
percolationUF.union(index, leftIndex);
}
}
}
}
}
//返回site(row, col)是否打开
public boolean isOpen(int row, int col)
{
int index = index(row, col);
return isOpenSites[index];
}
//返回site(row, col)是否full，即是否被渗透
public boolean isFull(int row, int col)
{
int index = index(row, col);
return percolationUF.connected(0, index);
}
//返回已打开的site数
public int numberOfOpenSites()
{
return numberOfOpenSites;
}
//返回系统是否已渗透
public boolean percolates()
{
return percolationUF.connected(0, n*n+1);
}
//main不做要求
public static void main(String[] args)
{
}
}
PercolationStats.java完整文件内容如下：
import edu.princeton.cs.algs4.StdRandom;
//需要生成随机数
import edu.princeton.cs.algs4.StdStats;
//需要其中的一些统计方法
import edu.princeton.cs.algs4.StdOut;
//main中需要一些输出
import java.lang.Math;
//需要使用根号
import java.lang.Integer;
//向main()传参时，需要将String转为int
public class PercolationStats
{
private double[] thresholds;
//保存每个Percolation的threshold
private double mean;
//所有threshold的平均数
private double stddev;
//标准差
private double confidenceLo;
private double confidenceHi;
public PercolationStats(int n, int trials)
{
thresholds = new double[trials];
//初始化后默认值为0.0
//用computeThreshold()生成一个Percolation的threshold
//循环生成所需的trials个
for(int i = 0; i < trials; i++)
{
thresholds[i] = computeThreshold(n);
}
//计算平均数和标准差并保存
mean = StdStats.mean(thresholds);
stddev = StdStats.stddev(thresholds);
//依据提供的公式计算confidenceLo和confidenceHi
double tmp = (1.96 * stddev) / Math.sqrt(trials);
confidenceLo = mean - tmp;
confidenceHi = mean + tmp;
}
//计算Percolation的threshold
private double computeThreshold(int n)
{
//为每次计算生成全新percolation
Percolation percolation = new Percolation(n);
//当percolation还未渗透，随机挑选其中的一个site打开
while(!percolation.percolates())
{
//随机生成一个[0, n*n)的int型数
int randomInt = StdRandom.uniform(n*n);
percolation.open( (randomInt / n) + 1 , (randomInt % n) + 1 );
}
//到此percolation已渗透，计算threshold并返回
double numberOfOpenSites = percolation.numberOfOpenSites();
return numberOfOpenSites / (n*n);
}
public double mean()
{
return mean;
}
public double stddev()
{
return stddev;
}
public double confidenceLo()
{
return confidenceLo;
}
public double confidenceHi()
{
return confidenceHi;
}
//进行一些测试
public static void main(String[] args)
{
PercolationStats pclStats = new PercolationStats(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
StdOut.println("mean = " + pclStats.mean);
StdOut.println("stddev = " + pclStats.stddev);
StdOut.println("95% confidence interval = [" + pclStats.confidenceLo + ", " + pclStats.confidenceHi + "]");
}
}
评分反馈：
See the Assessment Guide for information on how to interpret this report.
ASSESSMENT SUMMARY
Compilation: PASSED
API: PASSED
Findbugs: FAILED (1 warning)
Checkstyle: FAILED (37 warnings)
Correctness: 22/26 tests passed
Memory: 8/8 tests passed
Timing: 9/9 tests passed
Aggregate score: 90.77%
[Compilation: 5%, API: 5%, Findbugs: 0%, Checkstyle: 0%, Correctness: 60%, Memory: 10%, Timing: 20%]
ASSESSMENT DETAILS
The following files were submitted:
----------------------------------
4.6K Apr 21 11:38 Percolation.java
2.1K Apr 21 11:38 PercolationStats.java
********************************************************************************
* COMPILING
********************************************************************************
% javac Percolation.java
*-----------------------------------------------------------
% javac PercolationStats.java
*-----------------------------------------------------------
================================================================
Checking the APIs of your programs.
*-----------------------------------------------------------
Percolation:
PercolationStats:
================================================================
********************************************************************************
* CHECKING STYLE AND COMMON BUG PATTERNS
********************************************************************************
% findbugs *.class
*-----------------------------------------------------------
L D UC_USELESS_CONDITION UC: The condition 'this.n != 1' always produces the same result. Either something else was meant or the condition can be removed. At Percolation.java:[line 63]
Warnings generated: 1
================================================================
% checkstyle *.java
*-----------------------------------------------------------
Percolation.java:12:11: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:26:11: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:26:19: '>=' is not followed by whitespace. [WhitespaceAround]
Percolation.java:26:44: '>=' is not followed by whitespace. [WhitespaceAround]
Percolation.java:43:11: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:43:31: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:45:15: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:60:15: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:63:19: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:66:23: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:66:48: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:73:20: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:76:19: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:79:23: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:79:45: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:89:19: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:89:41: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:94:19: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:94:44: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:100:19: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:103:23: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:103:48: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:109:24: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:112:23: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:112:47: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:120:23: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:120:48: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:125:23: 'if' is not followed by whitespace. [WhitespaceAfter]
Percolation.java:125:47: Boolean expression can be simplified, e.g., use 'if (!isEmpty)' instead of 'if (isEmpty == false)'. [SimplifyBooleanExpression]
Percolation.java:135:7: '//' or '/*' is not followed by whitespace. [IllegalTokenText]
PercolationStats.java:4:1: Unnecessary import statement for 'java.lang.Math' because it is from the package 'java.lang'. [RedundantImport]
PercolationStats.java:5:1: Unnecessary import statement for 'java.lang.Integer' because it is from the package 'java.lang'. [RedundantImport]
PercolationStats.java:19:12: 'for' is not followed by whitespace. [WhitespaceAfter]
PercolationStats.java:38:14: 'while' is not followed by whitespace. [WhitespaceAfter]
PercolationStats.java:42:30: '(' is followed by whitespace. [ParenPad]
PercolationStats.java:42:50: ',' is preceded with whitespace. [NoWhitespaceBefore]
PercolationStats.java:42:71: ')' is preceded with whitespace. [ParenPad]
Checkstyle ends with 37 errors.
================================================================
********************************************************************************
* TESTING CORRECTNESS
********************************************************************************
Testing correctness of Percolation
*-----------------------------------------------------------
Running 15 total tests.
Tests 1 through 8 create a Percolation object using your code, then repeatedly
open sites by calling open(). After each call to open(), we check the return
values of isOpen(), percolates(), numberOfOpenSites(), and isFull() in that order.
Except as noted, a site is opened at most once.
Test 1: open predetermined list of sites using file inputs
* filename = input6.txt
* filename = input8.txt
* filename = input8-no.txt
* filename = input10-no.txt
* filename = greeting57.txt
* filename = heart25.txt
==> passed
Test 2: open random sites until just before system percolates
* n = 3
* n = 5
* n = 10
* n = 10
* n = 20
* n = 20
* n = 50
* n = 50
==> passed
Test 3: open predetermined sites for n = 1 and n = 2
* filename = input1.txt
* filename = input1-no.txt
* filename = input2.txt
* filename = input2-no.txt
==> passed
Test 4: check for backwash with predetermined sites
* filename = input20.txt
- isFull(18, 1) returns wrong value [after 231 sites opened]
- student = true
- reference = false
- failed after call 231 to isOpen()
* filename = input10.txt
- isFull(9, 1) returns wrong value [after 56 sites opened]
- student = true
- reference = false
- failed after call 56 to isOpen()
* filename = input50.txt
- isFull(22, 28) returns wrong value [after 1412 sites opened]
- student = true
- reference = false
- failed after call 1412 to isOpen()
* filename = jerry47.txt
- isFull(11, 47) returns wrong value [after 1076 sites opened]
- student = true
- reference = false
- failed after call 1076 to isOpen()
==> FAILED
Test 5: check for backwash with predetermined sites that have
multiple percolating paths
* filename = input3.txt
- isFull(3, 1) returns wrong value [after 4 sites opened]
- student = true
- reference = false
- failed after call 4 to isOpen()
* filename = input4.txt
- isFull(4, 4) returns wrong value [after 7 sites opened]
- student = true
- reference = false
- failed after call 7 to isOpen()
* filename = input7.txt
- isFull(6, 1) returns wrong value [after 12 sites opened]
- student = true
- reference = false
- failed after call 12 to isOpen()
==> FAILED
Test 6: open predetermined sites with long percolating path
* filename = snake13.txt
* filename = snake101.txt
==> passed
Test 7: open every site
* filename = input5.txt
==> passed
Test 8: open random sites until just before system percolates,
allowing open() to be called on a site more than once
* n = 3
* n = 5
* n = 10
* n = 10
* n = 20
* n = 20
* n = 50
* n = 50
==> passed
Test 9: check that IndexOutOfBoundsException is thrown if (col, row) is out of bounds
* n = 10, (col, row) = (0, 6)
* n = 10, (col, row) = (12, 6)
* n = 10, (col, row) = (11, 6)
* n = 10, (col, row) = (6, 0)
* n = 10, (col, row) = (6, 12)
* n = 10, (col, row) = (6, 11)
==> passed
Test 10: check that IllegalArgumentException is thrown if n <= 0 in constructor
* n = -10
* n = -1
* n = 0
==> passed
Test 11: create multiple Percolation objects at the same time
(to make sure you didn't store data in static variables)
==> passed
Test 12: open predetermined list of sites using file inputs,
but change the order in which methods are called
* filename = input8.txt; order = isFull(), isOpen(), percolates()
* filename = input8.txt; order = isFull(), percolates(), isOpen()
* filename = input8.txt; order = isOpen(), isFull(), percolates()
* filename = input8.txt; order = isOpen(), percolates(), isFull()
* filename = input8.txt; order = percolates(), isOpen(), isFull()
* filename = input8.txt; order = percolates(), isFull(), isOpen()
==> passed
Test 13: call all methods in random order until just before system percolates
* n = 3
* n = 5
* n = 7
* n = 10
* n = 20
* n = 50
==> passed
Test 14: call all methods in random order until almost all sites are open,
but with inputs not prone to backwash
* n = 3
* n = 5
* n = 7
* n = 10
* n = 20
* n = 50
==> passed
Test 15: call all methods in random order until all sites are open,
allowing open() to be called on a site more than once
(these inputs are prone to backwash)
* n = 3
- isFull(3, 3) returns wrong value [after 7 sites opened]
- student = true
- reference = false
- failed on trial 17 of 40
* n = 5
- isFull(5, 5) returns wrong value [after 15 sites opened]
- student = true
- reference = false
- failed on trial 1 of 20
* n = 7
- isFull(7, 7) returns wrong value [after 21 sites opened]
- student = true
- reference = false
- failed on trial 2 of 10
* n = 10
- isFull(9, 10) returns wrong value [after 65 sites opened]
- student = true
- reference = false
- failed on trial 1 of 5
* n = 20
- isFull(14, 13) returns wrong value [after 223 sites opened]
- student = true
- reference = false
- failed on trial 1 of 2
* n = 50
- isFull(41, 14) returns wrong value [after 1481 sites opened]
- student = true
- reference = false
- failed on trial 1 of 1
==> FAILED
Total: 12/15 tests passed!
================================================================
********************************************************************************
* TESTING CORRECTNESS (substituting reference Percolation)
********************************************************************************
Testing correctness of PercolationStats
*-----------------------------------------------------------
Running 11 total tests.
Test 1: Test that PercolationStats creates trials Percolation objects, each of size n-by-n
* n = 20, trials = 10
* n = 50, trials = 20
* n = 100, trials = 50
* n = 64, trials = 150
==> passed
Test 2: Test that PercolationStats calls open() until system percolates
* n = 20, trials = 10
* n = 50, trials = 20
* n = 100, trials = 50
* n = 64, trials = 150
==> passed
Test 3: Test that PercolationStats does not call open() after system percolates
* n = 20, trials = 10
* n = 50, trials = 20
* n = 100, trials = 50
* n = 64, trials = 150
==> passed
Test 4: Test that mean() is consistent with the number of intercepted calls to open()
on blocked sites
* n = 20, trials = 10
* n = 50, trials = 20
* n = 100, trials = 50
* n = 64, trials = 150
==> passed
Test 5: Test that stddev() is consistent with the number of intercepted calls to open()
on blocked sites
* n = 20, trials = 10
* n = 50, trials = 20
* n = 100, trials = 50
* n = 64, trials = 150
==> passed
Test 6: Test that confidenceLo() and confidenceHigh() are consistent with mean() and stddev()
* n = 20, trials = 10
* n = 50, trials = 20
* n = 100, trials = 50
* n = 64, trials = 150
==> passed
Test 7: Check whether exception is thrown if either n or trials is out of bounds
* n = -23, trials = 42
* n = 23, trials = 0
- java.lang.IllegalArgumentException not thrown for PercolationStats()
* n = -42, trials = 0
- java.lang.IllegalArgumentException not thrown for PercolationStats()
* n = 42, trials = -1
- java.lang.IllegalArgumentException not thrown for PercolationStats()
==> FAILED
Test 8: Create two PercolationStats objects at the same time and check mean()
(to make sure you didn't store data in static variables)
* n1 = 50, trials1 = 10, n2 = 50, trials2 = 5
* n1 = 50, trials1 = 5, n2 = 50, trials2 = 10
* n1 = 50, trials1 = 10, n2 = 25, trials2 = 10
* n1 = 25, trials1 = 10, n2 = 50, trials2 = 10
* n1 = 50, trials1 = 10, n2 = 15, trials2 = 100
* n1 = 15, trials1 = 100, n2 = 50, trials2 = 10
==> passed
Test 9: Check that the methods return the same value, regardless of
the order in which they are called
* n = 20, trials = 10
* n = 50, trials = 20
* n = 100, trials = 50
* n = 64, trials = 150
==> passed
Test 10: Check for any calls to StdRandom.setSeed()
* n = 20, trials = 10
* n = 20, trials = 10
* n = 40, trials = 10
* n = 80, trials = 10
==> passed
Test 11: Check distribution of number of sites opened until percolation
* n = 2, trials = 100000
* n = 3, trials = 100000
* n = 4, trials = 100000
==> passed
Total: 10/11 tests passed!
================================================================
********************************************************************************
* MEMORY (substituting reference Percolation)
********************************************************************************
Computing memory of PercolationStats
*-----------------------------------------------------------
Running 4 total tests.
Test 1a-1d: Memory usage as a function of trials for n = 100
(max allowed: 8*trials + 128 bytes)
trials bytes
--------------------------------------------
=> passed 16 208
=> passed 32 336
=> passed 64 592
=> passed 128 1104
==> 4/4 tests passed
Estimated student memory = 8.00 T + 80.00 (R^2 = 1.000)
Total: 4/4 tests passed!
================================================================
********************************************************************************
* MEMORY
********************************************************************************
Computing 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 37040
=> passed 256 590000
=> passed 512 2359472
=> passed 1024 9437360
==> 4/4 tests passed
Estimated student memory = 9.00 n^2 + 0.00 n + 176.00 (R^2 = 1.000)
Test 2 (bonus): Check that total memory <= 11 n^2 + 128 n + 1024 bytes
- bonus available only if solution passes backwash correctness test
==> FAILED
Total: 4/4 tests passed!
================================================================
********************************************************************************
* TIMING
********************************************************************************
Timing Percolation
*-----------------------------------------------------------
Running 9 total tests.
Test 1a-1e: Create an n-by-n percolation system; open sites at random until
the system percolates. Count calls to connected(), union() and
find() in WeightedQuickUnionUF.
2 * connected()
n seconds union() + find() constructor
---------------------------------------------------------------------------------------------
=> passed 8 0.00 53 250 1
=> passed 32 0.00 732 3092 1
=> passed 128 0.01 11205 48006 1
=> passed 512 0.04 184995 785726 1
=> passed 1024 0.10 728233 3100964 1
==> 5/5 tests passed
Running time in seconds depends on the machine on which the script runs,
and varies each time that you submit. If one of the values in the table
violates the performance limits, the factor by which you failed the test
appears in parentheses. For example, (9.6x) in the union() column
indicates that it uses 9.6x too many calls.
Tests 2a-2d: Check whether number of calls to union(), connected(), and find()
is a constant per call to open(), isFull(), and percolates().
The table shows the maximum number of union(), connected(), and
find() calls made during a single call to open(), isFull(), and
percolates().
n per open() per isOpen() per isFull() per percolates()
---------------------------------------------------------------------------------------------
=> passed 32 4 0 1 1
=> passed 128 4 0 1 1
=> passed 512 4 0 1 1
=> passed 1024 4 0 1 1
==> 4/4 tests passed
Total: 9/9 tests passed!
================================================================
查看评价，这次的提交主要是一个问题没有考虑到
- 在Percolation中没有预防回流（backwash）
解决思路：
回流问题通过创建两个WeightedQuickUnionUF来解决
一个最后一行各节点仍与额外的最后一个节点相连，提供是否渗透（percolates()）结果的快速反馈（和原有的一样）；
另一个最后没有额外的新增节点，提供是否充满（isFull()）的正确快速反馈至于小问题：在PercolationStats构造函数中没有抛出非法参数的异常，加个判断抛出即可。
更正后：
Pass
