關(guān)于時(shí)間輪算法的起始
我也認(rèn)真的看了時(shí)間輪算法相關(guān)，大致都是如下的一個(gè)圖
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述 個(gè)人認(rèn)為的問(wèn)題
大部分文章在解釋這個(gè)為何用時(shí)間輪的時(shí)候都再說(shuō)
為什么要用時(shí)間輪實(shí)現(xiàn)
- 1. 通常用于實(shí)現(xiàn)linux內(nèi)核任務(wù)、游戲類(lèi)的buf計(jì)時(shí)。
- 2. 單個(gè)時(shí)間輪局限性：保存的任務(wù)數(shù)量少，不能超過(guò)當(dāng)前時(shí)間輪。
- 3. 多層時(shí)間輪，典型：日-時(shí)-分-秒
- 4. 傳統(tǒng)JAVA實(shí)現(xiàn)定時(shí)：Timer，只能單線(xiàn)程，會(huì)阻塞；Executors.newScheduledThreadPoll, 使用的最小堆來(lái)實(shí)現(xiàn)，任務(wù)還是不能太多，添加時(shí)間復(fù)雜度為O(logn)
時(shí)間輪定時(shí)器最大的優(yōu)點(diǎn)
- 1. 是任務(wù)的添加與移除，都是O(1)級(jí)的復(fù)雜度；
- 2. 不會(huì)占用大量的資源；
- 3. 只需要有一個(gè)線(xiàn)程去推進(jìn)時(shí)間輪就可以工作了
privateTask[很長(zhǎng)] tasks;
publicList<Task> getTaskList( longtimestamp) {
returntask. get(timestamp)
}
// 假裝這里真的能一毫秒一個(gè)循環(huán)
publicvoidrun{
while( true){
getTaskList(System.currentTimeMillis).后臺(tái)執(zhí)行
Thread.sleep( 1);
}
}
基于個(gè)人的理解對(duì)其進(jìn)行改造和實(shí)現(xiàn)假如這個(gè)數(shù)組長(zhǎng)度達(dá)到了億億級(jí)，我們確實(shí)可以這么干。那如果將精度縮減到秒級(jí)呢？我們也需要一個(gè)百億級(jí)長(zhǎng)度的數(shù)組。
先不說(shuō)內(nèi)存夠不夠，顯然你的定時(shí)器要這么大的內(nèi)存顯然很浪費(fèi)。
對(duì)于以上的描述，我自己還是很不認(rèn)同的，我為啥要聲明這么大的數(shù)組，難道不能有一個(gè)任務(wù)，我就放一個(gè)任務(wù)么，實(shí)際數(shù)組的長(zhǎng)度應(yīng)該是你任務(wù)數(shù)的長(zhǎng)度吧。
要不然，為啥要這么浪費(fèi)。想不通，可能還有別的解釋?zhuān)l(shuí)有答案可以告訴我。
在實(shí)際的使用中，一般都為秒級(jí)，毫秒級(jí)都很少，因?yàn)楹撩爰?jí)的不準(zhǔn)。
所以，我可以根據(jù)這些通過(guò)hash字典構(gòu)建一個(gè) 這樣的時(shí)間輪算法，也作為我自己想實(shí)現(xiàn)定時(shí)任務(wù)框架的一部分。
static void Main( string[] args)邏輯：核心為一個(gè)字典，key 為時(shí)間戳，值為任務(wù)列表。整體就是每個(gè)添加的任務(wù)都有一個(gè)觸發(fā)的時(shí)間（秒），到了這個(gè)秒，時(shí)間就會(huì)觸發(fā)，自然會(huì)去執(zhí)行相關(guān)的任務(wù)。有了任務(wù)才會(huì)添加，不會(huì)任何任務(wù)都添加的。任務(wù)觸發(fā)的時(shí)候，會(huì)獲取任務(wù)下一次執(zhí)行的時(shí)間，并插入到任務(wù)列表里。
{
ScheduledTask scheduledTask = newScheduledTask( => { Console.WriteLine( $" {DateTime.Now}" ); }, newTimeSpan( 0, 0, 5));
TimeWheel timeWheel = newTimeWheel;
timeWheel.AddTask(scheduledTask);
timeWheel.Run;
Console.WriteLine( "開(kāi)始運(yùn)行時(shí)間輪!");
Console.ReadLine;
} ///<summary>
///時(shí)間輪算法(終極)實(shí)現(xiàn)
///大部分都是支持秒級(jí)，所以，按照秒級(jí)進(jìn)行實(shí)現(xiàn)
///</summary>
publicclassTimeWheel
{
///<summary>
///任務(wù)列表
///</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>
///定時(shí)器任務(wù)，普通任務(wù)
///間隔指定的時(shí)間
///</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);
}
}
最后的效果
在這里插入圖片描述
當(dāng)然，也可以通過(guò)CRON表達(dá)式來(lái)實(shí)現(xiàn)更為高級(jí)的。
后期再來(lái)個(gè)更高級(jí)一點(diǎn)的。 github地址
https://github.com/kesshei/TimeWheelDemo
