版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | 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. 结论

正常情况下,插入操作:多叉堆执行性能优于二叉堆; 删除操作:多叉堆执行性能弱于二叉堆。
但是细心的朋友应该已经发现,四叉堆插入操作的耗时只有二叉堆的一半,而删除操作的耗时与二叉堆完全相同。 这么一对比,优势确实显著。

参考资料

1.Heap (data structure)
2.Binary heap
3.d-ary heap
4.Golang 定时器底层实现深度剖析
5.数据结构:堆(Heap)


微信公众号

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据