【算法&数据结构初阶篇】：对数器，随机生成大量测试用例神器

朱雀 2024-03-27 15:56 103阅读 0赞

> 对数器就是一个工具，可以帮我们生成对应的大量测试用例，当然测试用例的定义就是我们业务自己来定，比如你写了一个排序算法，想验证数组的排序是否正确，除了在线OJ可以测试，有时本地方便也可以自己手写一个对数器来验证正确性，即生成大量的随机数组。

核心点：需要调用Math函数的随机方法random()

## 一、排序算法的对数器，返回大量随机数组 ##

1.  generateRandomArray（）对数器方法 生成大量测试用例

1.  comparator（）方法，调用原生的sort方法进行排序，用来验证与我们各种排序算法排序后的结果是否一致，验证正确性

package train;
    
    import org.junit.Test;
    
    import java.util.Arrays;
    
    public class Sort1 {
        //选择排序 从左往右取出最小索引 然后与第一位交换，接着找最小 再赋给第二位...
        public static void selectSort(int[] arr) {
            if (arr == null || arr.length == 1) {
                return;
            }
            for (int i = 0; i < arr.length - 1; i++) {
                int index = i;
                for (int j = i + 1; j < arr.length; j++) {
                    index = arr[index] > arr[j] ? j : index;
                }
                if(index != i) swap(arr, index, i);
    
            }
        }
         //冒泡排序  从左往右 前一个数大于后一个数，则交换，第一轮就把最大值放到尾索引，接着从左往右，最大值放到倒数第二个...
        public static void bubbleSort(int[] arr){
            if (arr == null || arr.length == 1) {
                return;
            }
            for(int i = arr.length - 1; i > 0; i--){
                for(int j = 0; j < i; j++){
                    if(arr[j] > arr[j+1]) {
                        swap(arr,j,j+1);
                    }
                }
            }
        }
    
        //插入排序，每次保证 0-i有序，就像扑克牌，每次往左侧依次比较，后面的数小于前面的数就两两交换..
        public static void insertSort(int[] arr){
            if (arr == null || arr.length == 1) {
                return;
            }
            for(int i = 1; i < arr.length; i++){
                for(int j = i-1; j >= 0 && arr[j+1] < arr[j];j--){
                    swap(arr,j+1,j);
                }
            }
        }
    
        //交换两个数值
        public static void swap(int[] arr, int i, int j) {
    //        int temp = arr[i];
    //        arr[i] = arr[j];
    //        arr[j] = temp;
            // i和j是一个位置的话，会出错
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }
    
        //用内置的数组排序api 进行验证选择排序是否有误
        public static void comparator(int[] arr) {
            Arrays.sort(arr);
        }
    
        //随机生成 指定范围 -maxValue,maxValue ，指定长度maxSize的数组
        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) ((maxSize + 1) * Math.random()) - (int) ((maxSize + 1) * Math.random());
            }
            return arr;
        }
    
        //将随机生成数组进行深度拷贝复制一份
        public static int[] copyArray(int[] arr){
            if(arr == null) return null;
            int[] ans = new int[arr.length];
            for(int i = 0 ;i < arr.length; i++){
                ans[i] = arr[i];
            }
            return ans;
        }
    
       //验证排序后的两个数组是否相等
        public static boolean  isEquals(int[] arr1, int[] arr2){
            if((arr1 == null && arr1 != null) || (arr1 != null && arr1 == null) || 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;
        }
    
        //输出数组内容
        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();
        }
        @Test
        public  void test(){
            int time = 50000;
            int maxSize = 10;
            int maxValue = 20;
            boolean flag = true;
            for(int i = 0; i < time; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
    //            printArray(arr1);
    //            selectSort(arr1);
    //            bubbleSort(arr1);
                insertSort(arr1);
                comparator(arr2);
                boolean equals = isEquals(arr1, arr2);
                if (!equals) {
                    System.out.println("排序出错！");
                    printArray(arr1);
                    printArray(arr2);
                    flag = false;
                    break;
                }
            }
            if(flag) System.out.println("排序成功！");
        }
    
        public static void main(String[] args) {
            int time = 50000;
            int maxSize = 10;
            int maxValue = 20;
            boolean flag = true;
            for(int i = 0; i < time; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
    //            printArray(arr1);
                selectSort(arr1);
                comparator(arr2);
                boolean equals = isEquals(arr1, arr2);
                if (!equals) {
                    System.out.println("排序出错！");
                    printArray(arr1);
                    printArray(arr2);
                    flag = false;
                    break;
                }
            }
            if(flag) System.out.println("排序成功！");
        }
    }

## 二、局部最小值的对数器，返回大量相邻元素不等数组 ##

1.  局部最小值的题目，前提就是测试用例数组，元素相邻之间不能相等，才能有局部最小的效果

1.  generateRandomArray2（）方法实现 do\{\}while(arr\[i\] == arr\[i-1\]),相等则继续随机生成直到不相等

package train;
    
    import org.junit.Test;
    
    import java.util.Arrays;
    
    public class BinarySearch {
        //找一个指定数值是否存在
        public static boolean isExist(int[] arr, int num) {
            if (arr == null || arr.length == 0)
                return false;
            int left = 0;
            int right = arr.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (arr[mid] == num) {
                    return true;
                } else if (arr[mid] > num) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return false;
        }
    
        // 在arr上，找满足>=value的最左位置
        public static int nearestIndex(int[] arr, int num) {
            int left = 0;
            int right = arr.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (arr[mid] == num) {
                    right = mid - 1;
                } else if (arr[mid] > num) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            //这里需要先判断 是否越界 假设num比所有数都大，left就会越界
            if (left == arr.length) return -1;
            return arr[left] >= num ? left : -1;
        }
    
        // 在arr上，找满足<=value的最右位置
        public static int nearestIndex2(int[] arr, int value) {
            int left = 0;
            int right = arr.length - 1;
            int index = -1;
            while (left <= right) {
                int mid = left + ((right - left) >> 2);
                if (arr[mid] <= value) {
                    index = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return index;
        }
    
        //获取局部最小。 验证了二分查找不一定需要有序的数组，只要有固定的一个趋势，也可以解决
        public static int getLessIndex(int[] arr) {
            if (arr == null || arr.length == 0) {
                return -1;
            }
            //如果第一个元素小于第二个 可以判断第一个是局部最小
            if (arr.length == 1 || arr[0] < arr[1]) {
                return 0;
            }
            //同理
            if (arr[arr.length - 1] < arr[arr.length - 2]) {
                return arr.length - 1;
            }
            //来到这里 说明前面情况都不符合，那么就可以得到一个 头部下扬，尾部上扬 那么中间必定是有个局部最小值
            //抛开首尾两节点 开始二分
            int left = 1;
            int right = arr.length - 2;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if(arr[mid] <arr[mid - 1] && arr[mid]  <arr[mid + 1]){
                    return mid;
                }
                if (arr[mid] > arr[mid - 1]) {
                    right = mid - 1;
                } else if(arr[mid] > arr[mid + 1]){
                    left= mid +1;
                }
            }
            return -1;
        }
    
        // for test
        public static boolean test(int[] sortedArr, int num) {
            for (int cur : sortedArr) {
                if (cur == num) {
                    return true;
                }
            }
            return false;
        }
    
        // for test
        public static int test2(int[] arr, int value) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] >= value) {
                    return i;
                }
            }
            return -1;
        }
    
        public static int test3(int[] arr, int value) {
            for (int i = arr.length - 1; i >= 0; i--) {
                if (arr[i] <= value) {
                    return i;
                }
            }
            return -1;
        }
    
        // 验证得到的结果，是不是局部最小
        public static boolean isRight(int[] arr, int index) {
            if (arr.length <= 1) {
                return true;
            }
            if (index == 0) {
                return arr[index] < arr[index + 1];
            }
            if (index == arr.length - 1) {
                return arr[index] < arr[index - 1];
            }
            return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
        }
    
        // for test
        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 int[] generateRandomArray2(int maxSize, int maxValue) {
            int[] arr = new int[(int)((maxSize)*Math.random())+1];
            arr[0] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
            for (int i =1; i< arr.length;i++){
            do {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
            }while(arr[i] == arr[i-1]);
            }
            return 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 + 1) * Math.random());
            }
            return arr;
        }
    
        @Test
        public void testNearestIndex() {
            int testTime = 500000;
            int maxSize = 10;
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
    //            int[] arr = generateRandomArray(maxSize, maxValue);
                int[] arr2 = generateRandomArray2(maxSize, maxValue);
    //            Arrays.sort(arr);
    //            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    //            if (test2(arr, value) != nearestIndex(arr, value)) {
    //                printArray(arr);
    //                System.out.println(value);
    //                System.out.println(test2(arr, value));
    //                System.out.println(nearestIndex(arr, value));
    //                succeed = false;
    //                break;
    //            }
    //            if (test3(arr, value) != nearestIndex2(arr, value)) {
    //                printArray(arr);
    //                System.out.println(value);
    //                System.out.println(test2(arr, value));
    //                System.out.println(nearestIndex(arr, value));
    //                succeed = false;
    //                break;
    //            }
                int index = getLessIndex(arr2);
                if(!isRight(arr2,index)){
                    System.out.println("测试失败！");
                    System.out.println(Arrays.toString(arr2));
                    System.out.println(index);
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
        }
    
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 10;
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                int[] arr = generateRandomArray(maxSize, maxValue);
                Arrays.sort(arr);
                int value = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
                if (test(arr, value) != isExist(arr, value)) {
                    succeed = false;
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
        }
    }