首页 > > 网页制作 > Javascript >

JS实现对数器

2018-08-10 11:20:59来源：博客园阅读 ()

对数器的概念和使用

对数器一般用于验证你写的算法是否正确，因为自己写的测试用例可能写的考虑不够全面。

0.有一个你想测试的方法a

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

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

3.实现比对的方法

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

5.如果有一个样本比对出错，打印样本分析是哪个方法出错

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

举例代码

假设我们需要测试我们自己写的插入排序

//要测试的方法
function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
    }
}
//正确的方法
function rightMethod(arr) {
    arr.sort((a, b)=>a - b);
}
//随机数组生成器，size为最大长度，value为最大值
function generateRandomArray(size, value) {
    //生成长度随机的数组
    let arr = new Array(Math.floor((size + 1) * Math.random()));
    for (let i = 0; i < arr.length; i++) {
        arr[i] = Math.floor((value + 1) * Math.random());
    }
    return arr;
}
//拷贝数组方法
function copyArray(arr) {
    if (arr == null) {
        return null;
    }
    return [].concat(arr);
}
//比对方法
function isEqual(arr1, 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 (let i = 0; i < arr1.length; i++) {
        if (arr1[i] != arr2[i]) {
            return false
        }
    }
    return true;
}
//测试
function Test() {
    let testTimes = 5000;
    let size = 10;
    let value = 100;
    let succeed = true;
    for (let i = 0; i < testTimes; i++) {
        let arr1 = generateRandomArray(size, value);
        let arr2 = copyArray(arr1);
        let arr3 = copyArray(arr1);
        insertSort(arr1);
        rightMethod(arr2);
        if (!isEqual(arr1, arr2)) {
            succeed = false;
            console.log(arr3);
            break;
        }
    }
    console.log(succeed ? "nice" : "Fucking fucked");
}
Test();