框架中实现小堆顶高性能定时器 10W计时器耗时1.9ms

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
 
        /// 
        /// 计时器回调时间持续时间
        /// 
        public float duration { get; private set; }
 
        /// 
        /// 执行完成后是否循环执行.
        /// 
        public bool isLooped { get; set; }
 
        /// 
        /// 本帧是否完成
        /// 
        public bool isCompletedThisFrame { get; private set; }
        
        /// 
        /// 是否完成
        /// 
        public bool isCompleted { get; private set; }
 
        /// 
        /// 计时器使用的是实时时间还是游戏时间
        /// 
        public bool usesRealTime { get; private set; }
 
        /// 
        /// 计时器是否暂停
        /// 
        public bool isPaused
        {
            get { return this._timeElapsedBeforePause.HasValue; }
        }
 
        /// 
        /// 是否取消了
        /// 
        public bool isCancelled
        {
            get { return this._timeElapsedBeforeCancel.HasValue; }
        }
 
        /// 
        /// 是否完成
        /// 
        public bool isDone
        {
            get { return this.isCompleted || this.isCancelled || this.isOwnerDestroyed; }
        }
 
        #endregion
 
        #region Public Static Methods
 
        /// 
        /// 注册一个新的计时器，在一定时间后触发一个事件
        /// 在切换场景的时候，注册的计时器会被销毁
        /// 
        /// 在一定秒后执行事件
        /// 计时器执行完回调事件.
        /// 每次执行计时器执行的回调
        /// 计时器在执行后是否重复执行
        /// 是否使用实时时间
        /// 此计时器附加到的对象，物体被摧毁后,定时器将不执行
        /// 一个计时器对象
        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();
                if (managerInScene != null)
                {
                    Timer._manager = managerInScene;
                }
                else
                {
                    GameObject managerObject = new GameObject { name = "TimerManager" };
                    Timer._manager = managerObject.AddComponent();
                }
            }
 
            Timer timer = new Timer(duration, onComplete, onUpdate, isLooped, useRealTime, autoDestroyOwner);
            Timer._manager.RegisterTimer(timer);
            return timer;
        }
 
        /// 
        /// 作用同上，不同的是此API创建的计时器在程序的生命周期内都有效，不会随着场景的销毁而销毁
        /// 
        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();
                if (globalManager != null)
                {
                    Timer._globalManager = globalManager;
                }
                else
                {
                    GameObject globalManagerObject = new GameObject { name = "GlobalTimerManager" };
                    Timer._globalManager = globalManagerObject.AddComponent();
                    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 _timers = new List();
 
        //初始化默认new 1个空间出来
        protected Timer[] m_szTimers = new Timer[1];
 
        //已使用的空间
        protected uint m_iUsedSize = 0;
 
        //protected List _timersToAdd = new List();
 
        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;
        }
 
        /// 
        /// 小顶堆排序   
        /// 
        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博客_小根堆定时器

相关阅读:
npm作用域包和版本
 【算法|动态规划No.25】leetcode LCR 020. 回文子串
 【云原生 · Kubernetes】KubeVirt热迁移
 【最长上升子序列】【博弈论】Game on Permutation—CF1860C
【机器学习技巧】之特征工程：数字编码以及One-hot独热编码的几种方式（sklearn与pandas处理方式)
Windows编程dll基本知识点
 JOSEF约瑟 JHOK-ZBM1；JHOK-ZBL1多档切换式漏电（剩余）继电器面板导轨安装
 ES6中新增加的Symbol数据类型及其使用场景
 头歌——Linux——下的 c 编程
 Leetcode 440. 字典序的第K小数字
原文地址：https://blog.csdn.net/qq_33531923/article/details/127895768

框架中实现 小堆顶高性能定时器 10W计时器耗时1.9ms

1 小顶堆计时器概要

小根堆定时器的优点如下：

2 代码设计

3 测试数据对比

框架中实现小堆顶高性能定时器 10W计时器耗时1.9ms