最近在做游戏排行榜服务器,记录一下想法。
定时排名:
- 只要前100,未进前100不记录排名。经典的TopK算法。 只求前 K 个值时可以考虑选择算法再处理前 K 项。Quickselect 的平均时间复杂度是 O(n),但不是固定“两次遍历”,普通实现的最坏情况也可能退化;如果前 K 还需要按名次排序,还要计算排序这 K 项的代价。
- 全服都要知道自己排名。可以定期调用
List.Sort,再按排序结果记录名次。我当时测得一百万名玩家排序约 400ms;这个数只对应当时的机器、数据和比较器,不能当作通用性能结论。List.Sort的时间复杂度是 O(n log n)。
实时排名:
假如有一百万名玩家,给全服所有玩家排名一次要400ms,100次就是40s,所以肯定不能每次玩家战力刷新时,排行榜执行一次List.Sort了。
- 新建一个RankList,包括一个双向链表和一个字典。双向链表的节点里包含前后节点,当前排名,当前的值。字典的key是玩家id,字典的value是对应节点。 初始化时调用一次List.Sort使List有序,之后倒序遍历,构建双链表。 每次插入会遍历到对应的节点,插入之后遍历刷新后面节点的排名。 找玩家名次直接用字典去找对应节点即可找到名次。
- 在1里提的RankList在每次玩家排名改变时都会让其后面节点排名加一,效率很低。可以把所有玩家分成区间,区间包括区间人数,最大值与最小值。当新加入一个玩家在区间里,区间人数就加一。区间内玩家排名改变也只是改变了区间内玩家的排名。排行榜一般都是两头人少,中间人多,这个方法的难点在于区间的划分,需要合理划分每段区间内的人数。
如果产品只要求定期刷新排名,周期性排序通常更简单,也可能足够快;如果需要高频实时更新、分页查询或严格时效性,就要根据读写比例和一致性要求另选结构。这里没有不依赖需求的“最优解”。
参考:Princeton 的 Quickselect 复杂度说明、Microsoft 的 List<T>.Sort 文档。
读到这里,感谢你。
