Timer

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1.引言 Golang在Timer(计时器)的实现中使用了四叉堆，而不是常见的二叉堆，这个问题引起了我的兴趣。 对于这个问题，网上的解释是这样的 但是我仔细查阅了资料以后，有了点有趣的发现。 2.说明 假设: 堆为d叉堆，堆中共有n个节点 备注: 时间复杂度的证明见d-ary heap Timer最常见的2个操作 1）Insert() 添加一个计时器。涉及 sift-up（上推）操作，时间复杂度为O(log n / log d) Python代码 import math result = math.log(n, d) 时间消耗（需要交换或者比较的次数） n(数量) 二叉堆 四叉堆 八叉堆 1w 13.3 6.64 4.43 10w 16.61 8.30 5.54 100w 19.93 9.97 6.64 1000w 23.25 11.63 7.75 2) Delete() 指定时间到达后，清除计时器。涉及 sift-down（下推）操作，时间复杂度为O(d * log n / log d) Python代码 import math result = d * math.log(n, d) 时间消耗（需要交换或者比较的次数） n(数量) 二叉堆 四叉堆 八叉堆 1w 26.58 26.58 35.43 10w 33.33 33.33 44.29 100w 39.86 39.86 53.15 1000w 46.51 46.51 62.01 3. 结论 正常情况下，插入操作：多叉堆执行性能优于二叉堆; 删除操作：多叉堆执行性能弱于二叉堆。 但是细心的朋友应该已经发现，四叉堆插入操作的耗时只有二叉堆的一半，而删除操作的耗时与二叉堆完全相同。 这么一对比，优势确实显著。 ...

版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 起因 我们有一个业务场景(高并发)，收到的每个任务都必须在很短的时间内完成，然后回报给调用方，因此每个任务都需要设定定时器。显然golang 默认的timer是不能支持这种场景的，因此我在delayqueue的基础上自己实现了一个库gtimer GitHub地址 timer 用golang实现的定时器，基于delayqueue 实现 实现受到了Java DelayQueue.java的启发 源码地址 DelayQueue.java 依赖的几个结构依次为为 timer -> delayqueue -> priorityqueue -> heap 由于golang的Condition不支持wait一段时间，所以使用golang原生的Timer来替代了Condition在delayqueue中的作用 Installation Install: go get -u github.com/vearne/gtimer Import: import "github.com/vearne/gtimer" Quick Start package main import ( "fmt" log "github.com/sirupsen/logrus" "github.com/vearne/gtimer" "math/rand" "strconv" "sync/atomic" "time" ) const ( PRODUCER_COUNT = 10 CONSUMER_COUNT = 10 TARGET_COUNT = 1000000 ) var ops int64 = 0 func main() { st := gtimer.NewSuperTimer(CONSUMER_COUNT) t1 := time.Now() for i := 0; i < PRODUCER_COUNT; i++ { go push(st, "worker"+strconv.Itoa(i)) } time.Sleep(100 * time.Millisecond) for { v := atomic.LoadInt64(&ops) if v >= TARGET_COUNT { st.Stop() break } else { time.Sleep(100 * time.Millisecond) } } t2 := time.Now() log.Infof("cost:%v\n", t2.Sub(t1)) } func DefaultAction(t time.Time, value string) { // fmt.Printf("trigger_time:%v, value:%v\n", t, value) atomic.AddInt64(&ops, 1) } func push(timer *gtimer.SuperTimer, name string) { r := rand.New(rand.NewSource(time.Now().UnixNano())) for i := 0; i < 1000000; i++ { now := time.Now() t := now.Add(time.Millisecond * time.Duration(r.Int63n(300))) value := fmt.Sprintf("%v:value:%v", name, strconv.Itoa(i)) // create a delayed task item := gtimer.NewDelayedItemFunc(t, value, DefaultAction) timer.Add(item) } } use NewDelayedItemFunc, we can create a task ...