学会对数器,自己测试代码!
Coding后找不到在线测试?学会自己写对数器,帮你调试出完全正确的代码!
我们敲完代码后可能并不是任何时候都能找到合适的在线测试来检测代码是否正确,而自己调试可能不敢保证代码的健壮性,因此学会对数器的使用就显得非常重要了。
接下来我将用一个简单选择排序算法,给大家演示对数器的原理以及如何写出自己需要的对数器。
首先,对数器是用来干什么的呢?简单来说,对于任意一个问题,我们一般都会有至少两种不同的解法,也就是一个想起来很简单,并且完全正确但是运行效率较低的解法和一个不容易想到,正确性未知但是运行效率比较高的解法,而我们要用的对数器,就是让同样的随机测试用例,用两种算法来跑,当测试用例非常大时(例如500000组),如果两组算法得出的结果相同,那我们就有理由认为我们想出的新解法是完全正确的,是不是感觉比在线测试得出的结论更加有说服力呢?话不多说我们来看代码(在这里我用的是Java):
以简单选择排序为例:
首先写出我们写出的算法(上文中那个“不容易想到,正确性未知但是运行效率比较高的解法”)
public static void selectionSort(int [] arr)
{
if(arr == null || arr.length<2)
return;
//0-N-1;找到最小值,找到后放在0位置上
for(int i=0;i<arr.length-1;i++)
{
int minIndex = i;
for(int j=i+1;j<arr.length;j++)
minIndex = arr[j]<arr[minIndex]?j:minIndex;
swap(arr,i,minIndex);
}
}
public static void swap(int[] arr,int i,int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
那我们想写对数器来测这个算法的正确性,这里我选择Java自带的Arrays.sort()方法 (上文中那个想起来很简单,并且完全正确但是运行效率较低的解法)
//For Test:
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
接下来的工作就是让完全随机的多组数同时在两个算法里运行,如果排序后每组数两个算法得出的结果都相同,则输出Nice!
//For Test:产生随机测试数组若干组
public static int[] generateRandomArray(int maxSize,int maxValue) {
int[] arr = new int[(int)((maxSize+1)*Math.random())];
//Math.random方法得到一个[0,1)的小数
//(maxSize+1)*Math.random() ----->[0,N+1) == [0,N]
//数组最大容量和内部最大值都采用随机生成
for(int i=0;i<arr.length;i++)
{
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
//ForTest:copy生成的随机数组
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;
}
//for Test:判断两种算法运行后,两个数组排序是否相同
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;
}
// 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();
}
//For Test :主函数测试函数正确性
public static void main(String[] args)
{
int testTime = 500000; //用例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);
selectionSort(arr1);
comparator(arr2);
if(!isEqual(arr1, arr2))
{
succeed = false;
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
//随机数列排序过程
int[] arr = generateRandomArray(maxSize, maxValue);
printArray(arr);
selectionSort(arr);
printArray(arr);
}
看到这里应该很理解对数器了吧,针对不同的算法,大家可以写出不同的对数器,以检测让自己的代码能做到万无一失哦!
本文地址:https://blog.csdn.net/weixin_45438935/article/details/112686201
上一篇: 【MQ】消息队列及常见MQ比较
下一篇: Java-sha256解密工具类