恒恒恒咩

V1

2022/06/26阅读:21主题:雁栖湖

对数器

Part1对数器

基本概念

对数器是用来测试代码正确性的,我们在找不到合适的oj系统测试自己的代码时,可以自己写一个对数器对代码进行测试

基本步骤以及相关代码:

1.有一个你想要测的方法a;

public static void insertionSort(int[] arr) {
  if (arr == null || arr.length < 2) {
   return;
  }
  for (int i = 1; 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];
 }

2.实现一个绝对正确但是复杂度不好的方法b;

public static void comparator(int[] arr) {
   Arrays.sort(arr);
}//java自带的排序方法

3.实现一个随机样本产生器;

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 * Math.random());
  }
  return arr;
 }
//产生的数组长度是[0, size]
//产生的数组中的数的范围是-value ~ value

4.实现对比算法a和b的方法;

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;
 }

5.把方法a和方法b比对多次来验证方法a是否正确;

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);
/*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;
 }*/

            //比较方法,确定样本相同
   insertionSort(arr1);
   comparator(arr2);
   if (!isEqual(arr1, arr2)) {
    succeed = false;
    break;
   }
  }
  System.out.println(succeed ? "Nice!" : "Sorry");

6.如果有一个样本使得比对出错,打印样本分析是哪个方法出错;

7.当样本数量很多时比对测试依然正确,可以确定方法a已经正确。


[^相关资源]: https://www.bilibili.com/video/BV13g41157hK?p=3&vd_source=d810daa390a8d5e7a9e67f1a5e78ed57 P3

分类:

后端

标签:

数据结构与算法

作者介绍

恒恒恒咩
V1