Java算法正确性分析工具：对数器

对数器是什么？

通常我们在笔试的时候或者参加编程大赛的时候，自己实现了一个算法，但是不能够判断该算法是否完全没问题，如果在比赛平台上验证，通常只会告诉你有没有错误，出了错不会告诉你哪里有问题，对于排错来说是非常坑爹的，所以对数器就横空出世了，对数器就是用一个绝对OK的方法和随机器生成的样本数据进行合体，如果你的算法是没问题的，那么和对数器的这个百分之百正确的方法一个元素一个元素的比较，也一定是equals的。如果返回false，说明你的算法有问题。

纳尼？？我都能写出一个百分之百正确的对数器了，还用得着跟我自己实现的算法比较么？肯定也是对的啊，话是如此，没错，但是算法的目的是更高效、更优的处理一些问题，你的比较器的时间复杂度和空间复杂度往往是比较低的，因为这样才能保证它的准确性，而你笔试或者比赛写出的算法，复杂度往往比较高，所以可以通过低复杂度但是绝对正确的方法验证你的算法正确不正确。

对数器的概念的：

1.有一个你想要测的方法a；
2.实现一个绝对正确但是复杂度不好的方法b；
3.实现一个随机样本产生器；
4.实现对比算法a和b的方法；
5.把方法a和方法b比对多次来验证方法a是否正确；
6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。

对数器怎么用？
知道了对数器是什么之后，我们来看看应该怎么实现一个自己的对数器，以冒泡排序为例，直接上代码：

public class BubbleSort {
    //这个是我想要测的方法A
    public static void bubbleSort(int arr[]) {
        for (int i = 0; i < arr.length-1; i++) {//外循环循环n-1次
            for (int j = 1; j < arr.length-i; j++) {//内循环每一次要比较n-i次
                if(arr[j-1]>arr[j]){
                    int temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                }
            }
        }
    }
    //这是一个绝对正确但是复杂度不好的方法
    public static void rightSort(int[] arr) {
        Arrays.sort(arr);
    }
    //这是一个随机样本产生器
    public static int[] generateRandomArray(int maxSize, int maxNum) {
        int[] arr = new int[(int) ((maxSize+1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*(maxNum+1)) - (int)(Math.random()*maxNum);
        }
        return arr;
    }
    //这个是对比算法a和b方法是否相同的方法
    public static boolean isEquals(int[] arr1, int[] arr2) {
        if (arr1.length != arr2.length) {
            return false;
        }
        if (arr1 != null && arr2 == null || arr1 == null && arr2 != null) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
  //复制当前数组的一个样本
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] newArray = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            newArray[i] = arr[i];
        }
        return newArray;
    }
    //打印数组
    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();
    }
    public static void main(String[] args) {
         int testTims = 500000;//测试次数
         int maxSize = 20;//最大测试容量
         int maxNum = 100;//最大测试数据
         boolean euqals = true;
         for (int i = 0; i < testTims; i++) {
                 //原始数组
                int[] arr1 = generateRandomArray(maxSize,maxNum);
                int[] arr2 = copyArray(arr1);//这两个数组除了
                int[] arr3 = copyArray(arr1);//这两个数组除了
                //数值相同内存地址完全没关系，请看copyArray()方法实现
                bubbleSort(arr2);//用自己的算法排序
                rightSort(arr3);//用java.util.Arrays包的排序算法排序
                if (!isEquals(arr2,arr3)) {//比较是否相同
                    printArray(arr1);//再次打印，程序员自己看看有没有毛病
                    printArray(arr2);//再次打印，程序员自己看看有没有毛病
                    printArray(arr3);//再次打印，程序员自己看看有没有毛病
                    euqals = false;//一旦有不一样的值就设为false;
                    break;
                }
            }
            System.out.println(euqals ? "Success:恭喜你！没毛病！" : "Error：抱歉，有错误" );//没错就恭喜，有错就报错
    }
}

结果如下:

Success:恭喜你！没毛病！

这就说明自己实现的冒泡排序是没毛病的，回过头再看一下对数器的概念，是不是更加理解了呢？