快捷導(dǎo)航

Java對(duì)數(shù)器驗(yàn)證算法詳解

更新時(shí)間：2023年04月12日 11:46:14 作者：ziop-三月

這篇文章主要介紹了Java對(duì)數(shù)器驗(yàn)證算法，Java對(duì)數(shù)函數(shù)的計(jì)算方法非常有問題，然而在API中卻有驚人的誤差。但是假如運(yùn)用了以下的方法，用Java處理數(shù)字所碰到的小麻煩就可以輕而易舉的解決了

對(duì)數(shù)器驗(yàn)證算法的正確性

對(duì)數(shù)器介紹

1.有一個(gè)你想要測的方法a；

2.實(shí)現(xiàn)一個(gè)絕對(duì)正確但是復(fù)雜度不好的方法b；

3.實(shí)現(xiàn)一個(gè)隨機(jī)樣本產(chǎn)生器；

4.實(shí)現(xiàn)對(duì)比算法a和b的方法；

5.把方法a和方法b比對(duì)多次來驗(yàn)證方法a是否正確；

6.如果有一個(gè)樣本使得比對(duì)出錯(cuò)，打印樣本分析是哪個(gè)方法出錯(cuò)；

7.當(dāng)樣本數(shù)量很多時(shí)比對(duì)測試依然正確，可以確定方法a已經(jīng)正確。

我們?cè)趯懰惴ǖ臅r(shí)候很多情況下可能是應(yīng)為沒有案例測試而找不到bug,而通過對(duì)數(shù)器我們可以很方便的進(jìn)行大量的樣本測試，在這些樣本中找到算法中不正確的案例，通過這些案例我們就能夠發(fā)現(xiàn)我們的的程序出錯(cuò)在哪？如果大樣本我們的程序都沒有出錯(cuò)那么我們的程序也就可以理解為是正確的了。

/**
 * 生成一個(gè)長度為 0-maxLength 的 int 數(shù)組，范圍是 [minValue,maxValue)<br/>
 * 只有正數(shù) 無負(fù)數(shù)<br/><br/>
 * <p>
 * 用法：<br/>
 * int[] array = ArrayTools.randomArray(20, 5, 10);<br/>
 * for (int i : array) {<br/>
 * &nbsp;&nbsp;&nbsp;&nbsp;System.out.print(i + " ");<br/>
 * }<br/>
 * 結(jié)果如下：<br/>
 * 8 7 7 8 9 7 5 5 9 9 6 5 8 8 7 6 9 7 8 5<br/>
 *
 * @param maxLength 數(shù)組長度
 * @param minValue  生成的數(shù)值都大于等于  minValue
 * @param maxValue  生成的數(shù)值都小于  maxValue
 * @return 生成一個(gè)長度為 0-maxLength 的 int 數(shù)組,范圍是 [minValue,maxValue)
 * @throws IndexOutOfBoundsException 左邊界不能大于右邊界
 */
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;
}
/**
 * 生成一個(gè) 在 [minValue,maxValue) 的隨機(jī)整數(shù)
 * @param minValue  最小值
 * @param maxValue  最大值
 * @return 在 [minValue,maxValue) 的隨機(jī)整數(shù)
 */
public static int random(int minValue, int maxValue) {
    if (minValue > maxValue) {
        throw new IllegalArgumentException("左邊界不能大于右邊界");
    }
    int rang = maxValue - minValue;
    return (int) (Math.random() * rang) + minValue;
}
/**
 * 檢驗(yàn)數(shù)組是否是升序排列
 * @param arr  待檢查數(shù)組
 * @return  檢查結(jié)果  
 */
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;
}
/**
 * 交換 arr 數(shù)組當(dāng)中 i 位置和 j 位置的元素
 * @param arr  待交換數(shù)組
 * @param i  第一個(gè)元素位置
 * @param j  第二個(gè)元素位置
 */
private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
/**
 *  選擇排序
 * @param arr 待排序數(shù)組
 */
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("選擇排序錯(cuò)了");
            break;
        }
    }
}

對(duì)數(shù)器模板

介紹：

該對(duì)數(shù)器會(huì)對(duì)我們寫的 target() 函數(shù) 進(jìn)行 500000 ，每次目標(biāo)數(shù)組是最大長度為 maxLength 最大值為maxValue 的整數(shù)數(shù)組，目標(biāo)值是生成一個(gè)最大值為maxValue 的整數(shù)，通過檢驗(yàn)兩個(gè)函數(shù)的計(jì)算結(jié)果來比對(duì)我們寫的函數(shù)是否正確的方法。

如果我們的函數(shù)在高達(dá) 50萬次的測試中都正確，那么就可以說明我們的函數(shù)是正確的。

testTimes 函數(shù)的測試次數(shù)
randomArray(maxLength, maxValue) 生成一個(gè) 最大長度為 maxLength 最大值為maxValue 的整數(shù)數(shù)組
random(0, maxValue); 生成一個(gè)最大值為maxValue 的整數(shù)
test(arr, num) 通過暴力方法寫的低效率函數(shù)，但是保證正確率是100%
target(arr, num) 我們自己寫的高效率的函數(shù)，不保證100%正確，通過對(duì)數(shù)器進(jìn)行檢驗(yàn)?zāi)０宓恼_性

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("判斷出錯(cuò)");
            System.out.println("目標(biāo)函數(shù)結(jié)果 = " + target(arr, num));
            System.out.println("測試函數(shù)結(jié)果 = " + test(arr, num));
            break;
        }
    }
    System.out.println(success ? "LUCK" : "Fucking fucked");
}