搜索
当前位置: 大无限平台 > 定时分析 >

一个高效的定时器分析及设计

gecimao 发表于 2019-04-26 01:17 | 查看: | 回复:

  对于一个游戏而言,定时器是必须的,而它一般作为一个游戏基本公共组件,而定时器在游戏逻辑中运用是非常明显的(比如吃药回血,每几秒回血多少),而对于游戏逻辑而言需要开发一个高效率高精度(毫秒级别)的定时器。

  1.Ace种定时器实现有4种,这里不具体介绍实现细节,主要介绍实现数据结构,性能。

  具体的4种定时器都是从ACE_Timer_Queue_T继承,每种定时器用不同的数据结构来实现具体Timer的算法。

  1)ACE_Timer_Heap定时器,根据触发时间建立一个优先级队列(一个最小堆数据结构)来维护所有的定时器,代价就是删除和插入过程为O(logn),代价比较高。

  2)ACE_Timer_List定时器,根据触发时间建立一个有序的双向链表,代价就是插入定时器代价较高。

  3)ACE_Timer_Hash定时器,采用开链的Hash方式每一个桶为一个单链表,在检查所有桶超时的时候会遍历链表所有的元素。为了提高效率这里所用的Hash桶应该足够 大,而对于定时器一般是频繁的超时响应定时器,已经插入和删除,响应会采用迭代的方式。所以效率并不是那么高效。

  4)ACE_Timer_Wheel定时器,采用的一种时间轮的方式,具体实现就好象一个轮子上面有很多插槽,每一个插槽下面包括一个有序双向链表,在Ace中把轮子叫做Wheel,插槽叫做Spoke,每一个定时器被Hash到Spoke中,而Spoke也可以理解为timer的分辨率,而Spoke的计算公式为 :( 触发时间>

  分辨率的位数)&(spoke大小-1).然后在根据触发时间把定时器插入到每一个Spoke的有序双向链表中, 与Ace_timer_Hash的实现类似,只是这里用户可以指定Spoke大小。这里代价就是插入的时候可能最坏为O(n).

  定时器是基于时间的中断函数,即是根据触发时间来超时响应。所以只要我们设计一个基于时间的Hash算法。只要我们能我们把一个函数触发时间全部Hash到此Hash算法的桶中,就实现了查找,插入,删除O(1)的操作了,其实不然基于时间的hash算法好像挺复杂,而且桶的数量太大,内存消耗太多,所以把一个时间直接Hash代价太大。是否有一种其他的方式呢,linux中断处理采用一种类似水表计算水量的方式,方式就是生活中的水表,第一个指针转一圈后一个转一格,假设每一个圈都是10个刻度,第一个圈能表示10,那么第二圈没一个刻度表示第一个圈的1圈,就能表示10*10, 二个圈一共就能表示10*10 + 10。 以此类推,5个圈就能表示10^5+10^4+10^3+10^2+10...

  A. 轮子,这里采用的轮子与上面介绍的Ace轮子大概一样,一个循环列队,每一个插槽你们有一个双向链表,注意这里链表不需要排序,所以在插入的是O(1)的操作。轮子为5个。

  A. Hash算法:这里Hash算法根据他的多少时间后触发,直接Hash得到轮子以及插槽,然后插入到某个插槽双向的链表中。

  B.定时器触发: 定时器触发只会触发第一个轮子超时的所有定时器,因为后面4个轮子定时器表示都在前1轮子触发完了才会触发,所以这里让后面4个轮子维护表示将要发生的定时。这里会根据当第一个轮子转第几圈后,第二个轮子会把第几插槽的所有定时器全部插入到第一个轮子中,依次类推,第二个轮子转一个第三个轮子某个插槽又会插入到第二个轮子中。。。

  B.定时器的迁移,也即将一个定时器从它原来所处的轮子插槽迁移到另一个轮子插槽中。

  47 /// 定时器的迁移,也即将一个定时器从它原来所处的定时器向量迁移到另一个定时器向量中。

  通过本文的介绍可以理解次定时器的的查找,删除,插入都是O(1)的复杂度。

本文链接:http://kingstonflowers.net/dingshifenxi/177.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部