CS61B 课程笔记（Project 1 Gold Autograding）

项目 1 Gold Autograding：自动评分系统详细实现笔记

1. 项目简介

目标：构建一个基本的自动评分系统，用于评估 ArrayDeque 的实现。
文件结构：
- StudentArrayDeque.java：包含错误的 ArrayDeque 实现。
- ArrayDequeSolution.java：包含正确的 ArrayDeque 实现。
- AssertEqualsStringDemo.java：展示如何使用 assertEquals。
- StudentArrayDequeLauncher.java：展示如何使用 StudentArrayDeque。

2. 获取项目文件

使用命令：
1
git pull skeleton master
以获取项目的基础文件。

3. 随机化测试原理

自动评分系统通过随机调用方法，比较学生实现与正确实现的输出，以找到差异。
使用 StdRandom 库来生成随机操作。

4. 任务 I：编写测试文件

创建 TestArrayDequeGold.java 文件。

引入必要的库：

1
2
3

import static org.junit.Assert.*;
import org.junit.Test;
import edu.princeton.cs.introcs.StdRandom; // 确保导入随机库

测试方法实现

编写一个方法随机调用 StudentArrayDeque 和 ArrayDequeSolution 直到它们的输出不一致：

@Test
public void testRandomizedDeque() {
    StudentArrayDeque<Integer> studentDeque = new StudentArrayDeque<>();
    ArrayDequeSolution<Integer> solutionDeque = new ArrayDequeSolution<>();
    StringBuilder operationSequence = new StringBuilder(); // 记录操作序列

    for (int i = 0; i < 1000; i++) {
        int operation = StdRandom.uniform(4); // 生成 0-3 之间的随机数
        int value = StdRandom.uniform(100); // 生成 0-99 之间的随机值

        switch (operation) {
            case 0: // addFirst
                studentDeque.addFirst(value);
                solutionDeque.addFirst(value);
                operationSequence.append("addFirst(").append(value).append(")\n");
                break;
            case 1: // addLast
                studentDeque.addLast(value);
                solutionDeque.addLast(value);
                operationSequence.append("addLast(").append(value).append(")\n");
                break;
            case 2: // removeFirst
                if (!studentDeque.isEmpty()) {
                    Integer studentResult = studentDeque.removeFirst();
                    Integer solutionResult = solutionDeque.removeFirst();
                    assertEquals("Failed on: " + operationSequence.toString(), solutionResult, studentResult);
                    operationSequence.append("removeFirst()\n");
                }
                break;
            case 3: // removeLast
                if (!studentDeque.isEmpty()) {
                    Integer studentResult = studentDeque.removeLast();
                    Integer solutionResult = solutionDeque.removeLast();
                    assertEquals("Failed on: " + operationSequence.toString(), solutionResult, studentResult);
                    operationSequence.append("removeLast()\n");
                }
                break;
        }
    }
}

这段代码是一个 JUnit 测试方法，名为 testRandomizedDeque，它的主要目的是对 StudentArrayDeque 类的实现进行随机化测试，以验证其与正确实现 ArrayDequeSolution 的行为是否一致。
初始化测试对象：
1
2
3
StudentArrayDeque<Integer> studentDeque = new StudentArrayDeque<>();
ArrayDequeSolution<Integer> solutionDeque = new ArrayDequeSolution<>();
StringBuilder operationSequence = new StringBuilder(); // 记录操作序列
创建两个 Deque 对象：一个是学生实现的（studentDeque），另一个是正确实现的（solutionDeque）。

使用 StringBuilder 记录所有执行的操作，以便在测试失败时输出具体的操作序列。
随机化操作循环：
1
2
3
for (int i = 0; i < 1000; i++) {
    int operation = StdRandom.uniform(4); // 生成 0-3 之间的随机数
    int value = StdRandom.uniform(100); // 生成 0-99 之间的随机值
进行 1000 次随机操作，每次随机选择一个操作（0 到 3）以及一个随机值（0 到 99）。
操作选择与执行：

通过 switch 语句，根据生成的随机数执行不同的操作：

addFirst（操作 0）：将随机值添加到 Deque 的前面，并记录操作。

addLast（操作 1）：将随机值添加到 Deque 的后面，并记录操作。

removeFirst（操作 2）：从 Deque 的前面移除一个元素。首先检查 Deque 是否为空，然后比较学生实现和正确实现的返回值，若不相同则触发断言错误，并输出操作序列。

removeLast（操作 3）：从 Deque 的后面移除一个元素，逻辑与 removeFirst 类似。
断言与错误报告：
1
assertEquals("Failed on: " + operationSequence.toString(), solutionResult, studentResult);
使用 assertEquals 断言比较学生实现与正确实现的返回值。

如果两者不一致，则输出相应的操作序列，帮助开发者快速定位问题。
这段代码通过随机调用 StudentArrayDeque 和 ArrayDequeSolution 的方法，模拟各种操作，检测其输出是否一致。通过这种方式，可以有效地发现学生实现中的潜在错误，从而进行更深入的调试与修复。这种随机化测试的方法提高了测试的覆盖率，能够发现许多边缘案例和潜在的逻辑错误。

5. 任务 II：输出有用的错误信息

使用 assertEquals(message, expected, actual) 方法来提供更有用的错误信息。

错误消息生成

在测试中，确保错误消息包含导致错误的操作序列：

1	assertEquals("Failed on: " + operationSequence.toString(), expectedValue, actualValue);

6. 提示和注意事项

避免比较整个 Deque：测试单个操作的返回值，避免使用全局比较方法。
防止 NullPointerException：在执行 removeFirst() 或 removeLast() 之前，确保 Deque 不为空。
使用 Integer 类型：确保使用 Integer 而不是 int 来处理返回值，避免拆箱导致的异常。

7. 常见问题解决

NullPointerExceptions：确保操作时不超出 Deque 的大小，使用 Integer 类型避免自动拆箱导致的错误。
模糊的错误消息：确保在错误消息中只包含导致失败的操作序列。

8. 最终完整示例

将上述内容整合为完整的 TestArrayDequeGold.java 文件：

import static org.junit.Assert.*;
import org.junit.Test;
import edu.princeton.cs.introcs.StdRandom;

public class TestArrayDequeGold {
    @Test
    public void testRandomizedDeque() {
        StudentArrayDeque<Integer> studentDeque = new StudentArrayDeque<>();
        ArrayDequeSolution<Integer> solutionDeque = new ArrayDequeSolution<>();
        StringBuilder operationSequence = new StringBuilder();

        for (int i = 0; i < 1000; i++) {
            int operation = StdRandom.uniform(4);
            int value = StdRandom.uniform(100);

            switch (operation) {
                case 0:
                    studentDeque.addFirst(value);
                    solutionDeque.addFirst(value);
                    operationSequence.append("addFirst(").append(value).append(")\n");
                    break;
                case 1:
                    studentDeque.addLast(value);
                    solutionDeque.addLast(value);
                    operationSequence.append("addLast(").append(value).append(")\n");
                    break;
                case 2:
                    if (!studentDeque.isEmpty()) {
                        Integer studentResult = studentDeque.removeFirst();
                        Integer solutionResult = solutionDeque.removeFirst();
                        assertEquals("Failed on: " + operationSequence.toString(), solutionResult, studentResult);
                        operationSequence.append("removeFirst()\n");
                    }
                    break;
                case 3:
                    if (!studentDeque.isEmpty()) {
                        Integer studentResult = studentDeque.removeLast();
                        Integer solutionResult = solutionDeque.removeLast();
                        assertEquals("Failed on: " + operationSequence.toString(), solutionResult, studentResult);
                        operationSequence.append("removeLast()\n");
                    }
                    break;
            }
        }
    }
}