对数器作用

  1. 你想要测的办法a
  2. 实现复杂度不好然而容易实现的办法b
  3. 实现一个随机样本产生器
  4. 把办法a和办法b跑雷同的随机样本，看看失去的后果是否一样
  5. 如果有一个随机样本使得比对后果不统一，打印样本进行人工干预，改对办法a和办法b
  6. 当样本数量很多时比对测试仍然正确，能够确定办法a曾经正确。

对数器的实现

// for testpublic static void comparator(int[] arr) { Arrays.sort(arr);}// for testpublic 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;}// for testpublic 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;}// for testpublic 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;}// for testpublic 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();}// for testpublic static void main(String[] args) { int testTime = 500000; int maxSize = 100; // 随机数组的长度0～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); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { // 打印arr1 // 打印arr2 succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr);}