一、什么是对数器？
通常我们在笔试的时候或者参加编程大赛的时候，自己实现了一个算法，但是不能够判断该算法是否完全没问题，如果在比赛平台上验证，通常只会告诉你有没有错误，出了错不会告诉你哪里有问题，对于排错来说是非常坑爹的，所以对数器就横空出世了，对数器就是用一个绝对OK的方法和随机器生成的样本数据进行合体，如果你的算法是没问题的，那么和对数器的这个百分之百正确的方法一个元素一个元素的比较，也一定是equals的。如果返回false，说明你的算法有问题。
简单来说，就是自己编写一个时间复杂度较低的算法和一个时间复杂度较高的算法进行结果的比对，因为时间复杂度低的算法比较容易实现，当然一定要确保时间复杂度低的算法是流程和结果是对的。再用对数器比较时间复杂度低和时间复杂度高的算法的结果，如果两算法的结果不同，就说明时间复杂度低的算法的实现是错误的。(对数器能保证在不同的情况下、多次进行实验)。
二、对数器的定义
1.有一个你想要测的方法a；
2.实现一个绝对正确但是复杂度不好的方法b；
3.实现一个随机样本产生器；
4.实现对比算法a和b的方法；
5.把方法a和方法b比对多次来验证方法a是否正确；
6.如果有一个样本使得比对出错，打印样本分析是哪个方法出错；
7.当样本数量很多时比对测试依然正确，可以确定方法a已经正确。
三、利用案例理解对数器的作用
看下面这个例子：
题目要求：在一个数组中，只有一种数出现了k次，而其它的数都出现了m次，试找出这个出现了k次的数字。
首先，按照题目要求…出现了几次，并找出该数，则时间复杂度高的可以使用哈希表来进行存储与记录。此处直接贴代码：
public static int test(int[] arr,int k,int m) {
Map<Integer,Integer> map = new HashMap<>();
for(int num:arr) {
if(map.containsKey(num)) {
map.put(num,map.get(num)+1);
}else {
map.put(num,1);
}
}
for(int num:map.keySet()) {
if(map.get(num)==k) {
return num;
}
}
return -1;
}
再接着，实现一个自己要测的实现该题目的算法代码，相对于上面的代码时间复杂度要低。
简单来描述下面代码的操作：
因为只有一种数出现了k次，而其它数都出现了m次，那么从int的角度，有32位，用ans来记录k在某一位上的1，只要出现了k次的数，则在某个位置上一定存在1。就用数组来记录全部数字每一位的1，某个数出现了m次的，在某一位一定是有t[i]%m==0 ；否则就不能被k整除。
public static int FindInitNum(int[] arr,int k,int m) {
int[] t = new int[32];
for(int i=0;i<arr.length;i++) {
for(int j=0;j<=31;j++) {
t[j]+=(arr[i]>>j)&1;
}
}
int ans = 0;
for(int i=0;i<32;i++) {
if(t[i]%m!=0) {
if(t[i]%m==k) {
ans|=(1<<i);
}
}
}
return ans;
}
为了验证上面的算法是否正确，就要使用到对数器：
1.先准备好一个main方法，指定好要利用什么条件来产生一个数组和数组中包含的数字。因为要保证数字是随机的，会用到大量的产生随机数的方法。我们可以先设置数字的种类数、数字的大小范围、测试的次数。
2.根据本题要求，k一定是要小于m的，因此要保证这个前提条件，有了k和m之后，目标就是要创建一个数组包含某个数出现了k次，其它数出现m次的前提条件，只要该数组创建出来就完成任务了。
3.数组中种类数要确保大于等于2，若只有一种数就不行了。并且可以根据种类数来确定出数组的长度。每填入一种数后，要控制数的种类要-- ，当然，在随机创造出现m次的数时，不可避免的是可能会出现跟出现k次的数是相等的。为了避免这个问题就在下面代码的do while循环中解决了，并且要使用一个Set来保存记录。
4.最后，数组的数填完了，但是我们是每种数依次填入的，为了打乱顺序，可以使用随机生成的下标与遍历到的下面进行交换。最后返回该数组就完成任务了。
public static int[] randomArray(int maxKinds, int range, int k, int m) {
int ktimeNum = rangeNumber(range);
int numKinds = (int)(Math.random()*maxKinds)+2;
int[] arr = new int[k+(numKinds-1)*m];
int index = 0;
for (;index<k;index++) {
arr[index]=ktimeNum;
}
numKinds--;
Set<Integer> set = new HashSet<>();
set.add(ktimeNum);
while (numKinds!=0) {
int curNum = 0;
do {
curNum = rangeNumber(range);
}while (set.contains(curNum));
set.add(curNum);
numKinds--;
for(int i=0;i<m;i++) {
arr[index++]=curNum;
}
}
for(int i=0;i<arr.length;i++) {
int j = (int)(Math.random()*arr.length);
int tmp = arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
return arr;
}
public static int rangeNumber(int range) {
return ((int)(Math.random()*range)+1) - ((int)(Math.random()*range)+1);
}
public static void main(String[] args) {
int kinds = 10;
int range = 200;
int testTime = 100000;
int max = 9;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int a = (int)(Math.random()*max)+1;
int b = (int)(Math.random()*max)+1;
int k = Math.min(a,b);
int m = Math.max(a,b);
if(k==m) {
m++;
}
int[] arr = randomArray(kinds,range,k,m);
int ans1 = test(arr,k,m);
int ans2 = FindInitNum(arr,k,m);
if(ans1!=ans2) {
System.out.println(ans1);
System.out.println(ans2);
System.out.println("测试错误");
}
}
System.out.println("测试结束");
}
|