对数器
对数器是用来测试代码正确性的,我们在找不到合适的oj系统测试自己的代码时,可以自己写一个对数器对代码进行测试。
对数器的概念和使用
0,有一个你想要测的方法a,
1,实现一个绝对正确但是复杂度不好的方法b,
2,实现一个随机样本产生器
3,实现比对的方法
4,把方法a和方法b比对很多次来验证方法a是否正确
5,如果有一个样本使得比对出错,打印样本分析是哪个方法出错
6,当样本数量很多时比对测试依然正确,可以确定方法a已经正确

下面使用冒泡排序的代码进行举例说明:
import java.util.Arrays; public class Code_00_BubbleSort { //要测试的方法 public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int e = arr.length - 1; e > 0; e--) { for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } } } public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // 实现一个绝对正确即使复杂度不好的方法 public static void comparator(int[] arr) { Arrays.sort(arr); } // 实现一个随机样本产生器 public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // 实现比对的方法 public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // 打印 public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } //把方法a和方法b比对很多次来验证方法a是否正确 //如果有一个样本使得比对出错,打印样本分析是哪个方法出错 //当样本数量很多时比对测试依然正确,可以确定方法a已经正确 public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); bubbleSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); bubbleSort(arr); printArray(arr); } }