Java教程

ExpRe[4] 单元测试,算法题对拍

本文主要是介绍ExpRe[4] 单元测试,算法题对拍,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

时效性
本篇撰写时间为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文件,写一个简单的动态规划。
image

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\)这个求和满足题意,最小。

单元测试发现错误

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

对拍是一种进行检验或调试的方法,通过对比两个程序的输出来检验程序的正确性。可以将自己程序的输出与其他程序的输出进行对比。 (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次自动生成的测试过了。

总结和问答练习

  1. 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)

这篇关于ExpRe[4] 单元测试,算法题对拍的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!