Contents
  1. 1. 最大的前K个排名:
  2. 2. 非通知型的实时排名:
  3. 3. 通知型的实时排名:
    1. 3.0.1. 启服:
    2. 3.0.2. 获取自身排名:
    3. 3.0.3. 通知:
    4. 3.0.4. 区间查询:
  • 4. 非实时排名:
  • 这个貌似最近成为了面试常见问题,上次就被问到过,没答好,闲来无事就想一下。

    问题一般是酱紫说的:

    一个游戏,大概百万个玩家,按照积分从低到高有个排行榜,在各个玩家积分频繁变化的情况下怎样获得玩家的排名?

    根据情况细节的不同,大概有这3种解答方向:

    最大的前K个排名:

    属于产品层面上做了妥协的,不管怎样用户只能看到全服前K个排名,处理起来比较简单。

    常见的可以先用nth_element找到前K个,然后对前K个sort,不过这样子还是有些别扭,更自然的方式当然是直接对[0,K)进行partial_sort。

    partial_sort在vs2012上的实现就是对未排序的前K个建最大堆,然后依次遍历后续数组更新最大堆,使用内存有限,效率也不错。

    缺点除了不能看到所有排名之外,玩家也没办法知道自己当前的排名,而且进行区间查询比较困难。

    非通知型的实时排名:

    需要客户端主动来查询才得到排名,排名是实时准确的。

    百万量级是个很好的提示,基本上否定了O(n)及以上的算法,把答案圈定在了对O(logN)算法的选择上。

    问题是怎样在O(logN)时间里得到某个用户的排名呢?

    由于排名是个线性顺序产生的数据,默认情况下就算是BBST,也只能通过从root开始中序遍历得到,这样算法效率依然是O(n)。

    很自然想到每个节点多维护一个排名数据(相当于对排名做cache),虽然查询效率提高了,但是维护的代价是非常大的达到了O(n),所以对排名做cache的想法也只能放弃。

    虽然cache排名不可行,但是仔细思考,之所以它的复杂度为O(n)是因为这种操作并没有用到BBST的特性。如果更进一步想到对每个节点cache它的子节点个数的话,问题就引刃而解了。

    根据统计信息获得排名的过程大致是这样的:

    function GetRank(node)
    	rank = node->left ? node->left->GetNodeCnt() : 1
    	while node do
    		iRank += node->parent->right ? node->parent->left->GetNodeCnt() + 1 : 0
    		node = node->parent;
    	end
    	return rank
    end
    

    相比排名,BBST上统计子节点是满足算法复杂度的前提下比较容易办到的事情。

    由于现在BBST采用的惯用实现是RBTree(比如AVL之类的实现实践中性能不如RBTree),只需在原实现的基础上添加size字段和相应维护步骤即可。

    原来《CLRS》上写RBTree的时候作为扩展话题有谈到对RBTree进行修改以使它支持更多特性,不过当时对RBTree本身实现都不是太理解,所以对这个话题也是一带而过,以至于面试的时候发晕了。

    通知型的实时排名:

    在百万的数据量这个问题炸一看好像是无解的,实际上这种观点有点想当然了,能不能做和具体产品特性也有很大关系。

    一般需要满足的功能无非这两个:就是获取到自己的排名 & 查询某个区间的排名。

    启服:

    首先是起服时,因为这么大量的数据时不可能专门搞个表来存排名的,所以要从无序数据中根据积分重建排名数据。

    考虑到频繁变动的情况,数组是不考虑的,直接在链表上想办法。

    由于链表不支持常见的O(NlogN)排序,所以大量数据下排序可能有点恐怖。优化方案我的想法是加入跳跃表

    比如说百万的量级的话,建一个1000个节点左右的索引表,这样每次查找的量就能控制在10^3量级,速度会快很多。

    对于有的长时在线游戏刚开服的时候一下子大量玩家登录,这种性能表现可能是灾难性的。可以考虑以uID为key建一个BBST,节点保存指向有序链表对应节点的指针来解决吧。

    获取自身排名:

    这要分排行榜是用户主动打开还是被动打开的情况来说,因为主动打开的情况优化的空间更大,下面就以此为背景来说。

    用户上线后首次打开排行榜时,遍历链表找到自己的数据,在用户连接上保存节点指针,最后返回用户名次。

    这里存在要不要给节点记录名次的问题,记录后用户每次可以O(1)低成本获得自身排名,但维护颇为麻烦。不维护的话用户无从知道自己的排名,只能从有序链表遍历获得。

    假设是个玩家爱看排行榜的游戏,那么cache排名就成为一种必然,我们看看如何维护:

    如果是排名变化比较温和的游戏(每次排名变化范围不大),大可直接更新区间内(排名变化的区间为[该用户的旧排名, 该用户的新排名])所有节点的排名数据。不然的话,这种操作就成为了比较沉重的负担,不过我们可以乐观估计一下现实状况,跨度大的操作一般都是低频的,高频操作影响又小,所以实际运用中未必性能表现不佳。

    比如说,A用户在玩游戏,积分一次性产生了吓人的变化,我们首先顺着A在有序链表的节点往前移,直到找到积分比他高的把自己放到他后面,移动的时候顺路更新中间各个节点的排名及排名索引节点。

    通知:

    在更新各节点排名时,可以判断下当前节点对应的客户端是否在线,是否正在关注排行,是的话就发新排名过去。

    区间查询:

    至于区间排名查询,只需要先辅以索引表找到排名起始节点,再往后遍历一定数量即可。

    非实时排名:

    以前见过不少游戏这么干的,一般一天设置一个时间点或者有一个比较长的时间间隔才能刷新一次。猜测是没有找到比较合适的算法,实时更新计算时间控制不下来,只好由服务器找个时间统一排个序。

    Contents
    1. 1. 最大的前K个排名:
    2. 2. 非通知型的实时排名:
    3. 3. 通知型的实时排名:
      1. 3.0.1. 启服:
      2. 3.0.2. 获取自身排名:
      3. 3.0.3. 通知:
      4. 3.0.4. 区间查询:
  • 4. 非实时排名: