CS61B项目练习笔记(二)--Lab3

经验点:

• Stopwatch的使用
• 在类的两个实现之间执行比较测试。
• 随机调用类内部的方法。
• 在类的两个实现之间执行随机比较测试。
• 使用 IntelliJ 中的恢复按钮。
• 向断点添加条件。
• 创建异常断点。

Stopwatch库的使用

package timingtest;

import edu.princeton.cs.algs4.Stopwatch;

/**
 * Created by hug.
 */
public class StopwatchDemo {
    /** Computes the nth Fibonacci number using a slow naive recursive strategy.*/
    private static int fib(int n) {
        if (n < 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        Stopwatch sw = new Stopwatch();
        int fib41 = fib(41);
        double timeInSeconds = sw.elapsedTime();
        System.out.println("The 50th fibonacci number is " + fib41);
        System.out.println("Time taken to compute 41st fibonacci number: " + timeInSeconds + " seconds.");
    }
}

• import edu.princeton.cs.algs4.Stopwatch;导入库
• Stopwatch sw = new Stopwatch();开始计时
• double timeInSeconds = sw.elapsedTime();结束计时，返回时间

在类的两个实现之间执行比较测试。

测试代码的一种技术是进行“比较测试”。在这样的测试中，我们有两个相同类的实现。一个实现是已知的（或坚信的）是正确的，另一个正在开发中，尚未验证。

例如，我们提供了类 AListNoResizing 。此类不支持任何调整大小操作，只是具有 1000 的硬编码数组大小。这意味着它实际上没有用，因为它永远不能容纳超过 1000 个项目。但是，由于它非常简单，我们对它的工作充满信心。

相比之下，我们也提供了课程 BuggyAList 。此类具有一个基础数组，该数组会根据存储的数据量向上和向下调整大小。由于调整大小有点棘手，因此我们更加怀疑此类的正确性。顾名思义，它确实在某处有一个错误。本实验的其余部分的目标是找到此 bug。

package randomizedtest;
import edu.princeton.cs.algs4.StdRandom;
import org.junit.Test;
import static org.junit.Assert.*;

public class testThreeAddThreeRemove {
    AListNoResizing<Integer> list_1 = new AListNoResizing<>();
    BuggyAList<Integer> list_2 = new BuggyAList<>();
    @Test
    public void test_1() {
        list_1.addLast(4);
        list_1.addLast(5);
        list_1.addLast(6);
        list_2.addLast(4);
        list_2.addLast(5);
        list_2.addLast(6);
        assertEquals(list_1.removeLast(), list_2.removeLast());
        assertEquals(list_1.removeLast(), list_2.removeLast());
        assertEquals(list_1.removeLast(), list_2.removeLast());
    }
}

随机函数调用

原则上，可以仔细制作一组比较测试，最终找到错误。但是，另一种补充策略是使用随机方法，在该方法中，我们对两个实现进行随机调用，并使用 JUnit 方法来验证它们是否始终返回相同的值。

作为随机调用方法的函数示例，下面的代码随机调用 AList addLast 对象 AListNoResizing ， size 总共调用其中一个函数的 N 次。

package randomizedtest;

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

/**
 * Created by hug.
 */
public class TestBuggyAList {
  // YOUR TESTS HERE
  @Test
  public void randomizedTest() {
      AListNoResizing<Integer> correct = new AListNoResizing<>();

      int N = 5000;
      for (int i = 0; i < N; i += 1) {
          int operationNumber = StdRandom.uniform(0, 3);
          if (operationNumber == 0) {
              // addLast
              int randVal = StdRandom.uniform(0, 100);
              correct.addLast(randVal);
              System.out.println("addLast(" + randVal + ")");
          } else if (operationNumber == 1) {
              // size
              int size = correct.size();
              System.out.println("size: " + size);
          }
      }
  }
}

调试器功能-条件断点和恢复

1. 在显示 的 int operationNumber = StdRandom.uniform(0, 2); 行上设置断点。
2. 然后，使用 debug 选项在 IntelliJ 中的这一行停止。
3. 单击可视化工具，您将看到一个包含大量空值的数组，这些空值最终将存储要添加到列表中的数据。
4. 单击“单步执行”，您将看到 operationNumber 设置为 0 或 1。这是因为该 StdRandom.uniform(0, 2) 函数返回 [0， 2] 范围内的随机整数，即排除正确的参数。如果选择的数字为 0，则将在列表末尾添加一个随机数。如果选择的数字是 1，则将打印尺寸。
5. 单击调试器上的 resume 按钮（下面以黄色突出显示），我们的代码将再次遇到它，命中断点。
6. 尝试单击“恢复”几次，您将看到值开始填充数组。请注意，每次单击“恢复”时，代码都会运行（就像您多次按下单步执行一样），直到它再次返回到断点。
7. 我们还可以从可视化工具切换回能够查看打印语句的输出。为此， Debugger 请再次单击（旁边 Java Visualizer ）并继续单击恢复。在某些计算机上，您可能需要单击 Debugger 而不是 Console 。单击“恢复”的每个类型，都会看到另一个 print 语句，对应于对 addLast 或 size 的调用。
8. 现在让我们尝试一个条件断点。右键单击断点，您会看到一个弹出框，上面写着“条件：”。在框中，键入 L.size() == 12 。
9. 单击“恢复”，代码将一直运行，直到满足断点的条件，即大小为 12。尝试一下，然后单击可视化工具，您应该会看到大小现在为 12，数组中有 12 个项目。如果您不小心点击得太远，很遗憾，您必须重新启动测试。

这两个新功能（恢复和条件断点）对实验 3 的其余部分没有用。但是，它们可能会在将来的项目中派上用场，您需要在实验 4 中使用它们。此时应删除条件断点，以便它不会影响实验室的其余部分。

执行随机比较

public class TestBuggyAList {
  // YOUR TESTS HERE
  @Test
  public void randomizedTest() {
      AListNoResizing<Integer> correct = new AListNoResizing<>();
      BuggyAList<Integer> broken = new BuggyAList<>();

      int N = 5000;
      for (int i = 0; i < N; i += 1) {
          int operationNumber = StdRandom.uniform(0, 3);
          if (operationNumber == 0) {
              // addLast
              int randVal = StdRandom.uniform(0, 100);
              correct.addLast(randVal);
              broken.addLast(randVal);
              System.out.println("addLast(" + randVal + ")");
          } else if (operationNumber == 1) {
              // size
              int size = correct.size();
              System.out.println("size: " + size);
          } else if (operationNumber == 2 && correct.size() > 0) {
              int last_num = correct.getLast();
              assertEquals(correct.removeLast(), broken.removeLast());
              System.out.println("removeLast(" + last_num + ")");
          }
      }
  }
}

这就提出了一个关于随机测试的重要观点：如果你应用随机操作，并且这个错误相当模糊，你的随机操作序列可能无法检测到这个错误！有一些方法可以改进随机测试来避免这个问题，但这超出了我们课程的范围。

另一个注意事项：随机测试不应替代精心设计的单元测试！我个人通常倾向于在可能的情况下进行非随机测试，并将随机测试视为一种补充测试方法。有关此问题的辩论，请参阅此链接。

异常断点的使用

请单击“运行 -> 查看断点”。您应该会看到一个类似这样的窗口弹出窗口：

单击左侧显示“任何例外”的复选框，然后单击显示“条件：”的复选框，然后在窗口中输入：

this instanceof java.lang.ArrayIndexOutOfBoundsException

完成此操作后，断点窗口应如下所示：

单击“调试”按钮，代码应在异常即将发生时停止。单击可视化工具，并尝试找出代码崩溃的原因。现在可以开始真正的问题解决了！

注意：如果在未指定条件的情况下使用调试功能，则代码将停止在一些不同的神秘位置。确保在未指定条件的情况下，绝不会选中“任何异常”。这是因为启动 JUnit 测试的过程会生成一堆最终被忽略的异常。这远远超出了我们课程的范围。如果使用完执行断点，则应取消选中左上角的“Java Exceptions Breakpoints”框。

答案:

private void resize(int capacity) {
    Item[] a = (Item[]) new Object[capacity];
    for (int i = 0; i < size; i += 1) {
        a[i] = items[i];
    }
    items = a;
}
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;
    }

观察可知，是removeLast()方法在传入resize方法值的时候过小，导致新收缩的数组太小，没办法存储所有原数组的值，答案为resize(size / 4)改为resize(items.length / 4)