简单高效的排行榜算法——树状数组

0 问题场景

在互联网业务中,为了刺激玩家活跃度,通常都会制作榜单,让用户能够看到自己在榜单中的名次。用户要看到的内容是:新的分数排行是多少名,相比之前是前进了,还是后退了,具体前进后退的数值是多少。例如充值排行榜,游戏分排行榜,活跃度排行榜等。由于互联网用户基数大,有些平台参与排行的用户可以达到上千万。但是排行榜最重要的就是时效性,能够让用户越早看到排行更新越好。

对于庞大的榜单,每次其中一个元素更新,都要重新排序,即使用快速排序,对CPU运算的消耗都是巨大的,很容易造成卡顿。很多互联网业务都采用离线定时更新榜单的方案。例如每天凌晨4点的数据切片,离线排序更新,更新后展示最新的榜单。这种方案在程序性能和用户体验间做了折衷,既保证了每天更新,又不至于实时更新导致运算量太大,算不出来。

有没有更高的解决方案,可以实时查看用户排行变化呢?一个有序的排行榜,只是一个用户的数据发生变化,就要所有数据重新排序,能只做到部分排序吗?

对于这两个问题,可以利用一种高级的数据结构「树状数组」,再结合对排行榜的算法来实现。

1 排行榜实现及优化方案

我们先梳理下排行榜的通用实现方案,再查看下针对具体的步骤进行优化。
一个通用排行榜的实现方案步骤如下:

  1. 已经有一个排好序的排行榜;
  2. 当用户分数有更新时,保存用户老的排行榜名次和老的分数;
  3. 更新用户新的分数,并更新排行榜,获取新排行名次;
  4. 展示新老名次的差异,结束。

难点就在第二点,如何更新排行榜。最简单粗暴的想法是,更新排行榜中对应的分数,然后调用快速排序对数组再重新排序一次。快速排序时间复杂度是nlog(n)的,如果有1000万人参与,每次就要进行上亿次的比较。如果每秒有一千个玩家修改分数,要执行千亿次运算。对于排行榜系统的性能消耗是巨大的,做不到实时展示排行数据更新。

原先已经排好序的数组,只有一个元素的值发生了变化,其他元素的相对顺序是不用更改的。从这个角度来优化程序,能够做到快速实现排序优化。使用树状数组,能够做到修改和查询都是log(n),那么对于1000万人参与的榜单,比较次数最多只需要23次,一千个玩家每秒修改,只需要23000次比较。单进程都可以承受住。而且树状数组底层是构建在数组之上的,数据结构简单,容易持久化,能够方便地保存在共享内存中。当常驻进程重启时能够快速恢复。

说了树状数组这么多好处,这么适合排行榜业务的实现,下面我们来介绍下树状数组的原理,以及在排行榜业务中使用的方法。

2 树状数组实现排行榜

我们利用树状数组来实现排行榜功能,能够在Olog(N)的复杂度实现查询和修改功能。下面先介绍树状数组的原理,再介绍如何利用树状数组来实现排行榜。由于涉及到学习算法,还有应用。本节的两个内容需要对照查看才能理解,建议对下面两小节的内容,先概览熟悉基本概念,再逐渐研究细节。并没有严格的先后顺序之分。

2.1 树状数组原理

树状数组(Binary Indexed Tree),又以其发明者命名为Fenwick树。可以在O(logn)时间内得到数组任意前缀和,并能够在O(log(n))时间内支持动态单点的值的修改。空间复杂度是O(n)。

所有的正整数,都可以表示为2的幂和。 N=\sum_{i=1}^m2^{ki} ,ki为二进制表示时,为1位的位置。

例如34=2^1+2^6;12 = 2^2+2^3;

我们设一个整数数组元素个数为N,数组名为A,包含元素为A_{j}(1<=j<=N)

对于一个整数i,lowbit(i)表示i的二进制最后一个位置1,所代表的值。(例如lowbit(12)= 4,lowbit(34)=2)

构造树状数组 BIT_{i} = \sum_{j=i-lowbit(i)+1}^{i}A_{j}

BIT[i]=A[i-lowbit(i)+1] + A[i-lowbit(i)+2] + ... + A[i]

所表示的数学意义为,下标为i的树状数组元素,为原数组A[i]往前lowbit(i)个元素的和(包括A[i])。

对于树状数组元素BIT[i],可以画一棵树表示,树中的父节点表示的区间和,覆盖子节点表示的区间和。

下图为i=8时画出的树。

树状数组是在数组上建立的一种树形关系结构。

以上图为例,A数组是原始存储数据的数组,有8个元素。C数组是按照每个下标覆盖2次幂范围得到的新的子序列和的数组。

BIT1 = A1 (1的二进制表示为1,有0个0,覆盖1个元素)

BIT2 = A1 + A2(2的二进制表示为10,有1个0,覆盖2个元素)

BIT3 = A3(3的二进制表示为11,有0个0,覆盖1个元素)

BIT4 = A1 + A2 + A3 + A4(4的二进制表示为100,有2个0,覆盖4个元素)

BIT5 = A5(5的二进制表示为101,有0个0,覆盖1个元素)

BIT6 = A5 + A6(6的二进制表示为110,有1个0,覆盖2个元素)

BIT7 = A7(7的二进制表示为111,有0个0,覆盖1个元素)

BIT8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8(8的二进制表示为1000,有3个0,覆盖8个元素)

有了树状数组BIT[i],我们就可以实现求原数组A[i]的前缀和,还有A[i]中单个元素修改时快速更新BIT[i]数组的功能

一、求原数组A的前缀和

假设求原数组A的前i个元素的和Sum[i],对于整数区间[1,i],可以表示为两个区间[1, i-lowbit(i)],[1-lowbit(i), i]。

如果设j=i-lowbit(i),那么j<=i并且Sum[0] = 0,则Sum[i] = Sum[j] + BIT[i];之后再逐步求解Sum[j],直到递推到Sum[0] = 0,便计算出前缀和Sum[i]。

二、原数组某个元素A[i]修改,同步修改树状数组BIT

当某个元素A[i]修改时,所有包含A[i]的树状数组元素BIT[j]都要进行相应的修改。

对于A[i],BIT[i]肯定包含A[i]的和。再根据上面的树形结构,

BIT_{i_{k+1}} = BIT_{i_{k}} + lowbit(i_{k}) 其中 (i_{0}=i, i_{k+1}<=N)

2.2 代码实现

根据上一小节的分析,可以用代码实现树状数组。
对于求lowbit(n),可以用n&(n^(n-1))得到,由于在C++中用补码表示负数,可以写为n&(-n)。用函数封装为

int lowbit(int x)
{
    return x & (-x);
}

求数组A的前i项和为

int sum(int i)//求前i项和 
{ 
    int s=0; 
    while(i>0) 
    { 
        s+=BIT[i]; 
        i-=lowbit(i); 
    } 
    return s; 
}

修改原数组A[i]元素,增加val值

void add(int i,int val) 
{ 
    while(i<=n) 
    { 
        BIT[i]+=val; 
        i+=lowbit(i);  
    } 
}

2.3 树状数组优化排行榜

如何使用树状数组来实现排行榜的需求呢?要经过一些转化。

我们把要排行的分数划定一个区间范围。假设分数都是整数,最大值MAX_SCORE为1,000,000分。

则原始数组A[i]表示具有分数为i的值的用户数量,然后求出BIT[i]数组。假设一个人的分数为j,则排名为BIT[MAX_SCORE]-BIT[j-1]。

利用上小节的代码很容易就实现了。

排行榜封装的代码如下

const int MAX_SCORE = 1000000;
int BIT[MAX_SCORE + 1]={0};//初始时所有分数的人数都是0
while(true)
{
    int uid, newScore, oldScore;
    GetUserInfoReq(&uid, &newScore, &oldScore);//假设收到请求,获得uid用户的最新分数为newscore,上次更新分数为oldscore;
    int oldRank = sum(MAX_SCORE)-sum(oldScore)+1;//查询旧排名
    //更新为新排名
    add(oldScore, -1);//先给旧分数的人数减一
    add(newScore,  1);//再给新分数的人数加一
    int newRank = sum(MAX_SCORE)-sum(newScore)+1;
    //返回用户新排名newRank,和老排名oldRank供前端展示
    SetUserInfoRsp(uid, newScore, newRank, oldScore, oldRank);
}

可以把用户的分数数据存储在用户资料中,排行榜模块只存储树状数组用来排名。最开始初始化时,可以遍历所有用户资料,获取每个用户的score,然后调用add(score, 1)完成全部初始化。之后用上面的代码,在每次分数有更新的时候调用获取排名变化。

核心代码只有30几行,而且由于是存储在数组中,一块连续的内存,可以把树状数组放到共享内存中。即使进程重启,也能够马上恢复服务。

使用树状数组有前提条件:

1、就是不能存储分数为0的玩家的排名;

2、分数要都是整数;

3、要有上限,最大不能超过MAX_SCORE范围。

虽然有诸多限制,但都能通过业务逻辑处理。如果分数有小数,可以乘以相应的倍数,转换成整数。例如充值1.01元,可以把单位转换成分来存储101分。上限可以根据业务逻辑调整,即使正整数的最大表示2^32,log(n)也只需要32次处理,远远小于O(n)的处理。

如果要突破限制,需要在业务层面和实现逻辑上再做些转换,一般都可以很好解决。

3 小结

对于排行榜需求,通过树状数组,能够实现实时更新和展示实时变化。排行榜实时更新的瓶颈是单值修改,整体排序。树状数组能够做到单值修改,部分更新,优化掉了排行榜瓶颈。

在实际开发中,遇到问题,要先梳理问题的步骤,找到瓶颈。针对瓶颈进行学习研究,对于高级数据结构要有所了解,在实际开发中,合理运用,能够达到简化开发,提升项目稳定和效率好处。同时在使用的过程中注意边界条件,让一些产品设计在边界条件内,能够达到产品特性用户满意和程序实现复杂度降低的双赢局面。


欢迎收听公众号

发表评论

电子邮件地址不会被公开。 必填项已用*标注