游戏排行榜

最近在做游戏排行榜服务器，记录一下想法。

定时排名：

1. 只要前100，未进前100不记录排名。经典的TopK算法。
   关于TopK，看知乎有个O(n)的方法：先遍历找到第n大的元素，之后根据这个元素划分。这样只需遍历两次，所以时间复杂度是O(n)。
2. 全服都要知道自己排名。也就是在排名时用一次语言内置的Sort方法，并且记录一下自己的排名。经测试在普通配置电脑上使用C#中给一百万名玩家排名一次仅需400ms左右，内置的Sort排序性能真的不错。

实时排名：

假如有一百万名玩家，给全服所有玩家排名一次要400ms，100次就是40s，所以肯定不能每次玩家战力刷新时，排行榜执行一次List.Sort了。

1. 新建一个RankList，包括一个双向链表和一个字典。双向链表的节点里包含前后节点，当前排名，当前的值。字典的key是玩家id，字典的value是对应节点。
   初始化时调用一次List.Sort使List有序，之后倒序遍历，构建双链表。
   每次插入会遍历到对应的节点，插入之后遍历刷新后面节点的排名。
   找玩家名次直接用字典去找对应节点即可找到名次。
2. 在1里提的RankList在每次玩家排名改变时都会让其后面节点排名加一，效率很低。可以把所有玩家分成区间，区间包括区间人数，最大值与最小值。当新加入一个玩家在区间里，区间人数就加一。区间内玩家排名改变也只是改变了区间内玩家的排名。排行榜一般都是两头人少，中间人多，这个方法的难点在于区间的划分，需要合理划分每段区间内的人数。

实际上游戏并不需要实时排名，直接Sort才是最优解。