电子商务网站建设与全程实例,成都有哪些做公司网站的公司,西安 网站建设 培训学校,什么网站帮人做网页当年我还是个学生的时候#xff0c;有一次去参加欢聚时代的一个面试#xff0c;有一道面试题记忆尤新#xff0c;让你来实现一个定时任务#xff0c;你会怎么做#xff1f;为了简化问题#xff0c;我们只用考虑内存方案#xff0c;不用考虑数据持久化。数组法最简单的有一次去参加欢聚时代的一个面试有一道面试题记忆尤新让你来实现一个定时任务你会怎么做为了简化问题我们只用考虑内存方案不用考虑数据持久化。数组法最简单的我们可以把所有的任务存放在一个数组里面然后每隔单位时间遍历整个数组找到是否有任务满足当前时间如果有那么从数组中取出然后执行。每隔单位时间查询算法复杂度为O(N)。那么新增一个任务怎么操作呢我们只要简单地往数组中追加一个元素即可算法时间复杂度为O(1)优先队列法评估一个算法我们既要考虑它的查询算法复杂度也要考虑他的插入算法复杂度。在定时任务场景中很显然查询场景是非常多的。几乎我们每个单位时间都要轮询一遍那么我们有没有优化算法的可能呢我们每次查询都只要查询时间最接近当前时间的时间比当前时间更早的肯定被我们丢弃了。所以这个题目等价于我们查询队列里面时间最小的。我们不禁想到一个熟悉的数据结构优先队列活着我们可以使用一个小根堆进行实现。每次我们插入一个新的定时任务我们将一个任务插入优先队列每次插入的时候队列内部需要进行调整算法时间复杂度为O(logN)。值得注意的是在讨论算法时间复杂度的时候logN是Base2的也就是说如果N等于8的时候logN就是3。同理虽然我们可以在O(1)的时间里面找到时间最小的任务但是如果我们取出这个元素优先队列需要做内部的调整这个算法时间复杂度也是O(logN)的。时间轮法上述优先队列的算法综合算法时间复杂度是O(logN)的已经很高效了但是在我们大并发的分布式系统下这个速度还是太慢了。我们有没有更高效的算法呢那便是时间轮算法时间轮是一个环形队列按照时间的单位区分我们假设1秒每个单位里面是一个链表用来存储定时任务。可能你会问一个环形队列里面的元素毕竟是优先的如果超过了长度我们该怎么办呢我们可以联想到我们家里的水表是不是也有很多个轮子每一个轮子的单位不一样同样时间轮也是如此我们可以用多级时间轮进行优化就跟我们的时钟或者水表一样这一层的走了一圈下一层的才走了一格。那么这个算法的 时间复杂度怎么计算呢插入的时候我们从最低层开始查找找到在哪一层然后直接插入对应的刻度。假如我们的时间轮有5层那么我们最多查找5次。查询的时候我们每一秒都是推动时间轮的滚动每次都是直接取队首的元素相当于算法时间复杂度为O(1)。当转了一圈的时候把下一层的下一格再推下来。这样子我们一个元素最多会从第5层逐渐插到第1层综合下来一个元素最多会被插入5次在算法时间复杂度评估的时候我们通常会忽略常数最终算法时间复杂度为O(1)。总结一个非常简单的面试题竟然有好几种不同的解法。这才是算法与数据结构的魅力欢迎大家关注我共同学习共同进步。大家的支持是我继续唠嗑的动力。同名公众号(沙茶敏碎碎念)
