《代码之美》（七）－－漂亮的测试

Alberto Savoia

通常，如果一段代码能优雅、简洁地完成了需要完成的功能，我们就认为这样的代码很漂亮。但测试代码的漂亮如何判定呢？Alberto认为：

1、测试因简单而漂亮。

2、测试因揭示出使代码更优雅，更可维护和更易测试的方法而漂亮。

3、测试因其深度和广度而漂亮。

这章我们来研究一下对二分查找法的测试。一个有bug的二分查找法的Java实现为：

public static int buggyBinarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low+high)/2;
        int midVal = a[mid];

        if (midVal < target)
            low = mid + 1;
        else
            high = mid - 1;
        else
            return mid;
    }
}

上面代码的bug隐藏在"int mid = (low+high)/2;"这行。如果low+high的值大于Integer.MAX_VALUE（2^31-1），它会溢出成为一个负数，这样使得 mid的值也成为一个负数。一种解决方法是用减法而不是加法来求中间值：

int mid = low + (high-low)/2;

另一种解决方法就是使用无符号位移运算：
int mid = (low+high) >>> 1;

这个bug的发现，警示着我们要懂得谦逊：哪怕是最简单的一段代码，要写正确也并非易事，更别提现实世界中的大段大段的复杂代码。

在改正掉整数溢出的bug后，二分查找法看起来已经是没问题了：

public static int binarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = low+high >>> 1;
        int midVal = a[mid];

        if (midVal < target)
            low = mid + 1;
        else
            high = mid - 1;
        else
            return mid;
    }
}

但它是否还会有其它的bug呢？通过整数溢出的bug的教训，我们并不能百分之百的确定。这时，我们就需要一个强壮的测试来建立我们信心。

Alberto决定使用JUnit来测试上面这段二分查找算法的代码，他的测试策略为：

1、从冒烟测试开始；

2、增加边界测试；

3、继续其他各种彻底的、全覆盖类型的测试；

4、最后，添加一些性能测试。

首先进行冒烟测试（smoke test）。这种测试用来确保代码在最基本的使用方式下能够正常工作。这是最基本的 测试，如果一个实现连冒烟测试都无法通过，就无需在进一步的测试了。通常我们应该在编写代码前就编写冒烟测试，这种开发方式称为测试驱动开发（test- driven development）。下面是二分查找的冒烟测试：

import static org.junit.Assert.*;
import org.junit.Test;

publid class BinarySearchSmokeTest {
    @Test
    public void smokeTestsForBinarySearch() {
        int[] arrayWith42 = new int[] {1, 4, 42, 55, 67, 87, 100, 245};
        assertEquals(2, Util.binarySearch(arrayWith42, 42);
        assertEquals(-1, Util.binarySearch(arrayWith42, 43);
    }
}

可以看到，这个测试真的很基本。通常情况下，我们可以写多个冒烟测试，并把它们组成一个测试组（suite），并在每次提交代码前运行它们。我们可能会有几千个冒烟测试，所以使每个冒烟测试都尽可能地小就是很重要的事了。

接下来，就可以进行边界测试（boundary test）了。这种测试用来处理极端或偏门的情况。
首先能想到的边界情况就是数组的大小，如果它是空的或只有一个元素会发生什么？下面的代码对这极端情况进行测试：

int[] testArray;

@Test
public void searchEmptyArray() {
    testArray = new int[] {};
    assertEquals(-1, Util.binarySearch(testArray, 42));
}

@Test
public void searchArrayOfSizeOne() {
    testArray = new int[] {42};
    assertEquals(0, Util.binarySearch(testArray, 42));
    assertEquals(-1, Util.binarySearch(testArray, 43));
}

我们还要考虑数组很大的数组，大到high+low可以发生溢出，这种情况下需要一个长度超过10亿的数组，会导致测试不容易进行。所以我们深入分析下， 确定我们现在需要确保的，其实只是中间值被正确的计算。为了使测试更容易进行，我们需要修改二分查找法的实现代码（的某行）：
int mid = calculateMidpoint(low, high);
其中calculateMidpoint的实现为：

static int calculateMidpint(int low, int high) {
    return (low + high) >>> 1;
}

这样我们就可以把测试精确定位到这个新增的函数里了。

不要为修改实现代码感到不安，因为这也应证了测试可以改进实现代码。通过上面的新增函数，程序可读性提高了。而由于编译器的优化，这个函数会被内联（inline），所以性能并不会有什么影响。
下面是对calculateMidpoint的测试：

@Test
public void calculateMidpointWithBoundaryValues() {
    assertEquals(0, calculateMidpoint(0, 1));
    assertEquals(1, calculateMidpoint(0, 2));
    assertEquals(1200000000, calculateMidpoint(1100000000, 130000000));
    assertEquals(Integer.MAX_VALUE-2, calculateMidpoint(Integer.MAX_VALUE-2, Integer.MAX_VALUE-1));
    assertEquals(Integer.MAX_VALUE-1, calculateMidpoint(Integer.MAX_VALUE-1, Integer.MAX_VALUE));
}

接下来要考虑的边界情况是元素为负数或0的情况：

@Test
public void testBoundaryCasesForItemsLocation() {
    testArray = new int[] {-324, -3, -1, 0, 42, 99, 101};
    assertEquals(0, Util.binarySearch(testArray, -324)); // first position
    assertEquals(3, Util.binarySearch(testArray, 0)); // middle position
    assertEquals(6, Util.binarySearch(testArray, 101)); // last position
}

另一种边界情况是最大和最小整数值：

public void testForMinAndMaxInteger() {
    testArray = new int[] {Integer.MIN_VALUE, -324, -3, -1, 0, 42, 99, 101, Integer.MAX_VALUE};
    assertEquals(0, Util.binarySearch(testArray, Integer.MIN_VALUE));
    assertEquals(8, Util.binarySearch(testArray, Integer.MAX_VALUE));
}

现在所有能想到的边界情况都被测试过了，我们对实现代码的已经非常有信心了。但是我们至今为止的测试过于具体，并没有对所有的输入进行一个全面的覆盖。这时我们需要随机测试，它包括：
1、一种能产生各种不同特征的、大数据量的输入集合的方法；
2、一组能通用于各种的输入集合的断言（assertion）。

下面先来实现第一种需求：

public int[] generateRandomSortedArray(int maxArraySize, int maxValue) {
    int arraySize = 1 + rand.nextInt(maxArraySize);
    int[] randomArray = new int[arraySize];
    for (int i = 0; i < arraySize; i++)
        randomArray[i] = rand.nextInt(maxValue);
    Array.sort(randomArray);
    return randomArray;
}

接下来要实现第二种需求，我们需要找到所有输入和（正确的）输出之间的共性。经过分析，我们可以得到下面的推论：

1、如果binarySearch(testArray, target)返回-1，那么testArray不包含元素target；

2、如果binarySearch(testArray, target)返回n(n>=0)，那么testArray包含元素target，且在数组中的位置是n。

根据上面的推论，我们就可以写测试代码了：

public class BinarySearchTestTheories {

Random rand;

@Before
public void initialize() {
    rand = new Random();
}

@Test
public void testTheories() {
    int maxArraySize = 1000;
    int maxValue = 1000;
    int experiments = 1000;
    int[] testArray;
    int target;
    int returnValue;

    while (experiments-- > 0) {
        testArray = generateRandomSortedArray(maxArraySize, maxValue);
        if (rand.nextBoolean())
            target = testArray[rand.nextInt(testArray.length)];
        else
            target = rand.nextInt();
        returnValue = Util.binarySearch(testArray, target);
        assertTheory1(testArray, target, returnValue);
        assertTheory2(testArray, target, returnValue);
    }
}

public void assertTheory1(int[] testArray, int target, int returnValue) {
    if (returnVAlue == -1)
        assertFalse(arrayContainsTarget(testArray, target));
}

public void assertTheory2(int[] testArray, int target, int returnValue) {
    if (returnValue >= 0)
        assertEquals(target, testArray[returnValue]);
}

public boolean arrayContainsTarget(int[] testArray, int target) {
    for (int i = 0; i < testArray.length; i++)
        if (testArray[i] == target)
            return true;
    return false;
}

}

上面我们根据返回值来推导输入的情况，但这其实只是测试了一半。我们在测试时需要进行逆向思维，在验证充分条件的时候，还要验证必要条件，即对于给定的输入，它的返回值也必定是我们的期望值。比如，下面修改的（被破坏的）二分法的代码：

public static int binarySearch(int[] a, int target) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low+high)/2;
        int midVal = a[mid];

        if (midVal < target)
            low = mid + 1;
        else
            high = mid - 1;
        else
            return mid;
    }
    if (target <= 424242)
        return -1;
    else
        return -42;
}

可以看到，在没找到的情况下，如果要找的目标元素不大于424242，那会正常返回-1；但如果元素值超过了424242，它会返回一个我们不期望的值。 很明显这个修改后的实现代码可以通过上面的随机测试，但是它却是错误的。为此，我们要填补另一半的测试，所以我们给出下面的另两个推论：

3、如果testArray不包含target，它就必须返回-1；

4、如果testArray在位置n上包含target，那么binarySearch(testArray, target)必须返回n。

下面是证明上两个推论的代码：

public void assertTheory3(int[] testArray, int target, int returnValue) {
    if (!arrayContainsTarget(testArray, target)
        assertEquals(-1, returnValue);
}

public void assertTheory4(int[] testArray, int target, int returnValue) {
    assertEquals(getTargetPosition(testArray, target), returnValue);
}

public int getTargetPosition(int[] testArray, int target) {
    for (int i = 0; i < testArray.length; i++)
        if (testArray[i] == target)
            return i;
    return -1;
}

public boolean arrayContainsTarget(int[] testArray, int target) {
    return getTargetPosition(testArray, target) >= 0;
}

在测试时会发现，推理4有时候会被违反：如果数组里有重复元素如{2, 11, 36, 66, 104, 108, 108, 108, 122, 155, 159, 161, 191}，target=108，期望值为5但实际的得到的值是6。这是我们测试代码的问题，为此，我们修改需要修改推理4使它将重复值纳入考量。

通过前面的测试，我们已经很确信我们的代码是正确的了。但是，它的性能如何呢？为此，我们需要进行性能测试。基于二分法的特性，我们可以得到：
推理5：如果testArray的长度为n，那么二分法的比较次数必须小于或等于1+log_2(n)。
下面是对应推理5的代码：

public static binarySearchComparisonCount(int[] a, target) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        comparisonCount++;

        int mid = (low+high)/2;
        int midVal = a[mid];

        if (midVal < target)
            low = mid + 1;
        else
            high = mid - 1;
        else
            return comparisonCount;
    }
    return comparisonCount;
}

public void assertTheory5(int[] testArray, int target) {
    int numberOfComparisons = Util.binarySearchComparisonCount(testArray, target);
    assertTrue(numberOfComparisons <= 1 + log2(testArray, length));
}

Alberto总结到：
1、有些测试因为简单和高效而漂亮；

2、有些测试因为可以改善变测代码的质量而漂亮；

3、有些测试因为它们的覆盖面和彻底性而漂亮。

：Agitar Software的CTO。著有《The Way of Testivus》。