本文主要是介绍算法学习笔记——对数器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
对数器
对数器的实现:
- 你想要测的方法a(最优解)
- 实现复杂度不好但是容易实现的方法b(暴力解)
- 实现一个随机样本产生器(长度也随机、值也随机)
- 把方法a和方法b跑相同的输入样本,看看得到的结果是否一样
- 如果有一个随机样本使得比对结果不一致,打印这个出错的样本进行人工干预,改对方法a和方法b
- 当样本数量很多时比对测试依然正确,可以确定方法a(最优解)已经正确。
关键是第5步,找到一个数据量小的错误样本,便于你去带入debug
然后把错误例子带入代码一步一步排查
Print大法、断点技术都可以
对数器的门槛其实是比较高的,因为往往需要在两种不同思路下实现功能相同的两个方法,暴力一个、想象中的最优解是另一个。
以后的很多题目都用到对数器,几乎可以验证任何方法,尤其在验证贪心、观察规律方面很有用。
public static void main(String[] args){// 随机数组最大长度int N = 100;// 随机数组每个值,在1~V之间随机int V = 1000;// testTimes : 测试次数int testTimes = 50000;System.out.println("测试开始");for (int i = 0; i < testTimes; i++){// 随机得到一个长度,长度在[0~N-1]int n = (int) (Math.random() * N);// 得到随机数组int[] arr = randomArray(n, V);int[] arr1 = copyArray(arr);int[] arr2 = copyArray(arr);int[] arr3 = copyArray(arr);selectionSort(arr1);bubbleSort(arr2);insertionSort(arr3);if (!sameArray(arr1, arr2 ) || !sameArray(arr1, arr3)){System.out.println("出错了!");// 当有错了// 打印是什么例子,出错的// 打印三个功能,各自排序成了什么样// 可能要把例子带入}}System.out.println("测试结束");
}// 为了验证
// 得到一个随机数组,长度是n
// 数组中每个数,都在1~v之间,随机得到
public static int[] randomArray(int n, int v){int[] arr = new int[n];for (int i = 0; i < n; i++){// Math.random() -> double -> [0,1)一个小数,0.37463473126、0.001231231// Math.random() * v -> double -> [0,v)一个小数,依然等概率// (int)(Math.random() * v) -> int -> 0 1 2 3 ... v-1,等概率的!// (int)(Math.random() * v) + 1 -> int ->1 2 3 ... v,等概率的!arr[i] = (int)(Math.random() * v) + 1;}return arr;
}// 为了验证
// 拷贝数组
public static int[] copyArray(int[] arr){int n = arr.length;int[] ans = new int[n];for (int i = 0; i < n; i++){ans[i] = arr[j];}return ans;
}// 为了验证
// 验证数组是否一样
public static boolen sameArray(int[] arr1, int[] arr2){int n = arr1.length;for (int i = 0; i < n; i++){if (arr1[i] != arr2[i]){return false;}}return true;
}....
这篇关于算法学习笔记——对数器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!