.Net 之时间轮算法(终极版)
关于时间轮算法的起始
我也认真的看了时间轮算法相关，大致都是如下的一个图
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述 个人认为的问题
大部分文章在解释这个为何用时间轮的时候都再说
为什么要用时间轮实现
- 1. 通常用于实现linux内核任务、游戏类的buf计时。
- 2. 单个时间轮局限性：保存的任务数量少，不能超过当前时间轮。
- 3. 多层时间轮，典型：日-时-分-秒
- 4. 传统JAVA实现定时：Timer，只能单线程，会阻塞；Executors.newScheduledThreadPoll, 使用的最小堆来实现，任务还是不能太多，添加时间复杂度为O(logn)
时间轮定时器最大的优点
- 1. 是任务的添加与移除，都是O(1)级的复杂度；
- 2. 不会占用大量的资源；
- 3. 只需要有一个线程去推进时间轮就可以工作了
privateTask[很长] tasks;
publicList<Task> getTaskList( longtimestamp) {
returntask. get(timestamp)
}
// 假装这里真的能一毫秒一个循环
publicvoidrun{
while( true){
getTaskList(System.currentTimeMillis).后台执行
Thread.sleep( 1);
}
}
基于个人的理解对其进行改造和实现假如这个数组长度达到了亿亿级，我们确实可以这么干。那如果将精度缩减到秒级呢？我们也需要一个百亿级长度的数组。
先不说内存够不够，显然你的定时器要这么大的内存显然很浪费。
对于以上的描述，我自己还是很不认同的，我为啥要声明这么大的数组，难道不能有一个任务，我就放一个任务么，实际数组的长度应该是你任务数的长度吧。
要不然，为啥要这么浪费。想不通，可能还有别的解释，谁有答案可以告诉我。
在实际的使用中，一般都为秒级，毫秒级都很少，因为毫秒级的不准。
所以，我可以根据这些通过hash字典构建一个 这样的时间轮算法，也作为我自己想实现定时任务框架的一部分。
static void Main( string[] args)逻辑：核心为一个字典，key 为时间戳，值为任务列表。整体就是每个添加的任务都有一个触发的时间（秒），到了这个秒，时间就会触发，自然会去执行相关的任务。有了任务才会添加，不会任何任务都添加的。任务触发的时候，会获取任务下一次执行的时间，并插入到任务列表里。
{
ScheduledTask scheduledTask = newScheduledTask( => { Console.WriteLine( $" {DateTime.Now}" ); }, newTimeSpan( 0, 0, 5));
TimeWheel timeWheel = newTimeWheel;
timeWheel.AddTask(scheduledTask);
timeWheel.Run;
Console.WriteLine( "开始运行时间轮!");
Console.ReadLine;
} ///<summary>
///时间轮算法(终极)实现
///大部分都是支持秒级，所以，按照秒级进行实现
///</summary>
publicclassTimeWheel
{
///<summary>
///任务列表
///</summary>
publicConcurrentDictionary< long, List<IScheduledTask>> Tasks = new;
publicvoidRun
{
while( true)
{
varnow = DateTime.Now;
Task.Run( => { Trigger(now); });
varoffset = 500- now.Millisecond;
SpinWait.SpinUntil( => false, 1000+ offset);
}
}
publicvoidTrigger(DateTime dateTime)
{
vartimeStamp = GenerateTimestamp(dateTime);
varoldTimeStamp = timeStamp - 1;
Tasks.TryRemove(oldTimeStamp, outvar_);
Tasks.TryGetValue(timeStamp, outvarresult);
if(result?.Any == true)
{
foreach( varitem inresult)
{
Task.Run(item.GetAction);
varNewTime = item.GetNextTime;
if(NewTime.HasValue)
{
AddTask(NewTime.Value, item);
}
}
}
}
publicvoidAddTask(IScheduledTask scheduledTask)
{
vartimeStamp = GenerateTimestamp(scheduledTask.GetNextTime.Value);
Tasks.AddOrUpdate(timeStamp, newList<IScheduledTask> { scheduledTask }, (k, v) =>
{
v.Add(scheduledTask);
returnv;
});
}
publicvoidAddTask(DateTime dateTime, IScheduledTask scheduledTask)
{
vartimeStamp = GenerateTimestamp(dateTime);
Tasks.AddOrUpdate(timeStamp, newList<IScheduledTask> { scheduledTask }, (k, v) =>
{
v.Add(scheduledTask);
returnv;
});
}
privatelongGenerateTimestamp(DateTime dateTime)
{
returnnewDateTimeOffset(dateTime.ToUniversalTime).ToUnixTimeSeconds;
}
privateDateTime GetDatetime( longtimeStamp)
{
vard = DateTimeOffset.FromUnixTimeSeconds(timeStamp);
returnd.LocalDateTime;
}
} publicinterfaceIScheduledTask
{
publicAction GetAction;
publicDateTime? GetNextTime;
}
///<summary>
///定时器任务，普通任务
///间隔指定的时间
///</summary>
publicclassScheduledTask: IScheduledTask
{
privateAction _action;
privateTimeSpan timeSpan;
publicScheduledTask(Action action, TimeSpan timeSpan)
{
this._action = action;
this.timeSpan = timeSpan;
}
publicAction GetAction
{
returnthis._action;
}
publicDateTime? GetNextTime
{
returnDateTime.Now.AddSeconds(timeSpan.TotalSeconds);
}
}
最后的效果
在这里插入图片描述
当然，也可以通过CRON表达式来实现更为高级的。
后期再来个更高级一点的。 github地址
https://github.com/kesshei/TimeWheelDemo
