对数器

对数器能够快速在本地检验一种算法的准确行

说明：对数器可以说是验证算法是否正确的一种方式。尤其是在笔试的时候，用贪心算法写出的程序，暂时无法用数学公式严格推导证明，只能通过大量的数据集验证算法的正确性。而大量的数据集当中要包括各种情况，各个方面都要考虑到，对我们自己来说，有时会考虑不周，而且又是在时间紧迫的情况下。所以对数器就派上了用场。

概念：

有一个你想测试的算法a

实现一个绝对正确但复杂度高的算法b

实现一个随机样本产生器

实现比对算法a和b的方法

多次（100000+）比对a和b来验证a是否正确

如果有样本出错，则打印出来分析

当对此对比测试都正确时，可以基本判断算法a正确

public class LogarithmicDetector {
    public static void main(String[] args) {
        int maxSize = 1000;
        int maxValue = 100;
        int cycles = 20000;
        boolean succeed = true;
        for (int i = 0; i < cycles; i++) {
            int[] array1 = CreateRandomArray(maxSize, maxValue);
            int[] array2 = copyArray(array1);
            Quicksort.sort(array1);
            Arrays.sort(array2);
            if (!isEqual(array1, array2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed);
    }

    private static boolean isEqual(int[] array1, int[] array2) {
        for (int i = 0; i < array1.length; i++) {
            if (array1[i] != array2[i]) {
                return false;
            }
        }
        return true;
    }

    private static int[] copyArray(int[] array1) {
        int[] arr = new int[array1.length];
        for (int i = 0; i < array1.length; i++) {
            arr[i] = array1[i];
        }
        return arr;
    }

    public static int[] CreateRandomArray(int maxSize, int maxValue) {
        int arraySize = (int) ((maxSize + 1) * Math.random());
        int[] arr = new int[arraySize];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = ((int) ((maxValue + 1) * Math.random())) - ((int) ((maxValue + 1) * Math.random()));
        }
        return arr;
    }

}