『每日算法 · 基础知识篇』备战面试，坚持算法 第一话——对数器！
文章目录
- 前言
- 一、对数器是什么
- 二、使用对数器
- 1.自己实现算法
- 2.使用另外一个算法写的解决问题的方法
- 3.实现一个随机器生成的样本数据
- 4.主方法中来使用对数器
- 三、完整代码展示
- 总结
前言
大家注意下列这些场景：
- 在写出一个算法程序的时候，我们往往无法通过手动输入各种各样的测试数据来验证，在OJ平台上也无法找到对应的题目来进行验证。
- 在一些样本量很大的情况下，我们往往无法考虑到所有的边界情况。
- 一些贪心算法是很难通过数学的方式来进行验证的，这时我们应该如何判断算法程序是否正确。
在这种情况的时候，我们就需要用到对数器了！
一、对数器是什么
通常我们在自己实现了一个算法之后，但是不能够判断该算法是否完全没问题，如果在比赛平台上验证，通常只会告诉你有没有错误，出了错不会告诉你哪里有问题，对于排错来说是非常麻烦的，所以对数器就横空出世了，对数器就是用一个绝对正确的方法和随机器生成的样本数据进行合体，如果你的算法是没问题的，那么和对数器的这个百分之百正确的方法一个元素一个元素的比较，也一定是equals的。如果返回false，说明你的算法有问题。
看到这里相信大家对于对数器已经多多少少有一些了解了！
对数器的使用需要具备两种东西：
- 对于解决这个问题的一个绝对正确的方法
- 一个随机器来生成样本数据
但对于第一个条件也可以变一下，我们其实也并不需要这个方法完全正确，只需要这个方法是另外一个算法写出来的，这样在使用对数器的过程中，如果出现了false，那么就是至少有一个方法出现了问题，这时候我们只需要对于这个测试案例对两个方法分别进行打断点测试，知道找出错误之后，继续使用对数器测试即可！
二、使用对数器
假如我们现在要使用选择排序算法来对数组排序从小到大排序，写完之后不知道自己写的这个方法是否完全正确那么我们需要使用到对数器来进行判断！
1.自己实现算法
//自己写的选择排序
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ N-1 找到最小值，在哪，放到0位置上
// 1 ~ n-1 找到最小值，在哪，放到1 位置上
// 2 ~ n-1 找到最小值，在哪，放到2 位置上
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
2.使用另外一个算法写的解决问题的方法
//直接使用Java自带的api数组排序
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
3.实现一个随机器生成的样本数据
//获得随机输入样例：随机的数组
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random() [0,1)
// Math.random() * N [0,N)
// (int)(Math.random() * N) [0, N-1]
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;
}
4.主方法中来使用对数器
//使用对数器判断自己写的选择排序算法是否正确
public static void main(String[] args) {
int testTime = 500000; //测试次数
int maxSize = 100; //最大测试容量：生成数组的最大容量
int maxValue = 100; //最大测试数据：生成随机数组中的值（-100~100）
boolean succeed = true; //是否对比成功
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);//生成随机数组
int[] arr2 = copyArray(arr1);
selectionSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "True！" : "False!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
selectionSort(arr);
printArray(arr);
}
三、完整代码展示
public class Code01_SelectionSort {
//自己写的选择排序
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 0 ~ N-1 找到最小值，在哪，放到0位置上
// 1 ~ n-1 找到最小值，在哪，放到1 位置上
// 2 ~ n-1 找到最小值，在哪，放到2 位置上
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//绝对正确的排序方法
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
/**
* 获得随机输入样例：随机的数组
* @param maxSize
* @param maxValue
* @return
*/
public static int[] generateRandomArray(int maxSize, int maxValue) {
// Math.random() [0,1)
// Math.random() * N [0,N)
// (int)(Math.random() * N) [0, N-1]
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;
}
//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;
}
//判断数组是否相等
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();
}
/**
* 使用对数器判断自己写的选择排序算法是否正确
* @param args
*/
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);
selectionSort(arr1);
comparator(arr2);
if (!isEqual(arr1, arr2)) {
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "True！" : "False!");
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
selectionSort(arr);
printArray(arr);
}
}
总结
最后再看看对数器使用思路：
- 有一个你想要测的方法a；
- 实现一个绝对正确但是复杂度不好的方法b；
- 实现一个随机样本产生器；
- 实现对比算法a和b的方法；
- 把方法a和方法b比对多次来验证方法a是否正确；
- 如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
- 当样本数量很多时比对测试依然正确，可以确定方法a已经正确；
本篇文章参考：
1.左神体系学习班课程第1节
2.https://blog.csdn.net/u011679785/article/details/97117250