游戏积分排行榜的实现

　　游戏中的积分排行榜就是将玩家的某些属性抽象为“积分”，然后对积分进行排序，从而得到各个独立的排行榜。比如玩家的战力，等级，装备评分，成就点等等。实现排行榜的方法依需求而变，最简单的是Top N排名。

　　只排行最高的前N个玩家；N之外的玩家干脆提示未进排行榜。这种模式下通常N不会太大，如果以1000个为例，假如一个玩家的排名项是40个字节，那么存储起来大概只需要40K左右，在DB中当成一条记录保存就可以了。

　　服务器启动时把排行榜加载进来，会生成两个数据结构：排名数组：元素的内容是玩家ID和分数，数组按分数从大到小排序，数组索引即是排名名次。排名映射，玩家ID映射到数组索引，通过玩家ID马上就知道他的排名。

　　数据结构大概是(以lua为例):

　　维护排行榜的逻辑非常简单，通过插入排序来维护数组的有序，同时不断更新rankmap的映射关系；玩家积分变化时：通过rankmap检查玩家是否在排行榜中：如果没在排行榜，则生成排名项加到ranklist最后，同时更新rankmap。如果有在排行榜中，我们马上就能得到玩家的排名项。

　　接下来要比较玩家的新积分和旧积分，假设未进排行榜的旧积分为-1：如果新积分==旧积分，则不用处理。如果新积分>旧积分，则向前逐个比较排行项，小于新积分的排行项往后移，直到找到大于等于新积分的项，把玩家项插到它后面；这个过程要不断更新rankmap。如果新积分<旧积分，则向后逐个比较排行项，大于新积分的排行项往前移，直到找到小于等于新积分的项，把玩家项插到它前面；这个过程要不断更新rankmap。最后判断ranklist的长度是否超出N，超出则把ranklist的最后项删除，同时更新rankmap。使其保持最长为N的长度。

　　这个算法在实践中效率是很高效的，因为游戏中的积分经常是小幅度的增减，这表示每次积分变化，排行项的移动次数不会很多。

　　Top N能够精确的列出前N个玩家的排名，但如果我在N之外，也想知道大概的排名要怎么办呢，这时就得思考一种预估排行的算法。

　　在程序的诸多优化方法中，有一种很典型的降低精度法，假如我们对结果要求不用很精确，那么可以通过分块或分段，把数据量大大减少，然后通过插值的方法计算出大概的值。比如客户端的压缩纹理，把图像划分成NxN的小块，用一个优化的数据结构来表示这NxN的像素范围，这能使显存占用减少数倍之多。

　　排行榜的预估排名也可以用类似的思想，把积分按固定的范围分成多个段，每个段保存着落入该段的玩家数，于是就有了下面的积分段数组：

　　假如我的积分是120，计算预估排名的过程是这样的：从最高分段往前遍历，直到找到我的积分在哪个分段，这个过程不断累加高分段的玩家人数。这里是。计算我在分段中的预估排名：。两项相加即得到我的预估排名：，这个排名是基于0开始的。

　　可以用max(N, rank)确保计算出来的排行不会小于N，这样就可以和Top N相结合使用。

　　分段的积分范围决定了预估的精确度，范围越小精度越高，分段的数量也越多，但这会加大存储量，也会影响计算效率。

　　如果分段数确实很多，就要想办法优化遍历的次数。我们可以把遍历低到O(logN)，方法是用多层分段。每一层的分段数是2的幂，且逐层减少，直到最后一层为2。下面是一个例子：第1层每个分段的积分范围是99，即0~99, 100~199等，分段中的值为落入该分段的玩家数。每2层每个分段的积分范围是上一层的2倍，即0~199, 200~399等，显然分段中的玩家数是上一层两个分段之和。以此类推，最后一层(第3层)是2个分段

　　现在要查询积分为210的玩家排名：从第3层开始，依次检查第2，1个分段，得到玩家在第1个分段中，即0~399这个范围；记住积分比我高的玩家人数是132。接着到第2层，检查第2，1个分段，得到玩家在第2个分段中，即200~399这个范围。接着到第3层，检查第4，3个分段，得到玩家在第3个分段中。累加积分比我高的玩家数。最后计算出玩家的预估排名：。

　　这就是玩家的排名，积分段越多效率优势就越明显。玩家积分变化时，需要先减少旧积分段的玩家数，然后再增加新积分段的玩家数，这个过程需要O(2*logN)的复杂度。另外，预估排行需要玩家自己维护旧积分和新积分。

　　如果玩家的新积分超过最大积分，那就得按2的幂扩大积分段，比如上面第1层扩大为16个段，第2层扩大为8个段，第3层扩大为4个段，同时要创建第4层容纳2个积分段。

　　前面的Top N和预估排行应该能应付大多数情况了。但还有一些排行榜要求所有玩家都有排名，比如全局竞技场，每一个玩家不单要知道自己的排名，还要看得到他前后一些玩家的排名。此时我们只能用全排方式，即每一个玩家都参与精确排行。

　　其实还是可以用类似Top N的做法的，ranklist可以用链表，rankmap为玩家ID到链表结点的映射，结点里面保存着玩家ID，积分，和名次。积分改变时，移动链表结点，使之保持有序，同时更新结点的排名。

　　这种看似存在大量移动结点的隐患，实际上大量移动的机率很小，因为积分都是小范围变动的。有真实线上的游戏采用这种做法，活跃玩家在10W+级别，效果非常不错。

　　另一种做法是用Redis的zset，相信也有很多游戏在用。简单说zset通过dict和skiplist来保证查询更新都是O(log(N))复杂度。通过dict从玩家ID找到分数，然后通过skiplist找到玩家排名。有兴趣的直接看起来。如果只想看skiplist的实现，前面500行就够了。

　　不过zset有一个地方不是太好，当积分相同时，它通过比较字符串key的"大小"确定谁在前面，符合直觉的排名应该是谁先进排行榜谁就在前面。

　　由于Redis用得非常多，源代码也在那儿，研究它的人也多，我就不在这儿搬门弄斧了。