unit-testing - (家庭作业)单元测试具有随机行为的类而不能模拟 RNG

Question

我正在学习 Coursera 的算法，第一部分类(class)。我必须使用以下 API 创建一个 RandomizedQueue:

public class RandomizedQueue<Item> implements Iterable<Item> {
   public RandomizedQueue()                 // construct an empty randomized queue
   public boolean isEmpty()                 // is the queue empty?
   public int size()                        // return the number of items on the queue
   public void enqueue(Item item)           // add the item
   public Item dequeue()                    // delete and return a random item
   public Item sample()                     // return (but do not delete) a random item
   public Iterator<Item> iterator()         // return an independent iterator over items in random order
   public static void main(String[] args)   // unit testing
}

问题:如果我不能创建一个模拟 RNG 来传递到结构中(因为我不允许更改 API)并且我不想测试私有(private)方法，如何我要测试这个结构的随机行为吗？

我尝试过的

我曾尝试将我期望的结果视为概率问题。因此，例如，我将运行以下伪代码测试 10,000 次:

create new RandomizedQueue
enqueue 100 items (e.g. integers 0 - 99)
deque 1 item

然后我可以测试这 100 个项目中每个项目的出列频率是否在某个置信区间内(基于二项分布)。

Answer 1

有些人可能会称之为作弊，但我会 beg to differ .

---

单元测试的重点是验证系统的行为。因此，如果测试要有用，它必须是确定性的。否则，您偶尔会得到假阴性结果，从而降低测试的完整性。 (“哦，如果那个测试失败也没关系。它有时会发生......”)

考虑到这一点，如果您没有不能修改 API 的限制会怎样？如果您有自己的想法，您将如何实现和测试您的类？首先创建那个 实现。您可以将此类设计为完全确定性的。

在你有一个工作和测试类之后，简单地实现RandomizedQueue<Item> as an adapter到你的类(class)。

---

例子

考虑以下设置:

public interface RandomNumberGenerator {
    int GetRandomInt();
}

// Identical to RandomizedQueue<T>, except takes a RandomNumberGenerator as a dependency
public class MyRandomizedQueue<Item> implements Iterable<Item> {

    public MyRandomizedQueue(RandomNumberGenerator generator) {
    ...
}

您的测试可以为 SUT 提供伪造的 RandomNumberGenerator并完全控制任何方法的预期结果。

在实际RandomizedQueue<T>实现，您将使用真实 RandomNumberGenerator 实例化您的测试类实现(例如，使用 java.util.Random 的实现)，将其存储为成员变量，并将方法调用转发给它。喜欢:

public Item dequeue() {
    return innerQueue.dequeue();
}