首页 > 代码库 > 记录——时间轮定时器（lua 实现）
记录——时间轮定时器（lua 实现）
很长一段时间里，我错误的认识了定时器。无意中，我发现了“时间轮”这个名词，让我对定时器有了新的看法。
我错误的认为，定时器只需要一个 tick 队列，按指定的时间周期遍历队列，检查 tick 倒计时满足触发条件就触发回调。
tick 定义如下：
1 struct Tick {2 int_t n;3 func_t func;4 };
遍历触发实现如下：
1 void Update() 2 { 3 for (auto & tick: _ticks) 4 { 5 if (Check(tick)) 6 { 7 tick.func(); 8 Remove(tick); 9 }10 }11 }
实现很简洁，但效率却出奇的慢。
假设有100个tick，依次触发时间是100～10000毫秒，也就是每一个tick的触发间隔为100毫秒
可以想象，在头100毫秒内，不会有任何tick被触发，但是Update却傻乎乎对100个tick进行Check。
当时间达到100毫秒的时候，只有第一个 tick 达到了触发条件，但是Update依旧会对余下99个进行Check。
时间轮很好的解决了这个问题。
思路是这样的：
需要一个轮盘，轮盘上有若干个插槽，
把 tick 放进合适的插槽，
每次轮询直接触发插槽里的 tick。
假设要实现一个最低刻度为毫秒，最大上限为1天的定时器（最长延时23点59分59秒999毫秒）
假设要在 3点30分25秒600毫秒 处安插一个 tick。
首先这个轮盘需要 24 × 60 x 60 x 1000 个插槽，
其次把 3点30分25秒600毫秒 转化为定时器最低刻度（毫秒），也就是 11005600 = 600 + 25000 + 180000 + 10800000.
也就是说，在这个轮盘的 11005600 刻度位置，安插上这个 tick。
就是这么简单粗暴！
这是一个错误例子。
其实不需要那么多插槽，如果你见过水表，你应该知道该怎么做，继续前面的假设。
我们为每一个时间单位准备一个时间轮，就是 时（24），分（60），秒（60），毫秒（1000）
因此只需要 1144 = 24 + 60 + 60 + 1000 个插槽就够了。
在 3点30分25秒600毫秒 处安插一个 tick，
首先在 时(3) 安插上这个 tick，
当执行到 时(3) 的时候，删除这个 tick，检查到该 tick 还有 30分25秒600毫秒
于是在 分（30）安插上这个 tick，
当执行到 分（30）的时候，删除这个 tick，检查到该 tick 还有 25秒600毫秒
于是在 秒（25）安插上这个 tick，
当执行到 秒（25）的时候，删除这个tick，检查到该 tick 还有 600毫秒
于是在 毫秒（600）安插上这个 tick，
当执行到 毫秒（600）的时候，删除这个tick，触发这个 tick。
这个 tick 从被安插到被触发，总共只需要 Check（4） 次。
如果采用本文开头的思路，那将会被 Check（天文数字）次。
因为只是为了理解算法，我只是用lua实现了一遍，算法本身大概只有90行不到，吐个槽，lua索引从1开始很蛋疼。
1 sformat = string.format 2 tinsert = table.insert 3 tremove = table.remove 4 tconcat = table.concat 5 mfloor = math.floor 6 local utils = require("utils") 7 local _M = { _slots = nil, 8 _cycle = nil, } 9 10 function _M.Init(self, cycle)11 if not self._slots then12 self._slots = {}13 self._slots[1] = {}14 self._slots[2] = {}15 self._slots[3] = {}16 self._slots[4] = {}17 utils.tinsert_n(self._slots[1], {}, 24)18 utils.tinsert_n(self._slots[2], {}, 60)19 utils.tinsert_n(self._slots[3], {}, 60)20 utils.tinsert_n(self._slots[4], {}, 1000)21 end22 if not self._cycle then23 self._cycle = cycle24 end25 end26 27 function _M.Update(self, cycle)28 local h1, m1, s1, ms1 = utils.ms2t(self._cycle)29 self._cycle = cycle30 local h2, m2, s2, ms2 = utils.ms2t(self._cycle)31 self:__UpdateT__(24, 1, h1, h2, utils.bind(self.__UpdateH__, self))32 self:__UpdateT__(60, 2, m1, m2, utils.bind(self.__UpdateM__, self))33 self:__UpdateT__(60, 3, s1, s2, utils.bind(self.__UpdateS__, self))34 self:__UpdateT__(1000, 4, ms1, ms2, utils.bind(self.__UpdateMS__, self))35 end36 37 function _M.AddTimer(self, delay, func)38 self:__Insert__(delay + 1, func)39 end40 41 function _M.__Insert__(self, delay, func)42 if 0 == delay then43 func()44 else45 local h1, m1, s1, ms1 = utils.ms2t(delay)46 local h2, m2, s2, ms2 = utils.ms2t(delay + self._cycle)47 local tick = { func = func, 48 time = { h = h2, m = m2, s = s2, ms = ms2 } }49 if h1 ~= 0 then50 tinsert(self._slots[1][h2 == 0 and 24 or h2], tick)51 elseif m1 ~= 0 then52 tinsert(self._slots[2][m2 == 0 and 60 or m2], tick)53 elseif s1 ~= 0 then54 tinsert(self._slots[3][s2 == 0 and 60 or s2], tick)55 elseif ms1 ~= 0 then56 tinsert(self._slots[4][ms2 == 0 and 1000 or ms2], tick)57 end58 end59 end60 61 function _M.__UpdateT__(self, cycle, index, first, last, func)62 local slots = self._slots[index]63 while first ~= last do64 first = first + 165 for i = 1, #slots[first] do66 func(slots[first][i])67 end68 slots[first] = {}69 first = first % cycle70 end71 end72 73 function _M.__UpdateH__(self, v)74 self:__Insert__(utils.t2ms(0, v.time.m, v.time.s, v.time.ms), v.func)75 end76 77 function _M.__UpdateM__(self, v)78 self:__Insert__(utils.t2ms(0, 0, v.time.s, v.time.ms), v.func)79 end80 81 function _M.__UpdateS__(self, v)82 self:__Insert__(utils.t2ms(0, 0, 0, v.time.ms), v.func)83 end84 85 function _M.__UpdateMS__(self, v)86 self:__Insert__(utils.t2ms(0, 0, 0, 0), v.func)87 end88 89 return _M
源码下载
记录——时间轮定时器（lua 实现）