當年我還是個學生的時候，有一次去參加歡聚時代的一個面試，有一道面試題記憶尤新，讓你來實現一個定時任務，你會怎么做?為了簡化問題，我們只用考慮內存方案，不用考慮數據持久化。

數組法

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

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

[[278610]]

優先隊列法

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

我們每次查詢，都只要查詢時間最接近當前時間的，時間比當前時間更早的，肯定被我們丟棄了。所以這個題目，等價于我們查詢隊列里面時間最小的。我們不禁想到一個熟悉的數據結構，優先隊列!活著我們可以使用一個小根堆進行實現。

每次我們插入一個新的定時任務，我們將一個任務插入優先隊列，每次插入的時候，隊列內部需要進行調整，算法時間復雜度為O(logN)。值得注意的是，在討論算法時間復雜度的時候，logN是Base2的，也就是說，如果N等于8的時候，logN就是3。

同理，雖然我們可以在O(1)的時間里面找到時間最小的任務，但是如果我們取出這個元素，優先隊列需要做內部的調整，這個算法時間復雜度也是O(logN)的。

時間輪法

上述優先隊列的算法，綜合算法時間復雜度是O(logN)的，已經很高效了，但是在我們大并發的分布式系統下，這個速度，還是太慢了。我們有沒有更高效的算法呢?

那便是時間輪算法，時間輪是一個環形隊列，按照時間的單位區分，我們假設1秒，每個單位里面，是一個鏈表，用來存儲定時任務。

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

同樣，時間輪也是如此，我們可以用多級時間輪進行優化，就跟我們的時鐘或者水表一樣，這一層的走了一圈，下一層的才走了一格。

那么，這個算法的 時間復雜度怎么計算呢?插入的時候，我們從低層開始查找，找到在哪一層，然后直接插入對應的刻度。假如我們的時間輪有5層，那么我們最多查找5次。

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

總結

一個非常簡單的面試題，竟然有好幾種不同的解法。這才是算法與數據結構的魅力，歡迎大家關注我，共同學習，共同進步。大家的支持是我繼續嘮嗑的動力。