當(dāng)年我還是個(gè)學(xué)生的時(shí)候，有一次去參加歡聚時(shí)代的一個(gè)面試，有一道面試題記憶尤新，讓你來實(shí)現(xiàn)一個(gè)定時(shí)任務(wù)，你會怎么做?為了簡化問題，我們只用考慮內(nèi)存方案，不用考慮數(shù)據(jù)持久化。

數(shù)組法

最簡單的，我們可以把所有的任務(wù)存放在一個(gè)數(shù)組里面，然后，每隔單位時(shí)間遍歷整個(gè)數(shù)組，找到是否有任務(wù)滿足當(dāng)前時(shí)間，如果有，那么從數(shù)組中取出，然后執(zhí)行。每隔單位時(shí)間查詢算法復(fù)雜度為O(N)。

那么，新增一個(gè)任務(wù)怎么操作呢?我們只要簡單地往數(shù)組中追加一個(gè)元素即可，算法時(shí)間復(fù)雜度為O(1)

[[278610]]

優(yōu)先隊(duì)列法

評估一個(gè)算法，我們既要考慮它的查詢算法復(fù)雜度，也要考慮他的插入算法復(fù)雜度。在定時(shí)任務(wù)場景中，很顯然，查詢場景是非常多的。幾乎我們每個(gè)單位時(shí)間都要輪詢一遍，那么我們有沒有優(yōu)化算法的可能呢?

我們每次查詢，都只要查詢時(shí)間最接近當(dāng)前時(shí)間的，時(shí)間比當(dāng)前時(shí)間更早的，肯定被我們丟棄了。所以這個(gè)題目，等價(jià)于我們查詢隊(duì)列里面時(shí)間最小的。我們不禁想到一個(gè)熟悉的數(shù)據(jù)結(jié)構(gòu)，優(yōu)先隊(duì)列!活著我們可以使用一個(gè)小根堆進(jìn)行實(shí)現(xiàn)。

每次我們插入一個(gè)新的定時(shí)任務(wù)，我們將一個(gè)任務(wù)插入優(yōu)先隊(duì)列，每次插入的時(shí)候，隊(duì)列內(nèi)部需要進(jìn)行調(diào)整，算法時(shí)間復(fù)雜度為O(logN)。值得注意的是，在討論算法時(shí)間復(fù)雜度的時(shí)候，logN是Base2的，也就是說，如果N等于8的時(shí)候，logN就是3。

同理，雖然我們可以在O(1)的時(shí)間里面找到時(shí)間最小的任務(wù)，但是如果我們?nèi)〕鲞@個(gè)元素，優(yōu)先隊(duì)列需要做內(nèi)部的調(diào)整，這個(gè)算法時(shí)間復(fù)雜度也是O(logN)的。

時(shí)間輪法

上述優(yōu)先隊(duì)列的算法，綜合算法時(shí)間復(fù)雜度是O(logN)的，已經(jīng)很高效了，但是在我們大并發(fā)的分布式系統(tǒng)下，這個(gè)速度，還是太慢了。我們有沒有更高效的算法呢?

那便是時(shí)間輪算法，時(shí)間輪是一個(gè)環(huán)形隊(duì)列，按照時(shí)間的單位區(qū)分，我們假設(shè)1秒，每個(gè)單位里面，是一個(gè)鏈表，用來存儲定時(shí)任務(wù)。

可能你會問，一個(gè)環(huán)形隊(duì)列里面的元素，畢竟是優(yōu)先的，如果超過了長度，我們該怎么辦呢?我們可以聯(lián)想到我們家里的水表，是不是也有很多個(gè)輪子，每一個(gè)輪子的單位不一樣!

同樣，時(shí)間輪也是如此，我們可以用多級時(shí)間輪進(jìn)行優(yōu)化，就跟我們的時(shí)鐘或者水表一樣，這一層的走了一圈，下一層的才走了一格。

那么，這個(gè)算法的 時(shí)間復(fù)雜度怎么計(jì)算呢?插入的時(shí)候，我們從低層開始查找，找到在哪一層，然后直接插入對應(yīng)的刻度。假如我們的時(shí)間輪有5層，那么我們最多查找5次。

查詢的時(shí)候，我們每一秒都是推動時(shí)間輪的滾動，每次都是直接取隊(duì)首的元素，相當(dāng)于算法時(shí)間復(fù)雜度為O(1)。當(dāng)轉(zhuǎn)了一圈的時(shí)候，把下一層的下一格再推下來。這樣子，我們一個(gè)元素，最多會從第5層，逐漸插到第1層，綜合下來一個(gè)元素最多會被插入5次，在算法時(shí)間復(fù)雜度評估的時(shí)候，我們通常會忽略常數(shù)，最終算法時(shí)間復(fù)雜度為O(1)。

總結(jié)

一個(gè)非常簡單的面試題，竟然有好幾種不同的解法。這才是算法與數(shù)據(jù)結(jié)構(gòu)的魅力，歡迎大家關(guān)注我，共同學(xué)習(xí)，共同進(jìn)步。大家的支持是我繼續(xù)嘮嗑的動力。