对数器

算法算法

创建时间:2019-03-19 16:30

阅读:

对数器的概念和使用

对数器的概念和使用

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

public class Util {

    public static void main(String[] args){
        int times = 5000;
        int maxSize = 10;
        int maxValue = 100;
        boolean success = true;
        for(int i = 0; i < times; i++){
            int[] arr1 = genericArray(maxSize,maxValue);
            int[] arr2 = copyArray(arr1);
            insertSort(arr1);
            Arrays.sort(arr2);
            if(!isEqual(arr1,arr2)){
                success = false;
                break;
            }
        }
        System.out.println(success ? "nice!": "fuck!");


        int[] arr = genericArray(maxSize,maxValue);
        printArray(arr);
        insertSort(arr);
        printArray(arr);

    }

    public static void printArray(int[] arr){
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    public static void insertSort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            for(int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--){
                swap(arr,j,j+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 int[] genericArray(int maxSize, int maxValue){
        int[] arr = new int[(int) (Math.random() * (maxSize + 1)) ];
        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[] arr_new = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
           arr_new[i] = arr[i];
        }
        return arr_new;
    }

    public static boolean isEqual(int[] arr1, int[] arr2){
        if( (arr1 == null && arr2 != null) || (arr1 != null && arr2 == null) ){
            return false;
        }
        if(arr1.length != arr2.length){
            return false;
        }
        if(arr1 == null && arr2 == null){
            return true;
        }
        for(int i = 0; i < arr1.length; i++){
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 876208453@qq.com