Python 对数器实现与使用

对数器

• 通过大量的测试数据来验证算法是否正确的方式
• 核心组件：
  • 绝对正确的方法
  • 能产生大量随机样例的随机发生器

用处

• 验证算法是否正确
• 使用小样本校验
• 证明贪心策略

实现步骤

• 有一个你想要测的方法a
• 实现一个绝对正确，但是复杂度不好的方法b
• 实现一个随机样本产生器
• 实现对比的方法
• 把方法a和方法b对比很多次，来验证方法a是否正确
• 如果有一个样本，使得比对出错，打印样本分析是哪个方法出错
• 当样本数量很多时，比对测试依然正确，可以确定方法a已经正确

代码实现

import random


class Logarithm():
    """对数器的实现与使用"""

    def random_(self, size, number):
        """
        生成随机样本, 不同的操作对象, 使用不同样本发生器
        生成长度随机的数组: 数组的长度, 每个值都是随机的
        """
        value = random.randint(0, size)
        # 使用随机数-随机数, 生成 可能为正 可能为负 的数
        return [random.randint(0, number) - random.randint(0, number) for num in range(value)]

    def func_(self, arr):
        """
        写一个 一定正确的方法 , 不考虑时间复杂度
        如果这个方法，还是不能确定是否正确, 也可以:
        测试的时候, 总会有两个结果不一样的时候, 这时候, 在math里面打印错误的数列, 然后校验 func_
        """
        return sorted(arr)

    def math_(self, arr):
        """这里是我们自己写的算法"""
        for i in range(len(arr) - 1):
            for j in range(len(arr) - 1 - i):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
        return arr

    def run(self, size, value):
        """
        拿两个一样的数组, 放到绝对正确的方法 和 我们写的算法, 比较两者的输出结果
        如果结果一样, 则说明算法是正确的的, 返回对数器的结果
        """
        succeed = "True"
        for times in range(500000):
            random_list = self.random_(size, value)
            func_arr = self.func_(random_list)
            math_arr = self.math_(random_list)
            if func_arr != math_arr:
                succeed = f"False\r\nfunc_arr:{func_arr}\r\nmath_arr:{math_arr}"
                break
        print(succeed)


Logarithm().run(4, 31)

问题

如果没法写出一个绝对正确的方法，怎么办？

• 就算我们写不出绝对正确的方法，只要我们在这个方法中，能实现一部分，对于返回False的数据，我们直接打印出来，然后在修改，调整就好了。