左神给出了对数器的概念和使用 ：七天刷爆LeetCode，顶级算法大神
对数器的使用场景
- 在写出一个算法程序的时候，我们往往无法通过手动输入各种各样的测试数据来验证，在OJ平台上也无法找到对应的题目来进行验证。
- 在一些样本量很大的情况下，我们往往无法考虑到所有的边界情况。
- 尤其是一些贪心算法是很难通过数学的方式来进行验证的，这时使用对数器来判断算法程序是否正确
概念
- 1.有一个想要测的方法
- 2.实现复杂度不好但是容易实现的方法b
- 3.实现一个随机样本产生器
- 4.把方法a和方法b跑相同的随机样本，看看得到的结果是否一样
- 5.如果有一个随机样本使得比对结果不一致，打印样本进行人工干预，改对方法a或者方法b
- 6.当样本数量很多时比对测试依然正确，可以确定方法a已经正确
具体使用
step1: 创建一个绝对正确的方法
public static void comparator(int[] arr) { //方法b Arrays.sort(arr); } 复制代码
step2:生成一个随机数组
maxSize为数组的大小，maxValue为数组的元素的大小的范围
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; } 复制代码
step3:copy数组
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; } 复制代码
step4:判断两数组是否相同
public static boolean isEqual(int[] arr1, int[] arr2) { if (arr1 == null && arr2 == null) { return true; } if (arr1 == null || arr2 == null) { return false; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } 复制代码
step5:大样本测试
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" : "Bad"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); //没排序打印 bubbleSort(arr); //排序 printArray(arr); //排序完打印，程序员自己观察是否正确 } 复制代码
step6:对冒泡排序测试
public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int end = arr.length-1; end > 0; end--) { for (int i = 0; i < end; i++) { if (arr[i] > arr[i+1]) { swap(arr,i,i+1); } } } } 复制代码
完整的代码
public class ComparatorTest { //冒泡排序 方法a public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int end = arr.length-1; end > 0; end--) { for (int i = 0; i < end; 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]; } //for test public static void comparator(int[] arr) { //方法b Arrays.sort(arr); } //for test //生成随机数组 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; } //for test //复制数组 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) { return true; } if (arr1 == null || arr2 == null) { return false; } 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(); } //for test 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" : "Bad"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); //没排序打印 bubbleSort(arr); //排序 printArray(arr); //排序完打印，程序员自己观察是否正确 } }
