”说说你最喜欢军阀和独..者的哪一点，那就是他们支付账单都很准时。“——《战争之王》
大多数应用环境里，都会提供一个 loop, 结构，如果一个loop不行，就两个loop...
例，逻辑循环+UI循环+渲染循环+IO循环...
有些环境没有提供loop......是的，你一定想到了web环境下的javascript, 它只提供定时器API，
setTimeout(task, elapse) //一次定时，
setInterval(task, every_tick) //循环定时，
在javascript环境里，通过定时器去做各种update的工作，
可以通过定时器，驱动主循环,
setInterval(update, 1/fps)
这就是以定时器(而非update)，为中心的编程模式，
它有些什么好处呢,
-
更好的性能
使用定时器，它强制你思考，
一个UI特效，需要多快的刷新率
一个AI应该多久更新，
多长时间轮循一次，定时器能够更优地处理这个过程，而不是每帧轮循，见文末定时器的实现。
-
方便的异步模型
我们前面说过的，主逻辑循环+UI循环+渲染循环+IO循环里，如果我们只暴露定时器...
把定时器作为每个线程处理器(processor),IO.setTimeout(io_task, 0); //增加IO任务Render.setTimeout(render_task, 0); //增加渲染任务
UI.setInterval(check_msg, 20);//20ms 检查一次是否有message推送,
可以定义post(), 它其实就是 setTimeout(task, 0)，
看，我们用不同线程的定时器完成了 消息队列功能！
定时器的实现
- 轮询
在update里轮询每一个定时事件是否发生
update()
foreach timer in timers
if(timer.time > now)
timer.run()
...
复杂度为 O(n)，效率感人...
- 最小堆
检查最近的定时器是否发生
update()
while(peek_timer().timeReach > now)
pop_timer().run()
float_last() //堆元素整理
...
复杂度为 O(lg n)，
- 时间轮
它和我们闹钟原理相似了，当秒针，分针，时针都走到 闹时的刻度时，定时发生，这并不需要每次tick判断!
本质上，它和基数排序有着一致的原理。复杂度 O(1)
思考题：
为了便于描述，我的实现缺少一些必要功能，
setInterval //定时循环
removeTimer //移除定时器，
未处理最大定时长度
使用更高效的链表作为action list
线程不安全
你可以实现完整，作为一个可用的定时器.
//lxf0525@gmail.com
//时间轮算法
class TimeUtil
{
//常量，每一轮64个刻度
const long _ticksInWheel = 64;
//定时事件
struct TimeAction
{
public long deltaTime;
public Action action;
}
//每一刻度事件
class TickAction
{
public List<TimeAction> actions { get; set; }
public TickAction()
{
actions = new List<TimeAction>();
}
}
//时间轮
class Wheel
{
TickAction[] ticks = new TickAction[_ticksInWheel];
int _id = 0;
public Wheel(int id)
{
_id = id;
for (long i = 0; i < _ticksInWheel; ++i)
{
ticks[i] = new TickAction();
}
}
long tickIdx = 0;//当前刻度
public Wheel quickerWheel = null;//指向较快的轮
public Wheel slowWheel = null;//指向较慢的轮
public long oneTickTime = 0;//每一刻度的时间长度
public void addTime(TimeAction act)
{
long whichTick = act.deltaTime / oneTickTime;
long deltaTime = act.deltaTime % oneTickTime;
act.deltaTime = deltaTime;
ticks[whichTick].actions.Add(act);
//Console.WriteLine("add in wheel {0}, tick:{1}, delta:{2}", _id, i, deltaTime);
}
Wheel stepOne()
{
tickIdx++;
if (tickIdx == _ticksInWheel)
{
tickIdx = 0;
return slowWheel.stepOne();
}
return this;
}
public void proceed(long delta)
{
while (delta > oneTickTime)
{
var t = ticks[tickIdx];
foreach (var act in t.actions)
{
act.action();
}
t.actions.Clear();
delta -= oneTickTime;
tickIdx++;
if (tickIdx == _ticksInWheel)
{
tickIdx = 0;
var w = slowWheel.stepOne();
w.proceed(delta);
return;
}
}
if (quickerWheel != null)
{
var t = ticks[tickIdx];
foreach (var act in t.actions)
{
quickerWheel.addTime(act);
}
t.actions.Clear();
quickerWheel.proceed(delta);
}
}
}
Wheel biggestWheel = null;
long timeSys = 0;
long timeCount = 0;
public void setTimeout(System.Action act, long elapse)
{
biggestWheel.addTime(new TimeAction { action = act, deltaTime = timeCount + elapse });
}
public void update()
{
long now = DateTime.Now.Ticks / 10000;
long delta = now - timeSys;
if (delta <= 0) return;
timeCount += delta;
timeSys = timeSys + delta;
biggestWheel.proceed(delta);
}
public TimeUtil()
{
Wheel w1 = new Wheel(1);
biggestWheel = w1;
Wheel w2 = new Wheel(2);
Wheel w3 = new Wheel(3);
Wheel w4 = new Wheel(4);
//w1.tickTime = _ticks_a_wheel * _ticks_a_wheel * _ticks_a_wheel * _ticks_a_wheel;
w1.oneTickTime = _ticksInWheel * _ticksInWheel * _ticksInWheel;
w2.oneTickTime = _ticksInWheel * _ticksInWheel;
w3.oneTickTime = _ticksInWheel;
w4.oneTickTime = 1;
w1.quickerWheel = w2;
w2.quickerWheel = w3;
w3.quickerWheel = w4;
w4.quickerWheel = null;
w4.slowWheel = w3;
w3.slowWheel = w2;
w2.slowWheel = w1;
w1.slowWheel = null;
timeSys = DateTime.Now.Ticks / 10000;
}
}
class Program
{
static void Main(string[] args)
{
TimeUtil timer = new TimeUtil();
timer.setTimeout(() => Console.WriteLine("2.5 sec later"), 2500);
timer.setTimeout(() => Console.WriteLine("1 sec later"), 1000);
timer.setTimeout(() => Console.WriteLine("1.5 sec later"), 1500);
for (; true;)
{
timer.update();
Thread.Sleep(21);
}
}
}
网友评论