當年我還是個學生的時候，有一次去參加歡聚時代的一個面試，有一道面試題記憶尤新，讓你來實現(xiàn)一個定時任務，你會怎么做?為了簡化問題，我們只用考慮內(nèi)存方案，不用考慮數(shù)據(jù)持久化。
數(shù)組法
最簡單的，我們可以把所有的任務存放在一個數(shù)組里面，然后，每隔單位時間遍歷整個數(shù)組，找到是否有任務滿足當前時間，如果有，那么從數(shù)組中取出，然后執(zhí)行。每隔單位時間查詢算法復雜度為O(N)。
那么，新增一個任務怎么操作呢?我們只要簡單地往數(shù)組中追加一個元素即可，算法時間復雜度為O(1)
優(yōu)先隊列法
評估一個算法，我們既要考慮它的查詢算法復雜度，也要考慮他的插入算法復雜度。在定時任務場景中，很顯然，查詢場景是非常多的。幾乎我們每個單位時間都要輪詢一遍，那么我們有沒有優(yōu)化算法的可能呢?
我們每次查詢，都只要查詢時間最接近當前時間的，時間比當前時間更早的，肯定被我們丟棄了。所以這個題目，等價于我們查詢隊列里面時間最小的。我們不禁想到一個熟悉的數(shù)據(jù)結(jié)構(gòu)，優(yōu)先隊列!活著我們可以使用一個小根堆進行實現(xiàn)。
每次我們插入一個新的定時任務，我們將一個任務插入優(yōu)先隊列，每次插入的時候，隊列內(nèi)部需要進行調(diào)整，算法時間復雜度為O(logN)。值得注意的是，在討論算法時間復雜度的時候，logN是Base2的，也就是說，如果N等于8的時候，logN就是3。
同理，雖然我們可以在O(1)的時間里面找到時間最小的任務，但是如果我們?nèi)〕鲞@個元素，優(yōu)先隊列需要做內(nèi)部的調(diào)整，這個算法時間復雜度也是O(logN)的。
時間輪法
上述優(yōu)先隊列的算法，綜合算法時間復雜度是O(logN)的，已經(jīng)很高效了，但是在我們大并發(fā)的分布式系統(tǒng)下，這個速度，還是太慢了。我們有沒有更高效的算法呢?
那便是時間輪算法，時間輪是一個環(huán)形隊列，按照時間的單位區(qū)分，我們假設1秒，每個單位里面，是一個鏈表，用來存儲定時任務。
可能你會問，一個環(huán)形隊列里面的元素，畢竟是優(yōu)先的，如果超過了長度，我們該怎么辦呢?我們可以聯(lián)想到我們家里的水表，是不是也有很多個輪子，每一個輪子的單位不一樣!
同樣，時間輪也是如此，我們可以用多級時間輪進行優(yōu)化，就跟我們的時鐘或者水表一樣，這一層的走了一圈，下一層的才走了一格。
那么，這個算法的 時間復雜度怎么計算呢?插入的時候，我們從低層開始查找，找到在哪一層，然后直接插入對應的刻度。假如我們的時間輪有5層，那么我們最多查找5次。
查詢的時候，我們每一秒都是推動時間輪的滾動，每次都是直接取隊首的元素，相當于算法時間復雜度為O(1)。當轉(zhuǎn)了一圈的時候，把下一層的下一格再推下來。這樣子，我們一個元素，最多會從第5層，逐漸插到第1層，綜合下來一個元素最多會被插入5次，在算法時間復雜度評估的時候，我們通常會忽略常數(shù)，最終算法時間復雜度為O(1)。
總結(jié)
一個非常簡單的面試題，竟然有好幾種不同的解法。這才是算法與數(shù)據(jù)結(jié)構(gòu)的魅力，歡迎大家關注我，共同學習，共同進步。大家的支持是我繼續(xù)嘮嗑的動力。
【責任編輯：華軒 TEL：（010）68476606】