我的关注 |
¥0.1 定时器使用队列queue还是堆heap?
1

定时器使用队列queue还是堆heap?

大智若愚
修改
评论(0)
1个回答
1
采纳

看需求的不同有不同的设计实现。主要的设计数据结构有三种:先进先出队列、小顶堆、跳表。

队列

如果定时器任务每次插入的时候只需要插入到队列尾部,而且没有修改需求或只需要修改队列尾部,那么使用队列的效率是最高的。插入和删除的时间复杂度都是O(1)。
但是在大部分的业务需求都不会只需要插入到尾部,如一次插入3个任务:(1,任务执行时间7点)、(2,任务执行时间10点)、(3,任务执行时间8点)。那么在这样的需求下,如果使用队列的时:

  • 添加任务的时间复杂度是O(n),因为需要遍历整个表才能插入。由于无法估算任务最多有多少,所以无法使用数组结构,所以无法使用二分查找。
  • 删除和读取时O(1),只需要读取和删除队首即可。
  • 修改任务的时间复杂度也是O(N).因为也需要遍历表

相比队列,使用最小队效率是最高的:

  • 读取的时间复杂度是O(1)
  • 删除队首的时间复杂度是log(n) ,需要跟新堆(时间复杂度logn)
  • 添加元素到任意位置的时间复杂度是log(n),需要跟新堆(时间复杂度logn)
  • 修改任意位置的元素的时间复杂度是log(n),需要跟新堆(时间复杂度logn)

跳表

同样的,也可以使用 跳表skip list来实现。其时间复杂度和堆是一样的。
由于redis 的sorted list是跳表结构,在实际使用中,可以直接使用redis的sorted list来实现定时器任务。

时间复杂度对比

读首元素 随机增 随机改 随机删除
队列 O(1) O(N) O(N) O(N)
O(1) log(N) log(N) log(N)
跳表 O(1) log(N) log(N) log(N)

.

采纳答案
hong
修改
评论 (0)
撰写回答