1 小顶堆计时器概要
小根堆定时器的优点如下：
a.添加时间复杂度为O(1);
b.删除时间复杂度为O(1);
c.执行一个定时器的时间复杂度为O(1);
2 代码设计
之前写的服务器定时器是全部轮询更新，这种计时器性能太差，每一帧都要全部迭代一次，客户端层应该把CPU性能压榨到极致，能少循环的尽量少循环尽可能的减少CPU循环次数，所以优化了算法，使用了小堆顶定时器。小顶堆是基于二叉树的排序算法，将剩余时间最小的节点交换到树的根节点。每次更新的时候只取树的根节点，判断是否超时，如果超时会对树重新进行排序，排序完成后继续轮询，查询到根节点无超时为止。
Timer.cs代码实现
using UnityEngine; using System; using Object = UnityEngine.Object; namespace UnityTimer { public class Timer { public enum SCOPE { eLocal, eGlobal, } #region Public Properties/Fields /// <summary> /// 计时器回调时间持续时间 /// </summary> public float duration { get; private set; } /// <summary> /// 执行完成后是否循环执行. /// </summary> public bool isLooped { get; set; } /// <summary> /// 本帧是否完成 /// </summary> public bool isCompletedThisFrame { get; private set; } /// <summary> /// 是否完成 /// </summary> public bool isCompleted { get; private set; } /// <summary> /// 计时器使用的是实时时间还是游戏时间 /// </summary> public bool usesRealTime { get; private set; } /// <summary> /// 计时器是否暂停 /// </summary> public bool isPaused { get { return this._timeElapsedBeforePause.HasValue; } } /// <summary> /// 是否取消了 /// </summary> public bool isCancelled { get { return this._timeElapsedBeforeCancel.HasValue; } } /// <summary> /// 是否完成 /// </summary> public bool isDone { get { return this.isCompleted || this.isCancelled || this.isOwnerDestroyed; } } #endregion #region Public Static Methods /// <summary> /// 注册一个新的计时器，在一定时间后触发一个事件 /// 在切换场景的时候，注册的计时器会被销毁 /// </summary> /// <param name="duration">在一定秒后执行事件</param> /// <param name="onComplete">计时器执行完回调事件.</param> /// <param name="onUpdate">每次执行计时器执行的回调</param> /// <param name="isLooped">计时器在执行后是否重复执行</param> /// <param name="useRealTime">是否使用实时时间</param> /// <param name="autoDestroyOwner">此计时器附加到的对象，物体被摧毁后,定时器将不执行</param> /// <returns>一个计时器对象</returns> public static Timer Regist(float duration, Action onComplete, Action<float> onUpdate = null, bool isLooped = false, bool useRealTime = false, MonoBehaviour autoDestroyOwner = null) { if (Timer._manager == null) { TimerManager managerInScene = Object.FindObjectOfType<TimerManager>(); if (managerInScene != null) { Timer._manager = managerInScene; } else { GameObject managerObject = new GameObject { name = "TimerManager" }; Timer._manager = managerObject.AddComponent<TimerManager>(); } } Timer timer = new Timer(duration, onComplete, onUpdate, isLooped, useRealTime, autoDestroyOwner); Timer._manager.RegisterTimer(timer); return timer; } /// <summary> /// 作用同上，不同的是此API创建的计时器在程序的生命周期内都有效，不会随着场景的销毁而销毁 /// </summary> public static Timer RegistGlobal(float duration, Action onComplete, Action<float> onUpdate = null, bool isLooped = false, bool useRealTime = false, MonoBehaviour autoDestroyOwner = null) { if (Timer._globalManager == null) { GlobalTimerManager globalManager = Object.FindObjectOfType<GlobalTimerManager>(); if (globalManager != null) { Timer._globalManager = globalManager; } else { GameObject globalManagerObject = new GameObject { name = "GlobalTimerManager" }; Timer._globalManager = globalManagerObject.AddComponent<GlobalTimerManager>(); GameObject.DontDestroyOnLoad(Timer._globalManager); } } Timer timer = new Timer(duration, onComplete, onUpdate, isLooped, useRealTime, autoDestroyOwner); Timer._globalManager.RegisterTimer(timer); return timer; } public static void Cancel(Timer timer) { if (timer != null) { timer.Cancel(); } } public static void Pause(Timer timer) { if (timer != null) { timer.Pause(); } } public static void Resume(Timer timer) { if (timer != null) { timer.Resume(); } } public static void CancelAllRegisteredTimers(SCOPE eScope = SCOPE.eLocal) { //如果计时器不存在，不需要做任何事情 if (eScope == SCOPE.eLocal) { if (Timer._manager != null) { Timer._manager.CancelAllTimers(); } } else if (eScope == SCOPE.eGlobal) { if (Timer._globalManager != null) { Timer._globalManager.CancelAllTimers(); } } } public static void PauseAllRegisteredTimers(SCOPE eScope = SCOPE.eLocal) { //如果计时器不存在，不需要做任何事情 if (eScope == SCOPE.eLocal) { if (Timer._manager != null) { Timer._manager.PauseAllTimers(); } } else if (eScope == SCOPE.eGlobal) { if (Timer._globalManager != null) { Timer._globalManager.PauseAllTimers(); } } } public static void ResumeAllRegisteredTimers(SCOPE eScope = SCOPE.eLocal) { //如果计时器不存在，不需要做任何事情 if (eScope == SCOPE.eLocal) { if (Timer._manager != null) { Timer._manager.ResumeAllTimers(); } } else if (eScope == SCOPE.eGlobal) { if (Timer._globalManager != null) { Timer._globalManager.ResumeAllTimers(); } } } #endregion #region Public Methods public void Cancel() { if (this.isDone) { return; } this._timeElapsedBeforeCancel = this.GetTimeElapsed(); this._timeElapsedBeforePause = null; } public void Pause() { if (this.isPaused || this.isDone) { return; } this._timeElapsedBeforePause = this.GetTimeElapsed(); } public void Resume() { if (!this.isPaused || this.isDone) { return; } this._timeElapsedBeforePause = null; } public float GetTimeElapsed() { if (this.isCompleted || this.GetWorldTime() >= this.GetFireTime()) { return this.duration; } return this._timeElapsedBeforeCancel ?? this._timeElapsedBeforePause ?? this.GetWorldTime() - this._startTime; } public float GetTimeRemaining() { return this.duration - this.GetTimeElapsed(); } public float GetRatioComplete() { return this.GetTimeElapsed() / this.duration; } public float GetRatioRemaining() { return this.GetTimeRemaining() / this.duration; } #endregion #region Private Static Properties/Fields private static TimerManager _manager; private static GlobalTimerManager _globalManager; #endregion #region Private Properties/Fields private bool isOwnerDestroyed { get { return this._hasAutoDestroyOwner && this._autoDestroyOwner == null; } } private readonly Action _onComplete; private readonly Action<float> _onUpdate; private float _startTime; private float _endTime; private float _lastUpdateTime; private float? _timeElapsedBeforeCancel; private float? _timeElapsedBeforePause; private readonly MonoBehaviour _autoDestroyOwner; private readonly bool _hasAutoDestroyOwner; #endregion #region 属性区 public float EndTime { get { return _endTime; } } #endregion #region Private Constructor (use static Register method to create new timer) private Timer(float duration, Action onComplete, Action<float> onUpdate, bool isLooped, bool usesRealTime, MonoBehaviour autoDestroyOwner) { this.duration = duration; this._onComplete = onComplete; this._onUpdate = onUpdate; this.isLooped = isLooped; this.usesRealTime = usesRealTime; this._autoDestroyOwner = autoDestroyOwner; this._hasAutoDestroyOwner = autoDestroyOwner != null; this._startTime = this.GetWorldTime(); this._lastUpdateTime = this._startTime; _endTime = _startTime + duration; } #endregion #region Methods public float GetWorldTime() { return this.usesRealTime ? Time.realtimeSinceStartup : Time.time; } private float GetFireTime() { return this._startTime + this.duration; } private float GetTimeDelta() { return this.GetWorldTime() - this._lastUpdateTime; } public void Update() { isCompletedThisFrame = false; if (this.isDone) { return; } if (this.isPaused) { this._startTime += this.GetTimeDelta(); this._lastUpdateTime = this.GetWorldTime(); return; } this._lastUpdateTime = this.GetWorldTime(); if (this._onUpdate != null) { this._onUpdate(this.GetTimeElapsed()); } if (this.GetWorldTime() >= this.GetFireTime()) { isCompletedThisFrame = true; if (this._onComplete != null) { this._onComplete(); } if (this.isLooped) { this._startTime = this.GetWorldTime(); _endTime = _startTime + duration; } else { this.isCompleted = true; } } } #endregion } }
TimerMgr.cs代码实现
using System.Collections.Generic; using UnityEngine; using System; using Object = UnityEngine.Object; namespace UnityTimer { public class TimerManager : MonoBehaviour { //protected List<Timer> _timers = new List<Timer>(); //初始化默认new 1个空间出来 protected Timer[] m_szTimers = new Timer[1]; //已使用的空间 protected uint m_iUsedSize = 0; //protected List<Timer> _timersToAdd = new List<Timer>(); protected void Resize() { int iOldCapacity = m_szTimers.Length; int iNewCapacity = iOldCapacity * 2; Timer[] szTempTimer = new Timer[iNewCapacity]; //尾部全部设置成null for (int i = iOldCapacity; i < iNewCapacity; ++i) { szTempTimer[i] = null; } //copy oldData -> newData Array.Copy(m_szTimers, szTempTimer, m_szTimers.Length); //指向新地址 m_szTimers = szTempTimer; //解除引用 szTempTimer = null; } /// <summary> /// 小顶堆排序 /// </summary> public void HeapAdjustSmall(int parent) { if (parent >= m_szTimers.Length) { return; } Timer tmp = m_szTimers[parent]; //时间复杂度应该在O(LogN)附近 for (int child = parent * 2 + 1; child < m_iUsedSize; child = child * 2 + 1) { if (child + 1 < m_iUsedSize && m_szTimers[child].EndTime > m_szTimers[child + 1].EndTime) { child++; } if (tmp.EndTime > m_szTimers[child].EndTime) { m_szTimers[parent] = m_szTimers[child]; parent = child; } else { break; } } m_szTimers[parent] = tmp; } public void AddTimer(Timer timer) { if (null == timer) { return; } if (m_iUsedSize >= m_szTimers.Length) { Resize(); } uint hole = m_iUsedSize; ++m_iUsedSize; // 由于新结点在最后，因此将其进行上滤，以符合最小堆 for (uint parent = (hole - 1) / 2; hole > 0; parent = (hole - 1) / 2) { //把时间最短的计时器交换到树根节点 if (m_szTimers[parent].EndTime > timer.EndTime) { m_szTimers[hole] = m_szTimers[parent]; hole = parent; } else { break; } } m_szTimers[hole] = timer; } public void PopTimer() { if (0 == m_iUsedSize) { return; } if (null != m_szTimers[0]) { m_szTimers[0] = m_szTimers[--m_iUsedSize]; HeapAdjustSmall(0); } } public void RegisterTimer(Timer timer) { AddTimer(timer); } public void CancelAllTimers() { Timer timer = null; for (int i = 0; i < m_szTimers.Length; ++i) { timer = m_szTimers[i]; if (null != timer) { timer.Cancel(); m_szTimers[i] = null; } } m_iUsedSize = 0; } public void PauseAllTimers() { Timer timer = null; for (int i = 0; i < m_szTimers.Length; ++i) { timer = m_szTimers[i]; if (null != timer) timer.Pause(); } } public void ResumeAllTimers() { Timer timer = null; for (int i = 0; i < m_szTimers.Length; ++i) { timer = m_szTimers[i]; if (null != timer) timer.Resume(); } } protected void Update() { UpdateAllTimers(); } protected void UpdateAllTimers() { Timer tm = null; //for (int i = 0; i < m_szTimers.Length; ++i) //{ // tm = m_szTimers[i]; // if (null != tm) // tm.Update(); //} Timer tmp = null; tmp = m_szTimers[0]; while (m_iUsedSize > 0) { if (null == tmp) break; tmp.Update(); //循环类型的计时器，如果到了时间，重新排序，而不清理 if (tmp.isCompletedThisFrame && tmp.isLooped) { HeapAdjustSmall(0); tmp = m_szTimers[0]; continue; } if (!tmp.isDone) break; PopTimer(); tmp = m_szTimers[0]; } } } public class GlobalTimerManager : TimerManager { } }
3 测试数据对比
在更新所有timer的地方，开启10w定时器测试使用小顶堆和不使用小顶堆做了对比：
计时器不使用小堆顶：更新全部，cpu main 在 14.1左右浮动；
计时器使用小堆顶：计时器timeout时间取的是1-10w,cpu mian 平均 在1.6左右浮动，在雪崩(全部更新的情况)情况下 cpuMian会突然上升到9.6左右；
通过数据比对，使用了小顶堆比不使用小顶堆，在综合情况下效率要快将近8.8倍
引用
文章：基于STL的小根堆定时器实现（C++）_AlwaysSimple的博客-CSDN博客_小根堆定时器
