大家好,又见面了,我是你们的朋友全栈君。
也是用来作定时器触发任务,只是他更高效,时间复杂度为O(1)。
为了方便理解我们参考钟表,它分为3个层次:时、分、秒,只有秒针在运动,走动一格时间为1秒,走一圈为1分钟,分针走一圈为1小时。 同样的,时间轮也分为多层,同样的只有第一层在运动,第一层走完,第二层走一格,第二层走完,第三次走一格,依次类推!!! 这样做就能用几个数组,代表一段较长的时间区间,左下图能计算0 – 135( 5333 ),如果将层1数组长度设置为60,第二层设置为60,第三层设置12,第四层去掉,则就是右下图的时钟了,时间区间为 0 – 42200(6060*12)秒
举个简单的4层时间轮例子(如左上图),假设最小计时单位为1(姑且理解为秒) 时间轮初始为0,那么给定任意时间time,求time落在每层时间轮的索引! 显然这是一个数学关系: 第一层:int first_index = time%5 第二层: int sencond_index = time/5 % 3 第三层: int third_index = time/5/3%3 第四层: int forth_index = time/5/3/3%3 如果不是很理解,可以举时钟的例子,假设当前时间为 3820 秒,求时分秒指针在哪个位置? 显然: 秒:3820%60 = 40 分:3820/60%60 = 3; 时:3820/60/60%12 = 1;
时间轮是由多个定长数组组成的,我们只需要把事件接在数组中就可以了,由于同一时刻会有多个事件,考虑先添加的事件先执行,使用链表来把事件连接起来,因此时间轮是一个 定长的包含链表的数组
只要知道了时间,就能得到给定的时间所在的层数与索引,就能找到该位置对应的事件链表,然后把事件添加进去
为了方便说明,依然以下图为例,以time作为从0开始时间,单位为秒,每过一秒 time+1。 事件执行永远只在1层,每过1秒数组索引右移一位,同时执行该数组里面的事件,执行完后删除事件,完整遍历后,需要把2层的事件更新到1层来执行,2层的事件都执行完后,需要把3层的事件更新到1、2,依此类推,直到最后一层。事件更新后又回到起始位置进行新一轮的事件执行过程。 显然,任务执行的过程很容易理解,用time对5求余就能知道事件执行到了那一刻,那么何时分发呢?注意看下图标红部分,因为举的例子层数和每层的数组长度都很少,先不考虑第四次,很容易知道当time等于 5、10、15、20、25、30、35、40、45时需要先分发事件在执行,不难看出: time% 5 == 0 时需要找把2层的事件更新到1层 (5) time%15 == 0 时需要找把3层的事件更新到2、1层 (53) time%45 == 0 时需要找把4层的事件更新到3、2、1层 (53*3) … **注意:**时间轮会有自己的最大计时区间,区间范围取决于时间轮层数及每层数组的大小,下图只有135秒的计时范围
以我自己的demo为例。 数据结构: 1、定义任务节点,组成任务链,节点应该包含需要执行的任务和任务执行的时间(以时间轮为起始点的时间) 2、定长链表数组,组成多层轮子,链表的节点为1定义的节点 3、定义时间变量,记录时间轮从起始时刻到当前的时间 成员函数: 1、增加节点函数 2、任务执行函数 3、数据更新函数(主要是为了从下层时间轮拿任务节点) 源代码有注释 头文件
//任务节点
class Node{
public:
qint64 expire = 0;
Node *next = nullptr;
};
//任务节点链表
class NodeList{
public:
Node head;
Node *tail = nullptr;
};
class TimeWheel
{
public:
TimeWheel();
const static qint64 FIRST_MAST = 8;
const static qint64 EACH_MAST = 6;
const static qint64 WHEEL_LEVEL = 5;
const static qint64 v = 1;
const static qint64 WHEEL_EACH_NUM = v<<EACH_MAST;
const static qint64 WHEEL_FIRST_NUM = (v<<FIRST_MAST);
//定长链表数组
NodeList first_wheel[WHEEL_FIRST_NUM];
NodeList other_level_wheel[WHEEL_LEVEL-1][WHEEL_EACH_NUM];
void addNodeInList(NodeList&,Node*node);
Node* clearNodeList(NodeList&);
void dispatchNode(NodeList&);
qint64 curtime;//单位为时间轮的单位刻度
void checkWheelUpdate();//数据更新函数
void addNode(Node *node);//添加节点函数
void addNode(int expire);
void execScale();
void execTask();//任务执行函数
};
#endif // TIMEWHEEL_H
源文件
#include "timewheel.h"
#include <QDebug>
TimeWheel::TimeWheel()
{
curtime = 0;
qDebug()<<"WHEEL_FIRST_NUM:"<<WHEEL_FIRST_NUM;
qDebug()<<"WHEEL_EACH_NUM:"<<WHEEL_EACH_NUM;
}
void TimeWheel::addNodeInList(NodeList&list,Node*node)
{
if(list.head.next == nullptr){
list.head.next = node;
list.tail = node;
}else{
list.tail->next = node;
list.tail = node;
}
}
void TimeWheel::addNode(int expire)
{
Node *node = new Node;
node->expire = curtime + expire;
node->next = nullptr;
addNode(node);
}
/* 注意节点的expire时间用来确认事件应该放在数组的哪个位置 delay 用来判断在哪层时间轮 */
void TimeWheel::addNode(Node *node)
{
int t = node->expire;
int delay = node->expire - curtime;
int index = 0;
if(delay < WHEEL_FIRST_NUM){
index = t % WHEEL_FIRST_NUM;
addNodeInList(first_wheel[index],node);
}else if(delay < WHEEL_EACH_NUM * WHEEL_FIRST_NUM){
index = t/ WHEEL_FIRST_NUM%WHEEL_EACH_NUM;
addNodeInList(other_level_wheel[0][index],node);
}else if(delay < WHEEL_EACH_NUM*WHEEL_EACH_NUM * WHEEL_FIRST_NUM){
index = t/ (WHEEL_EACH_NUM * WHEEL_FIRST_NUM)%WHEEL_EACH_NUM;
addNodeInList(other_level_wheel[1][index],node);
}else if(delay < WHEEL_EACH_NUM * WHEEL_FIRST_NUM){
index = t/ (WHEEL_EACH_NUM *WHEEL_EACH_NUM * WHEEL_FIRST_NUM)%WHEEL_EACH_NUM;
addNodeInList(other_level_wheel[2][index],node);
}else if(delay < WHEEL_EACH_NUM * WHEEL_FIRST_NUM){
index = t/ (WHEEL_EACH_NUM *WHEEL_EACH_NUM *WHEEL_EACH_NUM * WHEEL_FIRST_NUM)%WHEEL_EACH_NUM;
addNodeInList(other_level_wheel[3][index],node);
}
}
void TimeWheel::dispatchNode(NodeList& list)
{
Node *curnode = list.head.next;
//将节点分发时,需要清楚当前链表上的节点
list.head.next = nullptr;
list.tail = &list.head;
while (curnode != nullptr) {
Node *tmpnode = curnode;
curnode = curnode->next;
//因为添加节点时要保证节点为1个,而不是一个链表
//固将链表的连接点打断
tmpnode->next = nullptr;
addNode(tmpnode);
}
}
Node* TimeWheel::clearNodeList(NodeList&list)
{
Node*node = list.head.next;
list.head.next = nullptr;
list.tail = &list.head;
return node;
}
void TimeWheel::execTask(){
int index = curtime % WHEEL_FIRST_NUM;
Node *curnode = clearNodeList(first_wheel[index]);
while (curnode != nullptr) {
//执行定时节点任务
qDebug()<<"expire time:"<<curnode->expire;
Node *nextnode = curnode->next;
delete curnode;
curnode = nextnode;
}
}
void TimeWheel::execScale()
{
execTask();//执行任务
checkWheelUpdate();//检测更新
curtime++;//时间刻度更新
}
void TimeWheel::checkWheelUpdate()
{
qint64 dispatch_radio = WHEEL_FIRST_NUM;
qint64 dispatch_mask = curtime % dispatch_radio;
qint64 tmpa = WHEEL_FIRST_NUM;
int level = 0;
while(curtime != 0 && dispatch_mask == 0){
dispatch_radio *= WHEEL_EACH_NUM;
dispatch_mask = curtime % dispatch_radio ;
if(dispatch_mask == 0 ){
//如果整除,则往下一层找
level++;
tmpa *= WHEEL_EACH_NUM;
continue;
}
int index = curtime/tmpa%WHEEL_EACH_NUM;
dispatchNode(other_level_wheel[level][index]);
}
}
由于时间轮每层的数组的长度可以定义为任何值,并且时间轮涉及到了很多乘法和除法和取余,所以可以考虑使用位运算来替代运行。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/187298.html原文链接:https://javaforall.cn