那些惊艳的算法—时间轮算法( 二 ) _时间轮算法

文章插图

同一时刻存在多个任务时，只要把该刻度对应的链表全部遍历一遍，执行（扔到线程池中异步执行）其中的任务即可。
时间刻度不够用怎么办？如果任务不只限定在一天之内呢？比如我有个任务，需要每周一上午九点执行，我还有另一个任务，需要每周三的上午九点执行。一种很容易想到的解决办法是：
增大时间轮的刻度一天24个小时，一周168个小时，为了解决上面的问题，我可以把时间轮的刻度（槽）从12个增加到168个，比如现在是星期二上午10点钟，那么下周一上午九点就是时间轮的第9个刻度，这周三上午九点就是时间轮的第57个刻度，示意图如下：

文章插图

仔细思考一下，会发现这种设计方式存在几个缺陷：
时间刻度太多会导致时间轮走到的多数刻度没有任务执行，比如一个月就2个任务，我得移动720次，其中718次是无用功。
时间刻度太多会导致存储空间变大，利用率变低，比如一个月就2个任务，我得需要大小是720的数组，如果我的执行时间的粒度精确到秒，那就更恐怖了。
于是乎，聪明的你脑袋一转，想到另一个办法：
列表中的任务中添加round属性这次我不增加时间轮的刻度了，刻度还是24个，现在有三个任务需要执行，
任务一每周二上午九点。
任务二每周四上午九点。
任务三每个月12号上午九点。
比如现在是9月11号星期二上午10点，时间轮转一圈是24小时，到任务一下次执行（下周二上午九点）,需要时间轮转过6圈后，到第7圈的第9个刻度开始执行。
任务二下次执行第3圈的第9个刻度，任务三是第2圈的第9个刻度。
示意图如下：

文章插图

时间轮每移动到一个刻度时，遍历任务列表，把round值-1，然后取出所有round=0的任务执行。
这样做能解决时间轮刻度范围过大造成的空间浪费，但是却带来了另一个问题：时间轮每次都需要遍历任务列表，耗时增加，当时间轮刻度粒度很小(秒级甚至毫秒级)，任务列表又特别长时，这种遍历的办法是不可接受的。
当然，对于大多数场景，这种方法还是适用的。
有没有既节省空间，又节省时间的办法呢？答案是有的，正如《Hashed and Hierarchical Timing Wheels》标题中提到的，有一种分层时间轮，可以解决做到既节省空间，又节省时间：
分层时间轮分层时间轮是这样一种思想：
针对时间复杂度的问题：不做遍历计算round，凡是任务列表中的都应该是应该被执行的，直接全部取出来执行。
针对空间复杂度的问题：分层，每个时间粒度对应一个时间轮，多个时间轮之间进行级联协作。
第一点很好理解，第二点有必要举个例子来说明：
比如我有三个任务：
任务一每周二上午九点。
任务二每周四上午九点。
任务三每个月12号上午九点。
三个任务涉及到四个时间单位：小时、天、星期、月份。
拿任务三来说，任务三得到执行的前提是，时间刻度先得来到12号这一天，然后才需要关注其更细一级的时间单位：上午9点。
基于这个思想，我们可以设置三个时间轮：月轮、周轮、天轮。
月轮的时间刻度是天。
周轮的时间刻度是天。
天轮的时间刻度是小时。
初始添加任务时，任务一添加到天轮上，任务二添加到周轮上，任务三添加到月轮上。
三个时间轮以各自的时间刻度不停流转。
当周轮移动到刻度2(星期二)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。
同理，当月轮移动到刻度12(12号)时，取出这个刻度下的任务，丢到天轮上，天轮接管该任务，到9点执行。
这样就可以做到既不浪费空间，又不浪费时间。
整体的示意图如下所示：