算法笔试利器--对数器的使用

wyk1184 发布于2019-08-16 13:37 / 812人阅读

摘要：对于一个数组的排序，如果笔试中要求的时间复杂度是，但是你却写了一个冒泡排序的算法交上去了，这时就会提示而在对数器中，我们要求的绝对正确的算法是没有时间和空间复杂度的限制的，唯一的要求是确保绝对正确。

对数器的作用

对数器是通过用大量测试数据来验证算法是否正确的一种方式。在算法笔试的时候，我们经常只能确定我们写出的算法在逻辑上是大致正确的，但是谁也不能一次性保证绝对的正确。特别是对于一些复杂的题目，例如贪心算法，我们往往无法在有限时间内用数学公式来推导证明我们程序的正确性。而且在线的OJ一般只会给出有数的几个简单的samples，可能我们的算法在这些简单的samples偶然通过了，但是在一些复杂的samples处却出现了问题。这时我们无法使用复杂的samples来分析调试我们的代码，人工设计样例来测试代码的效率又太低，而且不能确保考虑各种特殊情况。因此，能随机产生不同情况的数据的对数器就派上了用场。

对数器，简而言之，就是一个绝对正确的方法和能产生大量随机样例的随机器的组合。看到这里，有些童鞋有疑问了。既然我们知道了绝对正确的方法，直接用这个方法不就好了嘛？

请注意，算法追求的不是解决问题，而是高效率的解决问题。对于一个数组的排序，如果笔试中要求的时间复杂度是$O(NlogN)$$，但是你却写了一个冒泡排序的算法交上去了，这时OJ就会提示：

Time Limit Exceeded

而在对数器中，我们要求的绝对正确的算法是没有时间和空间复杂度的限制的，唯一的要求是确保绝对正确。因为只有绝对正确，我们才能通过样例的比对，发现我们的代码是在哪里出了错误。

相关概念

有一个你想要测的方法a；

实现一个绝对正确但是复杂度不好的方法b；

实现一个随机样本产生器；

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

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

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

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

其中要注意以下几点：

随机产生的样本应该是小数据集，但是要进行多次(10w+)的对比。小数据集是因为方便对比分析，多次比对是要覆盖所有的随机情况。

算法b要保持正确性。

示例

冒泡排序的对数器：

要测的方法

public static void bubbleSort(int[] arr)
{
    if (arr==null || arr.length < 2)
        return;
    for (int end = arr.length - 1;end>0; end--)
    {
        for (int i = 0; i < end; i++)
        {
            if (arr[i] > arr[i+1])
                swap(arr, i, i+1);
        }
    }
}

实现一个绝对正确，可以复杂度不是很好的方法b

// 可以直接用一些库函数来进行测试
public static void rightMethod(int[] arr)
{
    Arrays.sort(arr);
}

实现一个随机样本产生器

// 随机数生成器
public static int[] generateRandomArray(int size, int value)
{
//Math.random() -> double [0,1)
//(int) ((size + 1) * Math.random()) -> [0,size]整数
// 生成长度随机[0, size]的数组
int[] arr = new int[(int) ((size+1) * Math.random())];
for (int i = 0; i < arr.length; i++)
{
    // 一个随机数减去另一个随机数，生成[-value, value]的随机数
    arr[i] = (int) ((value+1) * Math.random()) - (int) (value * Math.random());
}
return arr;
}

实现比对的方法

// 判断两个数组是否相等
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;
}

将方法a和方法b进行多次的比对

如果有一个样本使得本次比对出错，则打印该样本，分析方法错在哪里

当样本数量足够多时，比对测试依然正确，则可以确定我们写的方法a是正确的

public static void main(String[] args) 
{
    int testTime = 500000;
    int size = 10;
    int value = 100;
    boolean succeed = true;
    for (int i = 0; i < testTime; i++)
    {
        int[] arr1 = generateRandomArray(size, value);
        int[] arr2 = copyArray(arr1);
        int[] arr3 = copyArray(arr1);
        bubbleSort(arr1);
        rightMethod(arr2);
        if (!isEqual(arr1, arr2))
        {
            succeed = false;
            printArray(arr3);
            break;
        }
    }
    System.out.println(succeed ? "Nice!" : "error----");
    int[] arr = generateRandomArray(size, value);
    printArray(arr);
    bubbleSort(arr);
    printArray(arr);

}

小提示

很多童鞋进行笔试前，都是背一些记在小本本上的代码，然后匆匆上阵。写出的算法的正确性完全靠OJ的判断，当程序卡在一个2000行的数组样例处出现错误时，就完全傻了......这T喵叫我怎么去进行调试分析啊。而有对数器的小伙伴就不一样了，由于使用的都是小样本，出现错误时也方面进行分析。而且进行了多次测试，确保覆盖了所有的特殊情况。因此笔试前我们可以准备一些对数器模版，如数组排序的对数器，链表的对数器等等。后续我也会更新一些对数器的模版，有java版本和python版本。

记住哦，offer都是留给有准备的人~~

数组排序

Java版本

后续版本，陆续更新中.....

GPU云服务器云服务器自然对数e的算法服务器管理器的使用 java怎么使用对数分析利器

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72031.html

2019网易互娱数据挖掘实习生笔试部分记录

摘要：今晚做完了网易互娱数据挖掘实习生的笔试题，虽然大部分的题目都不太记得了。采样分为上采样和下采样。上采样是把小众类复制多份下采样是从大众类中剔除一些样本，或者说只从大众类中选取部分样本。今晚做完了网易互娱数据挖掘实习生的笔试题，虽然大部分的题目都不太记得了。但是还是有一些印象比较深的坑需要填一下。比起腾讯和字条跳动难度适中，不算很大，字节的笔试挂了。其实这次感觉自己做的也不是挺好哈哈哈...

Meils 2019-07-31 10:15 评论0 收藏0
令人拍案叫绝的Wasserstein GAN

摘要：测度是高维空间中长度面积体积概念的拓广，可以理解为超体积。前作其实已经针对第二点提出了一个解决方案，就是对生成样本和真实样本加噪声，直观上说，使得原本的两个低维流形弥散到整个高维空间，强行让它们产生不可忽略的重叠。在GAN的相关研究如火如荼甚至可以说是泛滥的今天，一篇新鲜出炉的arXiv论文《Wasserstein GAN》却在Reddit的Machine Learning频道火了，连Go...

lieeps 2019-04-25 18:08 评论0 收藏0
【天赢金创】算法复杂度分析

摘要：示例代码斐波那契数列复制代码复制代码这里，给定规模，计算所需的时间为计算的时间和计算的时间的和。示例代码复制代码复制代码同样是斐波那契数列，我们使用数组来存储计算结果，这样算法复杂度优化为。算法适用于少量数据的排序，时间复杂度为。原文：http://www.cnblogs.com/gaochundong/p/complexity_of_algorithms.html为什么要进行算法分...

NikoManiac 2019-06-27 11:34 评论0 收藏0
回溯算法讲解--适用于leetcode绝大多数回溯题目

摘要：什么是回溯算法回溯法是一种系统搜索问题解空间的方法。解空间定义为与数字长度相同。最后，为什么要掌握回溯法因为懂了回溯法之后笔试里的很多题就算不了，起码成功运行到之间是没问题的。什么是回溯算法？回溯法是一种系统搜索问题解空间的方法。为了实现回溯，需要给问题定义一个解空间。说到底它是一种搜索算法。只是这里的搜索是在一个叫做解空间的地方搜索。而往往所谓的dfs，bfs都是在图或者树这种数据...

saucxs 2019-08-16 15:23 评论0 收藏0