• 一个错误题解
• 单元测试发现错误
• 更正错误
• 再次发现错误和更正
• 总结和问答练习

• ExpRe[0] VSCode的使用，编辑Markdown，管理知乎
  https://www.cnblogs.com/minor-second/p/15528264.html
• ExpRe[3] Anaconda配置python环境
  https://www.cnblogs.com/minor-second/p/15549061.html

一个错误题解

我们看到一道普通的算法题：

给定实数列\(\{x_i\}_{i=1}^n\)，要确定\(1\le i\le j\le n\)，使得\(\sum_{k=i}^j x_k\)最小。请编制时间复杂度为\(O(n)\)的算法求解该问题。

由于算法课上只用交伪码，不知道自己写的究竟对不对，于是我们想用单元测试检查算法正确性。
在上一期创建的python环境中，新建.py文件，写一个简单的动态规划。

def find_min_sub(n, x):
    assert isinstance(x, tuple), 0
    assert all(isinstance(x[i], float) for i in range(len(x))), 1
    assert isinstance(n, int) and n > 0, 2
    assert len(x) == n, 3
    global_min = [0, 1, x[0]]
    marginal_min = [0, 1, x[0]] if x[0] < 0 else [1, 1, 0]
    for i in range(1, n):
        if marginal_min[2] + x[i] >= 0:
            marginal_min = [i+1, i+1, 0]
        else:
            marginal_min[1] = i+1
            marginal_min[2] += x[i]
        if marginal_min[2] < global_min[2] and marginal_min[0] < marginal_min[1]:
            global_min = marginal_min
        if x[i] < global_min[2]:
            global_min = [i, i+1, x[i]]
    return global_min[0]+1, global_min[1]
print(find_min_sub(5, (0., -1., 0.5, -0.6, 0.)))

其实这是错误的，你发现问题在哪里了吗？
但是直接Ctrl+F5运行，没有任何问题。正确输出(2, 5)，表示\(-1+0.5-0.6+0\)这个求和满足题意，最小。

单元测试发现错误

新建一个文件用于单元测试。

对拍是一种进行检验或调试的方法，通过对比两个程序的输出来检验程序的正确性。可以将自己程序的输出与其他程序的输出进行对比。 (OI Wiki)

比如把暴力方法和自己写的方法对比。

import unittest
import random
from problem1 import find_min_sub
class Test(unittest.TestCase):  # 编写自己的测试类，继承指定类

    def test_manual(self):  # test开头的才被认为测试方法，测试时才被执行
        i, j = find_min_sub(5, (0., -2., 1., -2., 3.))
        self.assertEqual(i, 2)
        self.assertEqual(j, 4)
        i, j = find_min_sub(10, (0.1, -2., -2., -7., 10., -3., -3., -5., 2., -1.))
        self.assertEqual(i, 2)
        self.assertEqual(j, 8)
    
    def test_assertion(self):
        with self.assertRaises(AssertionError):
            find_min_sub(1, (0.,0.))
            find_min_sub('', '')
    
    def test_auto(self):
        n = random.randrange(1, 1000)
        x = tuple(random.random() * 10 - 5 for _ in range(n))

        start, end, min_value = 0, 0, float('inf')
        for s in range(n):
            for e in range(s+1, n):
                v = sum(x[s:e])
                if v < min_value:
                    start, end, min_value = s, e, v
        start += 1     

        i, j = find_min_sub(n, x)       
        self.assertEqual(start, i, msg=(n, x))
        self.assertEqual(end, j, msg=(n, x))

if __name__ == '__main__':
    unittest.main()

运行，发现报告有

Ran 3 tests in 0.672s

FAILED (failures=2)

我们发现手工编写的长一点的测试例就出错了。于是去仔细检查代码。

更正错误

我们发现函数find_min_sub倒数第4行末尾少了[:]（或：.copy()），导致两个list之间修改一个也修改另一个。
这是使用python一个常见大坑：可变(mutable)对象
更正错误之后，保存文件，运行测试文件test1.py。输出

(2, 4)
...
----------------------------------------------------------------------
Ran 3 tests in 0.122s

OK

然而以上仍有错误，你发现了吗？

再次发现错误和更正

我们仍然不放心，更改test_auto函数为循环100次。

    def test_auto(self):
        for _ in range(100):
            n = random.randrange(1, 1000)
            x = tuple(random.random() * 10 - 5 for _ in range(n))

            start, end, min_value = 0, 0, float('inf')
            for s in range(n):
                for e in range(s+1, n):
                    v = sum(x[s:e])
                    if v < min_value:
                        start, end, min_value = s, e, v
            start += 1     

            i, j = find_min_sub(n, x)       
            self.assertEqual(start, i, msg=(n, x))
            self.assertEqual(end, j, msg=(n, x))

发现仍然出现了错误（但错误出现的频率并不高）。一个典型错误例：

(8, (2.2805755721332455, 1.1867061512050858, -2.061145458146788, -2.0107648781130516, 4.032469478859333, -2.184053441010362, 4.834683794987862, -4.984215701600048))

反复运行，发现错误总是和数组末尾有关。
经过仔细检查，发现是对拍的暴力方法写错了。for e in range(s+1, n):应该是for e in range(s+1, n+1):.
再次运行，发现对100次自动生成的测试过了。

总结和问答练习

0. Q: 之前写的测试真的可以充分发现出算法的错误吗？试写出一个（极大概率能）通过测试的错误算法。
   A:

def find_min_sub(n, x):
    assert isinstance(x, tuple), 0
    assert all(isinstance(x[i], float) for i in range(len(x))), 1
    assert isinstance(n, int) and n > 0, 2
    assert len(x) == n, 3
    global_min = [0, 1, x[0]]
    marginal_min = [0, 1, x[0]] if x[0] < 0 else [1, 1, 0]
    for i in range(1, n):
        if marginal_min[2] + x[i] >= 0:
            marginal_min = [i+1, i+1, 0]
        else:
            marginal_min[1] = i+1
            marginal_min[2] += x[i]
        if marginal_min[2] < global_min[2] and marginal_min[0] < marginal_min[1]:
            global_min = marginal_min[:]
    return global_min[0]+1, global_min[1]

此时对于恒正的数据就极有可能输出错误结果。
这说明完全随机生成测试数据有缺陷。

1. Q: 完全随机生成测试数据还可能有什么缺陷？举例说明。
   A: 比如不利于考察最坏时间复杂度，当实际问题的系统有很多assert断言条件时纯随机数据会有大量平凡的非法例等。
   注：因此我们之后将探索用约束求解生成测试例的技术。
2. Q: 运行test.py时，为什么输出了(2, 4)这种字样？
   A: import模块时，会自动执行其中的语句，如print

模块可以包含可执行的语句以及函数定义。这些语句用于初始化模块。它们仅在模块第一次在import语句中被导入时才执行。（当文件被当作脚本运行时，它们也会执行）
实际上，函数定义也是“被执行”的“语句”；模块级函数定义的执行在模块的全局符号表中输入该函数名。 (docs.python.org)