时效性
本篇撰写时间为2021.11.13,由于计算机技术日新月异,博客中所有内容都有时效和版本限制,具体做法不一定总行得通,链接可能改动失效,各种软件的用法可能有修改。但是其中透露的思想往往是值得学习的。
Windows 10家庭中文版,版本20H2,操作系统内部版本19042.1288
本篇前置:
- 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次自动生成的测试过了。
总结和问答练习
- 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]
此时对于恒正的数据就极有可能输出错误结果。
这说明完全随机生成测试数据有缺陷。
- Q: 完全随机生成测试数据还可能有什么缺陷?举例说明。
A: 比如不利于考察最坏时间复杂度,当实际问题的系统有很多assert
断言条件时纯随机数据会有大量平凡的非法例等。
注:因此我们之后将探索用约束求解生成测试例的技术。 - Q: 运行
test.py
时,为什么输出了(2, 4)
这种字样?
A:import
模块时,会自动执行其中的语句,如print
模块可以包含可执行的语句以及函数定义。这些语句用于初始化模块。它们仅在模块第一次在
import
语句中被导入时才执行。(当文件被当作脚本运行时,它们也会执行)
实际上,函数定义也是“被执行”的“语句”;模块级函数定义的执行在模块的全局符号表中输入该函数名。 (docs.python.org)