Lab 3
约 4800 字大约 16 分钟
2025-05-10
Lab 3 介绍
在本实验中，你将为SLList和AList类创建一个计时测试。你还将为AList类的一个有缺陷的实现创建一个随机化比较测试。
在此过程中，我们还将探索三个新的调试器功能：条件断点、继续按钮 和 执行断点。
List61B的计时测试
在本实验的这一部分，请确保你打开的是 timingtest 包中的代码，而不是 randomizedtest 包中的代码。
对糟糕扩容策略的 AList 进行计时测试
正如在课堂上所讨论的，乘法扩容策略会带来快速的添加操作/良好的性能，而加法扩容策略会导致缓慢的添加操作/较差的性能。在本实验部分，我们将展示如何通过实际测试来证明这一点。在 timingtest 包中，我们提供了在课堂上创建的具有不良扩容策略的AList类，如下所示：
public void addLast(Item x) {
if (size == items.length) {
resize(size + 1);
}
items[size] = x;
size = size + 1;
}本实验这部分的目标是编写代码，统计使用上述AList方法创建不同大小的AList所需的时间。这个计时测试的输出大概如下：
Timing table for addLast
N time (s) # ops microsec/op
------------------------------------------------------------
1000 0.00 1000 0.20
2000 0.01 2000 0.20
4000 0.01 4000 1.20
8000 0.04 8000 4.30
16000 0.10 16000 10.00
32000 0.50 32000 49.70
64000 1.15 64000 114.80
128000 3.74 128000 374.30- 第一列
N表示数据结构的大小（包含多少个元素）。 - 第二列
time (s)表示完成所有操作所需的时间。 - 第三列
# ops表示在计时实验中对addLast的调用次数。 - 第四列
microsec/op表示平均每次调用addLast完成所需的微秒数。
请注意，对于这个实验，N 和 # ops 是多余的，因为调用128000次 addLast 的结果将导致 N 为128000。
这里需要注意的重要一点是，addLast 并非 “常数时间”。也就是说，每次调用 addLast 完成所需的时间会随着列表大小的变化而显著不同：列表较长时为374.30微秒，而列表较短时仅为0.20微秒。这基本上就是我们的自动评分器对 proj 1 中的 LinkedListDeque 和 ArrayDeque 类进行测试的方式，即我们要确保那些本应是常数时间的操作所花费的时间是固定的。
你可能会注意到，对于 N = 1000 和 N = 2000，每次addLast操作所花费的时间是相同的。这在计时测试中很常见。对于小的输入，结果不可靠有两个原因：运行时间的方差很大（这是由于缓存、进程切换、分支预测等问题导致的，如果你选修61C课程就会学到这些内容），并且我们的计时器精度（毫秒级）不足以区分 N = 1000 和 N = 2000 之间的差异。这甚至可能导致 N = 1000 的运行时间比 N = 2000 的运行时间还要长。因此，当我们进行实证计时测试时，我们希望关注大 N 时的行为，例如 N = 32000 与 N = 64000 的情况。
你可能还会注意到，从这个表格中获取的你机器上的时间，可能与上面所写的有很大差异。这没关系，只要总体趋势相同即可。在61C课程中，你会确切了解到为什么相同的代码在不同硬件上运行所需的时间会有极大差异。在61B课程（以及大多数基于理论的课程）中，我们只关注总体趋势，这会掩盖诸如你所使用的处理器类型等非理想因素。虽然思考 “总体趋势” 可能看似棘手，但在本课程后面我们会学习一种相关的形式化方法（渐近表示法）。目前，凭直觉就好！
既然你已经理解了上面的表格，在类 public void timeAListConstruction 中添加一个函数 public void timeAListConstruction，该函数为一个AList生成上面的表格。注意：如果你的电脑有点慢，你可能需要在64000处停止，而不是128000。确保在 TimeAList 类的main方法中添加对 timeAListConstruction 的函数调用。
为方便起见，我们提供了一个名为 printTimingTable(AList<Integer> Ns, AList<Double> times, AList<Integer> opCounts) 的方法，该方法将打印上述表格，其中 Ns 是第一列，times 是第二列，opCounts 是第三列。第四列 （microsec/op） 会自动为你计算。你的时间应以秒为单位。你应该使用 Stopwatch 类。有关示例，请参阅 stopwatchDemo。有趣的是，请注意我们使用的是与正在计时的数据结构（AList）相同的数据结构来存储计时数据！我们实现这一点的方法是使用该数据结构的许多不同对象；正在计时的实例与存储计时数据的实例对象不同。
对优秀扩容策略的 AList 进行计时测试
现在修改 AList 类，使扩容策略变为乘法而非加法，然后重新运行 timeAListConstruction。现在，即使对于 N = 128000，你的 AList 对象也应该几乎能瞬间构建完成，而且每次添加操作应该只需要几分之一微秒。
可选操作：尝试将最大N值增大，例如增大到1000万。你会发现每次添加操作所花费的时间保持不变。
可选：尝试使用不同的扩容因子进行实验，看看运行时间会如何变化。例如，如果你按1.01的因子进行扩容，你仍应该得到常数时间的 addLast 操作！请注意，要使用非整数因子，你需要将其转换为最接近的整数。例如，你可以使用 Math.round()。
public void addLast(Item x) {
if (size == items.length) {
resize((int) (size * 1.01));
}
items[size] = x;
size = size + 1;
}对 SLList 的 getLast 方法计时测试
上面，我们展示了如何对数据结构的构建过程进行计时。然而，有时我们感兴趣的是，一个方法的运行时间与已构建好的现有数据结构大小之间的依赖关系。
例如，在你的 LinkedListDeque 中，你应该实现快速的 addLast 操作…… 单个 addLast 操作必须是 “常数时间”，即执行时间不应依赖于双端队列的大小。
在实验的这一部分，我们将向你展示如何通过实证测试来判断一个方法的运行时间是否取决于数据结构的大小。
假设我们想计算 getLast 操作在 SLList 上每次操作的时间，并且想知道这个运行时间如何依赖于 N。要做到这一点，我们需要遵循以下步骤：
- 创建一个SLList。
- 向SLList中添加N个元素。
- 启动计时器。
- 对SLList执行M次getLast操作。
- 查看计时器。这将给出完成所有M次操作的总时间。
重要的是，我们要在步骤2完成之后再启动计时器。否则，计时测试会将构建数据结构的运行时间包含在内，而我们只关心 getLast 的运行时间如何取决于 SLList 的大小。
在 TimeSLList 类中，编辑函数 timeGetLast 以执行上述步骤，并生成一个类似于以下所示的表格：
Timing table for getLast
N time (s) # ops microsec/op
------------------------------------------------------------
1000 0.02 10000 1.70
2000 0.03 10000 3.10
4000 0.06 10000 6.20
8000 0.13 10000 12.50
16000 0.25 10000 25.00
32000 0.53 10000 52.80
64000 1.35 10000 135.30
128000 2.57 10000 257.30请注意，N 列和 # ops 列不再相同。这是因为无论列表的大小如何，我们调用 getLast 的次数始终相同，即对于上述过程的步骤4，M = 10000 。
请注意，这些操作的时间复杂度仍然不是常数时间！（如果你的结果表明这些操作是常数时间，确保你是在SLList上运行测试，而不是在AList上！）。这意味着随着列表规模的增大，getLast操作会变得更慢。在实际应用中，这将是一个严重的问题。例如，假设这个列表记录的是自动取款机（ATM）的交易记录，调用 getLast 操作是为了获取最新的交易以打印收据。每次使用ATM时，下一张收据的打印时间都会变长一点。最终，经过数月或数年，列表会变得非常大，以至于 getLast 操作会慢到无法使用。虽然这是一个人为构造的例子，但类似的问题在实际系统中也屡见不鲜！
出于这个原因，你在项目1中构建的 LinkedListDeque 需要具备与数据结构大小无关的运行时间。换句话说，最后一列将是某个近似恒定的值。
供思考的选做题：为什么 getLast 这么慢？你的 LinkedListDeque 有什么特别之处，能让getLast函数更快？
随机化比较测试
在本实验的这一部分，请确保你使用的是 randomizedtest 包中的代码，而不是 timingtest 包中的代码。
简单的随机测试
测试代码的一种技术是进行“比较测试”。在这样的测试中，我们有同一个类的两种实现。一种实现已知（或坚信）是正确的，而另一种正在开发中且尚未验证。
例如，我们提供了 AListNoResizing 类。这个类不支持任何调整大小的操作，并且简单地将数组大小硬编码为1000。这意味着它实际上没什么用，因为它永远无法容纳超过1000个元素。然而，由于它极其简单，我们非常确信它能正常工作。
相比之下，我们还提供了 BuggyAList 类。这个类有一个底层数组，它会根据存储的数据量进行上下调整大小。由于调整大小的操作要正确实现有点棘手，所以我们对这个类的正确性持怀疑态度。正如其名称所暗示的，它在某个地方确实存在一个错误。本实验接下来的目标就是找出这个错误。
我们先写一个JUnit测试练习来热身。编写一个名为 testThreeAddThreeRemove 的测试，向正确的和有缺陷的 AList 实现中添加相同的值，然后检查后续三次调用 removeLast 的结果是否相同。例如，你可以分别向两者 addLast 4，然后分别 addLast 5，再分别 addLast 6。接着，你从两者中 removeLast，并验证结果是否相等。然后，再次从两者中 removeLast，并检查结果是否相等。最后，你 removeLast 最后一个元素（即4），并验证结果是否相等。完成后，或者如果你遇到困难，可以点击此链接查看代码解决方案，但先尝试不看代码自己完成！
运行你的测试，你会发现它应该通过。这个测试还不够强大，无法识别BuggyAList中的错误。
随机函数调用
原则上，可以精心设计一组对比测试，最终找到这个程序缺陷。然而，另一种补充策略是采用随机化方法，即对两种实现进行随机调用，并使用JUnit方法来验证它们始终返回相同的值。
作为一个随机调用 AList 方法的函数示例，下面的代码会对一个 AListNoResizing 对象总共随机调用 N 次 addLast 和 size 中的一个方法。
AListNoResizing<Integer> L = new AListNoResizing<>();
int N = 500;
for (int i = 0; i < N; i += 1) {
int operationNumber = StdRandom.uniform(0, 2);
if (operationNumber == 0) {
// addLast
int randVal = StdRandom.uniform(0, 100);
L.addLast(randVal);
System.out.println("addLast(" + randVal + ")");
} else if (operationNumber == 1) {
// size
int size = L.size();
System.out.println("size: " + size);
}
}创建一个名为 randomizedTest() 的新JUnit测试，然后复制并粘贴上面的代码，你应该会看到类似这样的内容：
size: 0
addLast(68)
size: 1
size: 1
addLast(12)
addLast(19)
addLast(79)
...
size: 265条件断点
虽然今天这对查找错误没有帮助，但我们还是来介绍两个新的调试器功能：“恢复（resume）”和“条件断点”。
- 在写有
int operationNumber = StdRandom.uniform(0, 2);的这一行设置断点。 - 然后在IntelliJ中使用调试选项在此行暂停。如果你不记得如何使用调试选项，请参考实验2。
- 点击可视化工具，你会看到一个有很多很多空值的数组，这个数组最终会存储添加到我们列表中的数据。
- 点击
step over，你会看到operationNumber被设置为0或1。这是因为StdRandom.uniform(0, 2)函数返回一个范围在[0, 2)内的随机整数，也就是说不包括右侧参数。如果所选数字为0，那么一个随机数将被添加到列表末尾。如果所选数字为1，那么将打印大小。 - 点击调试器上的
resume按钮（如下以黄色突出显示），我们的代码将继续运行，直到再次遇到断点。 - 尝试点击几次
resume按钮，你会看到数组开始填充值。请注意，每次点击“继续”，代码都会运行（就好像你多次按下“单步跳过”一样），直到再次回到断点处。 - 我们也可以切换离开可视化工具，重新能够看到打印语句的输出。要做到这一点，再次点击
Debugger（在Java Visualizer旁边），然后继续点击“恢复”。在某些机器上，你可能需要点击Console而不是Debugger。每次点击“恢复”，你会看到另一条打印语句，对应于对addLast或size的调用。 - 现在让我们试试
条件断点。右键点击断点，你会看到弹出一个框，上面写着Condition:。在框中，输入L.size() == 12。 - 点击
resume，代码将运行，直到满足断点条件，即大小为12。试试看，然后点击可视化工具，你应该会看到大小现在是12，数组中有12个元素。如果你不小心点击过头了，很遗憾，你必须重新开始测试。
这两个新功能（ resume 和条件断点）在 Lab 3 的剩余部分不会有用。不过，它们可能在未来的项目中派上用场，并且在 Lab 4 中你需要用到它们。此时你应该移除条件断点，以免影响实验的其余部分。
添加更多随机调用
修改随机测试，使其现在有可能进行另外两个操作：getLast 和 removeLast。注意，你需要修改对 StdRandom.uniform 的调用，使其选取0到3之间的一个数字。
重要提示：仅当 L.size 大于0时，才应调用 getLast 和 removeLast！如果大小为0，这些方法将会崩溃。换句话说，如果大小为0，要有一个if语句来跳过对 getLast 或 removelast 的调用。
可选：添加这些方法后，在调用 removeLast 的那一行设置断点，然后使用调试器的单步跳过功能，确认 removeLast 似乎能正确运行。
添加随机比较
我们上面编写的代码仅调用我们已知正常的实现。修改代码，使得每次调用 AListNoResizing 方法时，也对 TestBuggyAList 中的相同方法进行调用。你的代码还应该比较每个有返回值的方法的返回值。
运行我们的随机测试
多次运行该测试。它可能通过，也可能失败。现在尝试将N增加到5000。它几乎每次都应该失败。
这就引出了关于随机测试的一个重要问题：如果你执行随机操作，而程序缺陷相当隐蔽，那么你的随机操作序列可能无法检测到该缺陷！有一些方法可以改进随机测试以避免这个问题，但这超出了我们课程的范围。
另一个注意事项：随机测试不应被用作精心设计的单元测试的替代品！就我个人而言，只要有可能，我通常倾向于非随机测试，并将随机测试视为一种补充测试方法。有关此问题的辩论，请参阅此主题帖。
修复程序错误和执行断点
既然我们有一个失败的测试，我们想弄清楚原因。
你会注意到，每次测试失败时，我们得到的消息类似于：
java.lang.ArrayIndexOutOfBoundsException: Index 7 out of bounds for length 7
at randomizedtest.BuggyAList.resize(BuggyAList.java:31)一种实现方法是在 BuggyAList.java 的第31行设置一个条件断点，条件为 i == items.length 。这样做效果很好，欢迎你尝试。
不过，我们将借此机会向你展示如何设置 “执行断点(Execution Breakpoint)”，以便在代码崩溃时，我们能够停止代码并直观地了解发生了什么。
为此，点击“Run -> View Breakpoints”。你应该会看到这样一个窗口弹出：
点击左侧写有“any exception”的复选框，然后点击写有“Condition:”的地方，并在窗口中准确输入：
this instanceof java.lang.ArrayIndexOutOfBoundsException完成此操作后，你的断点窗口应如下所示：
点击调试按钮，你的代码应该会在异常即将发生的那一刻停止。点击可视化工具，试着弄清楚代码崩溃的原因。现在真正的问题解决可以开始了！
在可视化工具窗口中有一系列线索，可确切表明问题所在。这是一个棘手且微妙的问题，但如果你采用系统的方法，应该能够找出问题。
一旦你找出了程序缺陷，就修复它。重新运行测试，以验证BuggyAList现在是否能正常运行。
注意：如果在未指定条件的情况下使用调试功能，你的代码会在一些莫名其妙的地方停止运行。确保在没有指定条件时，切勿勾选“任何异常”。这是因为启动JUnit测试的过程会产生一系列最终会被忽略的异常。这远远超出了我们课程的范围。如果你已使用完执行断点，应取消勾选左上角的“Java异常断点”框。
清理
最后：我们的JUnit测试中包含打印语句，用于创建所有随机调用的日志。虽然这在教学目的上很有用，但在实际测试中你并不希望这样，因为它只会生成一大堆无用的文本。请从你的JUnit测试中删除所有打印语句。
注意：通常，“log”随机测试所进行的函数调用比打印出来更有用。如需了解更多信息，请完成 proj 1 的附加学分作业。
总结
在本实验中，我们学习了如何：
- 通过实验测量构建数据结构所需的时间。
- 通过实验测量数据结构方法的运行时间与数据结构大小的关系。
- 对一个类的两种实现进行比较测试。
- 在类中随机调用方法。
- 对一个类的两种实现进行随机比较测试。
- 使用IntelliJ中的恢复按钮。
- 为断点添加条件。
- 创建执行断点。