oSym，即定时事件处理队列，每次可以往里面插入一个任务，在指定时间后执行。

主要接口名称与作用：

下面是 jspvz 原版 oSym 实现代码

可以看出执行 Start 函数后代码会每时间刻扫描一遍任务队列，把需要执行的任务执行并从队列里删除，单次处理（不调用函数）时间复杂度 O(N) ，空间复杂度 O(N) ，其中 N 为队列长度，若加上调用函数的复杂度那么执行速度会更慢，面对这种情况有什么办法优化呢？

• 方案一：优先队列优化
  

既然任务时间会有先后顺序问题，那不如直接用优先队列等数据结构优化，根据任务结束时间从小到大排序，每次取最小值的任务进行处理，直到队列里最小值大于当前时间即可，优先队列可采用简单的最小堆进行实现，如下：

有了数据结构加持，可以配合 oSym 进行处理队列，如下：

如代码所示，不难看出，每次插入任务时会把所要执行的任务丢入到一个等待队列时，等主线程执行时再把等待队列的任务插入优先队列，这样能有效避免在执行函数时执行 addTask 导致的死循环，每次执行时取出堆顶比较并执行。这样单次执行时间复杂度 O(M log N + K log N) 其中 N 是总任务数，M 是等待队列任务数量，K 是需要执行的任务数量，因为堆的插入与删除需要 O(log N) 复杂度，所以复杂度会相乘，但是空间复杂度为 O (N) ，其中 N 为总元素数量。

由时间复杂度可知，使用优先队列可以适用于处理比较零散的任务，比如几百时间刻才有一个任务需要被处理，而且有许多这种任务的情况下，执行几个任务单次处理是 O(log N) 的，而原版则需要 O(N) ，这时使用优先队列的优点就出来了。

但是植物大战僵尸中游戏的刷新频率是极高的，如果每时间刻都有几十到几百个任务要处理并且都是将要处理的任务，优先队列优化就反而会起到反向作用，甚至不如 O(N) 扫描，这个时候就要考虑其他方法。

• 方案二：链表/跳表优化

考虑到扫描任务、执行过期任务频率是远远大于插入任务的，可以使用链表、跳表进行优化，每次插入寻找合适位置使得链表/跳表是有序的，查询时从其头部开始遍历把到期任务处理掉，即使遍历是 O(K) 的，K 为符合条件的任务数量，但有序的代价就是插入复杂度最坏 O(N) ，其中 N 是元素数量，对于某些极端时候还是不能很好的胜任甚至会起到反优化结果，这里便不展示实现代码。

• 方案三：平衡二叉树

平衡二叉树常见的就 AVL树 和 红黑树 了，你肯定以为要用这个数据结构进行所有的插入读取操作，其实不然。

既然 jspvz 中有大量密集的任务和大量零散的任务，而对于插入删除 O(log N) 来说，嵌套一层数组遍历也不是不可以，什么意思呢？如果我们把所有任务按照某个方式区分成 K 组，把这 K 个数组丢进平衡二叉树里，每次询问筛选出符合条件的所有数组，再把符合条件的数组里元素提取出来并删除，便可以对优先队列进行个小优化

这里我使用的是 GitHub 上的 AVL 树模板（https://github.com/w8r/avl），进行加工使用的类

代码大意是把每个任务进行划分，如果树里有这个区域则直接修改，否则插入新值域；对于查询来说，O (K) 遍历区间筛选出范围内的区间，其中 K 是符合条件的值域数，然后再从这些区间里面细分任务数，最后直接对数组进行删除或者截取操作。

整套流程插入为 O(M log E)，其中 M 为所有元素中属于不同值域的个数，E 为当前树里所含的值域个数，筛选执行删除理想是 O(K) 的，其中 K 为符合条件的任务数量，总体来看复杂度也没有那么难看。

搞定了基本模板，接下来是 oSym 部分了：

总体代码与优先队列的版本类似，实际运行效果也能说得过去，对“你的心脏够强劲”那关5000僵尸来说还是有比较可观的优化的

好了以上就是关于 oSym 的研究与探讨了，如果我想到更好的方案到时候会重新发出来，感谢您的阅读。