【Python笔试题】2020-09-17

假设一个版本更新导致出现了bug，版本更新的源代码中一共有 $n(n>0)$ 处变动，现在需要找出其中导致发生bug的所有变动，变动用有序列表[1, 2, ..., n]表示。

用函数make(list)来将给定列表中的变动应用到版本更新前的源代码上并编译，该函数返回布尔类型表示编译成功或者失败。编译失败是因为变动之间有依赖关系，不把有依赖关系的变动放在同一个列表中进行编译就会导致失败。比如，假设变动2和变动3有依赖关系（可能是变动2定义了一个函数而变动3使用了这个函数），那么make([1, 2])就会返回False，make([2, 3])则会返回True。

如果某个变动是导致bug的原因，那么这个变动所有的依赖变动都认为是导致bug的原因。比如，变动2和变动3有依赖关系，且变动2位于问题变动列表中，那么变动3也在这个列表中。

编译好的版本才可以进行测试，用函数test(list)表示对list中的变动成功编译后的版本进行测试，该函数返回布尔类型表示列表中是否存在导致bug的变动。比如，如果test([2, 3])返回True，那么变动2跟变动3都没有问题；如果返回False，则说明变动2跟变动3中存在导致bug的变动。

现在我们给定 $n=1000$ ，并且从中随机选出 $m(m∈[3,5])$ 个变动作为问题变动，下面是提供的代码文件：

utils.py

import random

# 从1跟1000之间随机选3-5个组成列表，用下划线防止被其他文件通过星号导入
_bugs = random.sample(range(1, 1001), random.randint(3, 5))
# 从问题变动和非问题变动中随机选择一些作为依赖关系
_together = [random.sample(set(range(1, 1001)) - set(_bugs), 
                         random.randint(2, 3))]
_together.extend([random.sample(_bugs, random.randint(2, 3))])

def test(_list):
    """测试编译后的版本是否包含bug"""
    assert(make(_list))
    if set(_bugs) & set(_list):
        return False
    else:
        return True
    
def make(_list):
    """测试是否可以成功编译"""
    for i in _together:
        if len(set(_list) & set(i)) == 0 or \
           len(set(_list) & set(i)) == len(i):
            pass
        else:
            return False
    return True

def split(_list, n):
    """
    >>> split([1, 2, 3, 4, 5], 3)
    [[1, 2], [3, 4], [5]]
    """
    def inner():
        length = len(_list) // n + 1 if \
                 len(_list) % n else \
                 len(_list) // n
        start = 0
        for i in range(n):
            yield _list[start:start+length]
            start += length
    return list(inner())

def listminus(list1, list2):
    """
    >>> listminus([1, 2, 3], [1, 2])
    [3]
    """
    return sorted(set(list1)-set(list2))

def listunion(list1, list2):
    """
    >>> listunion([1, 2, 3], [3, 4])
    [1, 2, 3, 4]
    """
    return sorted(set(list1)|set(list2))

def test_dd(func):
    from profile import Profile
    
    def wrapper(*args, **kwargs):
        p = Profile()
        res = p.runcall(func, *args, **kwargs)
        if set(res) == set(_bugs):
            print("找到所有bug")
        else:
            print("失败")
        p.print_stats()
    return wrapper

请编写函数dd，找出导致发生bug的所有变动：

from utils import *

@test_dd
def dd(c_pass, c_fail, test):
    """
    初始情况下认为全都属于c_fail
    """
    pass

if __name__ == "__main__":
    dd([], [i for i in range(1, 1001)], test)

注意，每次编译make(list)和测试test(list)都需要花费一定时间，因此编写的函数要尽可能减少对这两个函数调用的次数。