今天时间有点紧只记了一下重点的，要注意的部分。
Timing Tests for List61B
Timing the getLast method of SLList
这里刚开始第一时间读完文档之后，没想懂测试时间的例子哪里来，苦思冥想许久没办法了，于是参考了一下别人的仓库，发现确实是自己手动编写的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static void timeAListConstruction() {
AList<Integer> Ns = new AList<>();
AList<Double> times = new AList<>();
AList<Integer> opCounts = new AList<>();
int temp = 1;
int N = 1000;
for (int i = 0; i < 8; i++) {
AList<Integer> tempAList = new AList<>();
Stopwatch sw = new Stopwatch();
for (int j = 0; j < N; j += 1) {
tempAList.addLast(temp);
}
double timeInSeconds = sw.elapsedTime();
Ns.addLast(N);
times.addLast(timeInSeconds);
opCounts.addLast(N);
N *= 2;
}
printTimingTable(Ns, times, opCounts);
}
|
后续两个都差不多的思路。
Randomized Comparison Tests
Conditional Breakpoints
IDEA中可以为断点设置触发条件，只有在满足条件的时候才会停下来。
Adding More Randomized Calls
这里添加了两个新的随机函数调用：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class randomizedTest {
@Test
public void randomizedTest() {
AListNoResizing<Integer> L = new AListNoResizing<>();
int N = 500;
for (int i = 0; i < N; i += 1) {
int operationNumber = StdRandom.uniform(0, 4);
if (operationNumber == 0) {
int randVal = StdRandom.uniform(0, 100);
L.addLast(randVal);
System.out.println("addLast(" + randVal + ")");
} else if (operationNumber == 1) {
int size = L.size();
System.out.println("size: " + size);
} else if (operationNumber == 2 && L.size() > 0) {
int Last = L.getLast();
System.out.println("LastItem: " + Last);
} else if (operationNumber == 3 && L.size() > 0) {
int Last = L.removeLast();
System.out.println("removeLastItem: " + Last);
}
}
}
}
|
Adding Randomized Comparisons
把每次随机操作之后的两个数组都比较一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| package randomizedtest;
import org.junit.Test;
import static org.junit.Assert.*;
import edu.princeton.cs.algs4.StdRandom;
public class randomizedTest {
@Test
public void randomizedTest() {
AListNoResizing<Integer> L1 = new AListNoResizing<>();
BuggyAList<Integer> L2 = new BuggyAList<>();
int N = 5000;
for (int i = 0; i < N; i += 1) {
int operationNumber = StdRandom.uniform(0, 4);
if (operationNumber == 0) {
int randVal = StdRandom.uniform(0, 100);
L1.addLast(randVal);
L2.addLast(randVal);
System.out.println("addLast(" + randVal + ")");
} else if (operationNumber == 1) {
int size1 = L1.size();
int size2 = L2.size();
System.out.println("size1: " + size1 + "\nsize2: " + size2);
} else if (operationNumber == 2 && L1.size() > 0) {
int Last1 = L1.getLast();
int Last2 = L2.getLast();
System.out.println("LastItem: " + Last1 + "\nLastItem: " + Last2);
} else if (operationNumber == 3 && L1.size() > 0) {
int Last1 = L1.removeLast();
int Last2 = L2.removeLast();
System.out.println("removeLastItem: " + Last1 + "\nremoveLastItem: " + Last2);
}
assertEquals(L1.size(), L2.size());
for (int j = 0; j < L1.size(); j += 1) {
assertEquals(L1.get(j), L2.get(j));
}
}
}
}
|
Running our Randomized Test
这里需要把N调大一些才能触发bug。改为N=5000。
Fixing the Bug and Execution Breakpoints
这里感觉是这个Lab里面的精华了。
由于每次bug触发之后的报错信息都类似于：
1
2
3
| java.lang.ArrayIndexOutOfBoundsException: Index 7 out of bounds for length 7
at randomizedtest.BuggyAList.resize(BuggyAList.java:31)
|
而且直接debug又不好找到问题所在，这里交给我们一个方式用来直接在bug处暂停:
点击Run -> View Breakpoints -> + -> Java Exception Breakpoints -> Any Exception
添加Conditions: this instanceof java.lang.ArrayIndexOutOfBoundsException
之后直接在测试函数中点击debug,就可以在bug触发时自动暂停了。
然后我们在通过观察visualizer窗口以及想象，就能够发现bug所在了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public Item removeLast() {
if ((size < items.length / 4) && (size > 4)) {
resize(size / 4);
}
Item x = getLast();
items[size - 1] = null;
size = size - 1;
return x;
}
|