關于時間輪算法的起始
我也認真的看了時間輪算法相關，大致都是如下的一個圖
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述 個人認為的問題
大部分文章在解釋這個為何用時間輪的時候都再說
為什么要用時間輪實現
- 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
