.Net 之时间轮算法(终极版)

关于时间轮算法的起始

我也认真的看了时间轮算法相关，大致都是如下的一个图

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述 个人认为的问题

大部分文章在解释这个为何用时间轮的时候都再说

为什么要用时间轮实现

1. 1. 通常用于实现linux内核任务、游戏类的buf计时。
2. 2. 单个时间轮局限性：保存的任务数量少，不能超过当前时间轮。
3. 3. 多层时间轮，典型：日-时-分-秒
4. 4. 传统JAVA实现定时：Timer，只能单线程，会阻塞；Executors.newScheduledThreadPoll, 使用的最小堆来实现，任务还是不能太多，添加时间复杂度为O(logn)

时间轮定时器最大的优点

1. 1. 是任务的添加与移除，都是O(1)级的复杂度；
2. 2. 不会占用大量的资源；
3. 3. 只需要有一个线程去推进时间轮就可以工作了

publicList<Task> getTaskList( longtimestamp) {

returntask. get(timestamp)

}

// 假装这里真的能一毫秒一个循环

publicvoidrun{

while( true){

getTaskList(System.currentTimeMillis).后台执行

Thread.sleep( 1);

}

}

假如这个数组长度达到了亿亿级，我们确实可以这么干。那如果将精度缩减到秒级呢？我们也需要一个百亿级长度的数组。

先不说内存够不够，显然你的定时器要这么大的内存显然很浪费。

对于以上的描述，我自己还是很不认同的，我为啥要声明这么大的数组，难道不能有一个任务，我就放一个任务么，实际数组的长度应该是你任务数的长度吧。

要不然，为啥要这么浪费。想不通，可能还有别的解释，谁有答案可以告诉我。

在实际的使用中，一般都为秒级，毫秒级都很少，因为毫秒级的不准。

所以，我可以根据这些通过hash字典构建一个 这样的时间轮算法，也作为我自己想实现定时任务框架的一部分。

逻辑：核心为一个字典，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