oSym，即定時(shí)事件處理隊(duì)列，每次可以往里面插入一個(gè)任務(wù)，在指定時(shí)間后執(zhí)行。

主要接口名稱(chēng)與作用：

下面是 jspvz 原版 oSym 實(shí)現(xiàn)代碼

可以看出執(zhí)行 Start 函數(shù)后代碼會(huì)每時(shí)間刻掃描一遍任務(wù)隊(duì)列，把需要執(zhí)行的任務(wù)執(zhí)行并從隊(duì)列里刪除，單次處理（不調(diào)用函數(shù)）時(shí)間復(fù)雜度 O(N)?，空間復(fù)雜度 O(N) ，其中 N 為隊(duì)列長(zhǎng)度，若加上調(diào)用函數(shù)的復(fù)雜度那么執(zhí)行速度會(huì)更慢，面對(duì)這種情況有什么辦法優(yōu)化呢？

• 方案一：優(yōu)先隊(duì)列優(yōu)化
  

既然任務(wù)時(shí)間會(huì)有先后順序問(wèn)題，那不如直接用優(yōu)先隊(duì)列等數(shù)據(jù)結(jié)構(gòu)優(yōu)化，根據(jù)任務(wù)結(jié)束時(shí)間從小到大排序，每次取最小值的任務(wù)進(jìn)行處理，直到隊(duì)列里最小值大于當(dāng)前時(shí)間即可，優(yōu)先隊(duì)列可采用簡(jiǎn)單的最小堆進(jìn)行實(shí)現(xiàn)，如下：

有了數(shù)據(jù)結(jié)構(gòu)加持，可以配合 oSym 進(jìn)行處理隊(duì)列，如下：

如代碼所示，不難看出，每次插入任務(wù)時(shí)會(huì)把所要執(zhí)行的任務(wù)丟入到一個(gè)等待隊(duì)列時(shí)，等主線(xiàn)程執(zhí)行時(shí)再把等待隊(duì)列的任務(wù)插入優(yōu)先隊(duì)列，這樣能有效避免在執(zhí)行函數(shù)時(shí)執(zhí)行 addTask 導(dǎo)致的死循環(huán)，每次執(zhí)行時(shí)取出堆頂比較并執(zhí)行。這樣單次執(zhí)行時(shí)間復(fù)雜度 O(M log N?+ K log N) 其中 N 是總?cè)蝿?wù)數(shù)，M?是等待隊(duì)列任務(wù)數(shù)量，K 是需要執(zhí)行的任務(wù)數(shù)量，因?yàn)槎训牟迦肱c刪除需要 O(log N) 復(fù)雜度，所以復(fù)雜度會(huì)相乘，但是空間復(fù)雜度為 O (N) ，其中 N 為總元素?cái)?shù)量。

由時(shí)間復(fù)雜度可知，使用優(yōu)先隊(duì)列可以適用于處理比較零散的任務(wù)，比如幾百時(shí)間刻才有一個(gè)任務(wù)需要被處理，而且有許多這種任務(wù)的情況下，執(zhí)行幾個(gè)任務(wù)單次處理是 O(log N) 的，而原版則需要 O(N) ，這時(shí)使用優(yōu)先隊(duì)列的優(yōu)點(diǎn)就出來(lái)了。

但是植物大戰(zhàn)僵尸中游戲的刷新頻率是極高的，如果每時(shí)間刻都有幾十到幾百個(gè)任務(wù)要處理并且都是將要處理的任務(wù)，優(yōu)先隊(duì)列優(yōu)化就反而會(huì)起到反向作用，甚至不如 O(N) 掃描，這個(gè)時(shí)候就要考慮其他方法。

• 方案二：鏈表/跳表優(yōu)化

考慮到掃描任務(wù)、執(zhí)行過(guò)期任務(wù)頻率是遠(yuǎn)遠(yuǎn)大于插入任務(wù)的，可以使用鏈表、跳表進(jìn)行優(yōu)化，每次插入尋找合適位置使得鏈表/跳表是有序的，查詢(xún)時(shí)從其頭部開(kāi)始遍歷把到期任務(wù)處理掉，即使遍歷是 O(K) 的，K 為符合條件的任務(wù)數(shù)量，但有序的代價(jià)就是插入復(fù)雜度最壞 O(N) ，其中 N 是元素?cái)?shù)量，對(duì)于某些極端時(shí)候還是不能很好的勝任甚至?xí)鸬椒磧?yōu)化結(jié)果，這里便不展示實(shí)現(xiàn)代碼。

• 方案三：平衡二叉樹(shù)

平衡二叉樹(shù)常見(jiàn)的就 AVL樹(shù) 和 紅黑樹(shù) 了，你肯定以為要用這個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行所有的插入讀取操作，其實(shí)不然。

既然 jspvz 中有大量密集的任務(wù)和大量零散的任務(wù)，而對(duì)于插入刪除?O(log?N)?來(lái)說(shuō)，嵌套一層數(shù)組遍歷也不是不可以，什么意思呢？如果我們把所有任務(wù)按照某個(gè)方式區(qū)分成 K 組，把這 K?個(gè)數(shù)組丟進(jìn)平衡二叉樹(shù)里，每次詢(xún)問(wèn)篩選出符合條件的所有數(shù)組，再把符合條件的數(shù)組里元素提取出來(lái)并刪除，便可以對(duì)優(yōu)先隊(duì)列進(jìn)行個(gè)小優(yōu)化

這里我使用的是 GitHub 上的 AVL 樹(shù)模板（https://github.com/w8r/avl），進(jìn)行加工使用的類(lèi)

代碼大意是把每個(gè)任務(wù)進(jìn)行劃分，如果樹(shù)里有這個(gè)區(qū)域則直接修改，否則插入新值域；對(duì)于查詢(xún)來(lái)說(shuō)，O (K) 遍歷區(qū)間篩選出范圍內(nèi)的區(qū)間，其中 K?是符合條件的值域數(shù)，然后再?gòu)倪@些區(qū)間里面細(xì)分任務(wù)數(shù)，最后直接對(duì)數(shù)組進(jìn)行刪除或者截取操作。

整套流程插入為 O(M log E)，其中 M 為所有元素中屬于不同值域的個(gè)數(shù)，E 為當(dāng)前樹(shù)里所含的值域個(gè)數(shù)，篩選執(zhí)行刪除理想是?O(K) 的，其中 K 為符合條件的任務(wù)數(shù)量，總體來(lái)看復(fù)雜度也沒(méi)有那么難看。

搞定了基本模板，接下來(lái)是 oSym 部分了：

總體代碼與優(yōu)先隊(duì)列的版本類(lèi)似，實(shí)際運(yùn)行效果也能說(shuō)得過(guò)去，對(duì)“你的心臟夠強(qiáng)勁”那關(guān)5000僵尸來(lái)說(shuō)還是有比較可觀的優(yōu)化的

好了以上就是關(guān)于 oSym 的研究與探討了，如果我想到更好的方案到時(shí)候會(huì)重新發(fā)出來(lái)，感謝您的閱讀。