Java对数器验证算法详解

2023-05-15 14:05:11 算法对数详解

对数器验证算法的正确性

对数器介绍

1.有一个你想要测的方法a；

2.实现一个绝对正确但是复杂度不好的方法b；

3.实现一个随机样本产生器；

4.实现对比算法a和b的方法；

5.把方法a和方法b比对多次来验证方法a是否正确；

6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；

7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

我们在写算法的时候很多情况下可能是应为没有案例测试而找不到bug,而通过对数器我们可以很方便的进行大量的样本测试，在这些样本中找到算法中不正确的案例，通过这些案例我们就能够发现我们的的程序出错在哪？如果大样本我们的程序都没有出错那么我们的程序也就可以理解为是正确的了。


public static int[] randomArray(int maxLength, int minValue, int maxValue) {
    int[] array = new int[random(0, maxLength + 1)];
    if (minValue > maxValue) {
        throw new IllegalArgumentException("左边界不能大于右边界");
    }
    int range = maxValue - minValue;
    for (int i = 0; i < array.length; i++) {
        array[i] = (int) (Math.random() * range) + minValue;
    }
    return array;
}

public static int random(int minValue, int maxValue) {
    if (minValue > maxValue) {
        throw new IllegalArgumentException("左边界不能大于右边界");
    }
    int rang = maxValue - minValue;
    return (int) (Math.random() * rang) + minValue;
}

public static boolean isSorted(int[] arr) {
    if (arr.length < 2) {
        return true;
    }
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (max > arr[i]) {
            return false;
        }
        max = Math.max(max, arr[i]);
    }
    return true;
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    for (int i = 0; i < N; i++) {
        int minValueIndex = i;
        for (int j = i + 1; j < N; j++) {
            minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
        }
        swap(arr, i, minValueIndex);
    }
}
public static void main(String[] args) {
    int maxLength = 50;
    int maxValue = 1000;
    int testTimes = 1000000;
    for (int i = 0; i < testTimes; i++) {
        int[] arr1 = randomArray(maxLength, 0, maxValue);
        int[] arr2 = arr1.clone();
        selectionSort(arr1);
        if (!isSorted(arr1)) {
            printArray(arr2);
            System.out.println("选择排序错了");
            break;
        }
    }
}

对数器模板

介绍：

该对数器会对我们写的 target() 函数进行 500000 ，每次目标数组是最大长度为 maxLength 最大值为maxValue 的整数数组，目标值是生成一个最大值为maxValue 的整数，通过检验两个函数的计算结果来比对我们写的函数是否正确的方法。

如果我们的函数在高达 50万次的测试中都正确，那么就可以说明我们的函数是正确的。

testTimes 函数的测试次数
randomArray(maxLength, maxValue) 生成一个最大长度为 maxLength 最大值为maxValue 的整数数组
random(0, maxValue); 生成一个最大值为maxValue 的整数
test(arr, num) 通过暴力方法写的低效率函数，但是保证正确率是100%
target(arr, num) 我们自己写的高效率的函数，不保证100%正确，通过对数器进行检验模板的正确性

public static void main(String[] args) {
    int testTimes = 500000;
    int maxLength = 50;
    int maxValue = 100;
    boolean success = true;
    for (int i = 0; i < testTimes; i++) {
        int[] arr = randomArray(maxLength, maxValue);
        Arrays.sort(arr);
        int num = random(0, maxValue);
        if (target(arr, num) != test(arr, num)) {
            success = false;
            printArray(arr);
            System.out.println(num);
            System.out.println("判断出错");
            System.out.println("目标函数结果 = " + target(arr, num));
            System.out.println("测试函数结果 = " + test(arr, num));
            break;
        }
    }
    System.out.println(success ? "LUCK" : "Fucking fucked");
}

到此这篇关于Java对数器验证算法详解的文章就介绍到这了,更多相关Java对数器内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

相关文章

Java对数器验证算法详解

目录

对数器验证算法的正确性

对数器模板