关于实时TopN排名算法的思考 |
您所在的位置:网站首页 › msi实时排名 › 关于实时TopN排名算法的思考 |
关于实时TopN排名算法的思考
0.引言1.TopN实时排名算法1.1 一个失败的方案1.2 现成的数据结构?1.3 合理的方案
Reference
0.引言
实时排名是网络应用中常见的功能。根据需求不同,大概可以分为以下几类: i. TopN排名ii. 全数据排名作为通用需求,我们必须做如下假设: a. 用户基数较大b. 排名数据更新较频繁c. 用于排序的数据(score)范围不确定d. 用作排名的score只会增加,不会减少基于以上假设,全数据排名就是海量数据处理问题,一般认为内存难以胜任,一般通过数据库(如redis)实现,本文暂不讨论。 1.TopN实时排名算法这里,我们假设: N的范围有限(如1000),榜单数据内存完全可以处理那么,问题来了。如何设计数据结构和算法,来满足大批量用户频繁更新榜单情况下的实时排名需求? 1.1 一个失败的方案曾经看到一个实现,方案如下: a. 定义一个长度为N+1的数组b. 更新数据时,将新数据放到数组尾部c. 对数组排序,如果数组长度为N+1,则移除尾部元素咋一看,由于榜单数据较小,每次更新排序好像可行,但是随着用户基数和更新频度增加, 这个算法无疑跟DB设计把query建立在没有index的table上一样可怕。 随着更新频度提升,这个sort操作无疑将成为CPU的噩梦。 低效率的算法不会出bug,但是隐藏在角落偷偷的吃CPU,还很难被发现。 因此,该方案不可取。 1.2 现成的数据结构?经典的有序数据结构,如 红黑树Heap貌似可以满足这种需求。 但是,我们知道,平衡二叉树的高效操作是在于快速查找,然而维护一棵树的平衡(插入,删除元素),却是成本很高的操作。 因此,不可取。 1.3 合理的方案这个功能里有一个令人头疼的要求,就是客户端要实时能够查看到排名情况,那么问题来了: 这里的实时是否意味着服务端数据必须实时有序?答案是未必。我们知道,排序算法是计算机里面一个比较耗时的操作,频繁的排序更是无法忍受。 比较可行的方案是服务端不排序,只保证榜单记录TopN的数据,把实时排序的任务交给客户端执行。 服务器如何保证榜单上只记录TopN的数据?数据结构定义如下: type RankInfo struct{ name string // name of this rank element score int // rank score } type RankList struct { list []*RankInfo // unordered top N rank list min *RankInfo // the last one who own the minimum score in list nameMap map[string]*RankInfo // name->rankInfo }更新积分榜UdateRankList(name, score)的操作流程如下(假设score只会增加不会减少): a. 从nameMap查找指定的name是否已在榜单上,如果存在,更新积分。如果该对象==min,则重新查找积分最低对象赋值给min,返回。b. 如果list长度 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |