我正在使用redis编写一个应用程序，我需要一个优先级队列--项目被分配一个1到10之间的优先级，然后弹出一个最高优先级的项目（顺序无关紧要），从我的理解来看，优先级集的ZADD和BZPOPMAX似乎非常适合这个用例。
然而，我在Redis文档中注意到这两个操作都是O（LOG（N）），而列表和集合的等价操作是O（1）。
这就引出了几个与性能相关的问题：
- 即使我知道队列的优先级范围很小（1-10），但redis优先级集实现的实际大O仍然是O（LOG（N））吗？
- 是否值得追求另一种实现（也许是使用对列表和集合的几个调用）？我的队列中可能有数十万甚至数百万个项。
1条答案
按热度按时间91zkwejq1#
即使我知道队列的优先级范围很小（1 - 10），但redis优先级集实现的实际大O仍然是O（LOG（N））吗？
Redis排序集的时间复杂度与得分的范围无关（在你的例子中，是优先级），而是与排序集中的项目数量有关，所以实际的大O仍然是
O(LOG(N))。是否值得追求另一种实现（也许是使用对列表和集合的几个调用）？
使用Redis列表和Redis集合是无法实现这个目标的，因为Redis集合是无序的，搜索列表和访问列表中的项目（除了列表的头部和尾部）都是O（N）。
O(LOG(N))并不慢，即使你有100万个项目，调用ZPOPMAX只需要大约20次比较就可以得到结果，这是相当快的。在选择更复杂的算法之前，尝试简单的解决方案并进行基准测试。