实时排行榜要求实时,无延迟。 为了实现这一点,必须在插入时排序,而不是在读取时排序。 读取时排序的工作量非常大。 以下是一些可能的选择。
桶排序
在游戏开发中电路模拟小程序网站排名,很多时候都需要对分数进行排名。 例如,分数范围是1-5000,但可能有数百万用户。 显然很多人在这些场景中都有相同的分数。 此时,你可以将1-5000设计成5000个桶,然后根据每个用户自己的分数将其放入相应的分数桶中。
查询实时排名topN,只需要将得分高的前几桶组合起来展示即可。
桶排序
Redis实现
使用redis有序集进行排序。 排序集是一个有序列表。 使用zadd、zrange、zrank可以轻松实现实时排名。
将三个人的分数相加
获取所有人(有分数)
按倒序排列所有人(包括分数)
获取张三的排名(正序)
获取张三的排名(倒序)
redis的排序集是使用跳表(skip list)算法实现的。 时间复杂度为O(log(N))。 跳表是在数组的基础上额外创建一个父数组电路模拟小程序网站排名,增强了数组的查找效率。 另外,由于跳表插入一个元素,只需要改变前驱和后继的引用就可以轻松插入一个元素,所以性能比平衡树更好(平衡树需要各种旋转)。
平衡树
Java的树形图是基于红黑树实现的。 您可以尝试通过树形图来实现排行榜。
通过这些方法,需要解决几个问题:
1、分数相同时如何解决? 我目前想到的是通过分段来确定唯一性。 将小数点后的位数设置为用户 ID。
2、如何实时获取指定用户的评分和排名?
抛砖引玉,欢迎告诉我们您的计划!