Java实现分数排名算法_海量⽤户积分排名算法探讨（转）某海量⽤户⽹站，⽤户拥有积分，积分可能会在使⽤过程中随时更新。现在要为该⽹站设计⼀种算法，在每次⽤户登录时显⽰其当前积分排名。⽤户最⼤规模为2亿；积分为⾮负整数，且⼩于100万。 PS: 据说这是迅雷的⼀道⾯试题，不过问题本⾝具有很强的真实性，所以本⽂打算按照真实场景来考虑，⽽不局限于⾯试题的理想环境。
存储结构
wo318
⾸先，我们⽤⼀张⽤户积分表user_score来保存⽤户的积分信息。
表结构：
⽰例数据：
下⾯的算法会基于这个基本的表结构来进⾏。
算法1：简单SQL查询
⾸先，我们很容易想到⽤⼀条简单的SQL语句查询出积分⼤于该⽤户积分的⽤户数量：select 1 + count(t2.uid) as rank from
user_score t1, user_score t2 where t1.uid = @uid and t2.score > t1.score
测向天线对于4号⽤户我们可以得到下⾯的结果：
算法特点
优点：简单，利⽤了SQL的功能，不需要复杂的查询逻辑，也不引⼊额外的存储结构，对⼩规模或性能要求不⾼的应⽤不失为⼀种良好的解决⽅案。
缺点：需要对user_score表进⾏全表扫描，还需要考虑到查询的同时若有积分更新会对表造成锁定，
在海量数据规模和⾼并发的应⽤中，性能是⽆法接受的。载人旅行箱
算法2：均匀分区设计
在许多应⽤中缓存是解决性能问题的重要途径，我们⾃然会想能不能把⽤户排名⽤Memcached缓存下来呢？不过再⼀想发现缓存似乎帮不上什么忙，因为⽤户排名是⼀个全局性的统计性指标，⽽并⾮⽤户的私有属性，其他⽤户的积分变化可能会马上影响到本⽤户的排名。然⽽，真实的应⽤中积分的变化其实也是有⼀定规律的，通常⼀个⽤户的积分不会突然暴增暴减，⼀般⽤户总是要在低分区混迹很长⼀段时间才会慢慢升⼊⾼分区，也就是说⽤户积分的分布总体说来是有区段的，我们进⼀步注意到⾼分区⽤户积分的细微变化其实对低分段⽤户的排名影响不⼤。于是，我们可以想到按积分区段进⾏统计的⽅法，引⼊⼀张分区积分表score_range：
表结构：
数据⽰例：
表⽰[from_score, to_score)区间有count个⽤户。若我们按每1000分划分⼀个区间则有[0, 1000), [1000, 2000), …, [999000, 1000000)这1000个区间，以后对⽤户积分的更新要相应地更新score_range表的区间值。在分区积分表的辅助下查询积分为s的⽤户的排名，可以⾸先确定其所属区间，把⾼于s的积分区间的count值累加，然后再查询出该⽤户在本区间内的排名，⼆者相加即可获得⽤户的排名。 乍⼀看，这个⽅法貌似通过区间聚合减少了查询计算量，实则不然。最⼤的问题在于如何查询⽤户在本区间内的排名呢？如果是在算法1中的SQL中加上积分条件：select 1 + count(t2.uid) as rank from user_score t1, user_score t2 where t1.uid = @uid and t2.score > t1.score and t2.score < @to_score
在理想情况下，由于把t2.score的范围限制在了1000以内，如果对score字段建⽴索引，我们期望本条SQL语句将通过索引⼤⼤减少扫描的user_score表的⾏数。不过真实情况并⾮如此，t2.score的范围在1000以内并不意味着该区间内的⽤户数也是1000，因为这⾥有积分相同的情况存在！⼆⼋定律告诉我们，前20%的低分区往往集中了80%的⽤户，这就是说对于⼤量低分区⽤户进⾏区间内排名查询的性能远不及对少数的⾼分区⽤户，所以在⼀般情况下这种分区⽅法不会带来实质性的性能提升。
算法特点
优点：注意到了积分区间的存在，并通过预先聚合消除查询的全表扫描。
缺点：积分⾮均匀分布的特点使得性能提升并不理想。
肠镜裤算法3：树形分区设计
均匀分区查询算法的失败是由于积分分布的⾮均匀性，那么我们⾃然就会想，能不能按⼆⼋定律，把score_range表设计为⾮均匀区间呢？⽐如，把低分区划密集⼀点，10分⼀个区间，然后逐渐变成100分，1000分，10000分 … 当然，这不失为⼀种⽅法，不过这种分法有⼀定的随意性，不容易把握好，⽽且整个系统的积分分布会随着使⽤⽽逐渐发⽣变化，最初的较好的分区⽅法可能会变得不适应未来的情况了。我们希望到⼀种分区⽅法，既可以适应积分⾮均匀性，⼜可以适应系统积分分布的变化，这就是树形分区。
我们可以把[0, 1,000,000)作为⼀级区间；再把⼀级区间分为两个2级区间[0, 500,000), [500,000, 1,000,000)，然后把⼆级区间⼆分为4个3级区间[0, 250,000), [250,000, 500,000), [500,000, 750,000), [750,000, 1,000,000)，依此类推，最终我们会得到
1,000,000个21级区间[0,1), [1,2) … [999,999, 1,000,000)。这实际上是把区间组织成了⼀种平衡⼆叉树结构，根结点代表⼀级区间，每个⾮叶⼦结点有两个⼦结点，左⼦结点代表低分区间，右⼦结点代表⾼分区间。树形分区结构需要在更新时保持⼀种不变量(Invariant)：⾮叶⼦结点的count值总是等于其左右⼦结点的count值之和。
以后，每次⽤户积分有变化所需要更新的区间数量和积分变化量有关系，积分变化越⼩更新的区间层次越低。总体上，每次所需要更新的区间数量是⽤户积分变量的log(n)级别的，也就是说如果⽤户积分⼀次变化在百万级，更新区间的数量在⼆⼗这个级别。在这种树形分区积分表的辅助下查询积分为s的⽤户排名，实际上是⼀个在区间树上由上⾄下、由粗到细⼀步步明确s所在位置的过程。⽐如，对于积分
499,000，我们⽤⼀个初值为0的排名变量来做累加；⾸先，它属于1级区间的左⼦树[0, 500,000)，那么该⽤户排名应该在右⼦树[500,000, 1,000,000)的⽤户数count之后，我们把该count值累加到该⽤户排名变量，进⼊下⼀级区间；其次，它属于3级区间的[250,000, 500,000)，这是2级区间的右⼦树，所以不⽤累加count到排名变量，直接进⼊下⼀级区间；再次，它属于4级区间的…；直到最后我们把⽤户积分精确定位在21级区间[499,000, 499,001)，整个累加过程完成，得出排名！
路灯远程控制系统
虽然，本算法的更新和查询都涉及到若⼲个操作，但如果我们为区间的from_score和to_score建⽴索
引，这些操作都是基于键的查询和更新，不会产⽣表扫描，因此效率更⾼。另外，本算法并不依赖于关系数据模型和SQL运算，可以轻易地改造为NoSQL等其他存储⽅式，⽽基于键的操作也很容易引⼊缓存机制进⼀步优化性能。进⼀步，我们可以估算⼀下树形区间的数⽬⼤约为2,000,000，考虑每个结点的⼤⼩，整个结构只占⽤⼏⼗M空间。所以，我们完全可以在内存建⽴区间树结构，并通过user_score表在O(n)的时间内初始化区间树，然后排名的查询和更新操作都可以在内存进⾏。⼀般来讲，同样的算法，从数据库到内存算法的性能提升常常可以达到10^5以上；因此，本算法可以达到⾮常⾼的性能。
算法特点
优点：结构稳定，不受积分分布影响；每次查询或更新的复杂度为积分最⼤值的O(log(n))级别，且与⽤户规模⽆关，可以应对海量规模；不依赖于SQL，容易改造为NoSQL或内存数据结构。
缺点：算法相对更复杂。
算法4：积分排名数组
算法3虽然性能较⾼，达到了积分变化的O(log(n))的复杂度，但是实现上⽐较复杂。另外，O(log(n))的复杂度只在n特别⼤的时候才显出它的优势，⽽实际应⽤中积分的变化情况往往不会太⼤，这时和O(n)的算法相⽐往往没有明显的优势，甚⾄可能更慢。
考虑到这⼀情况，仔细观察⼀下积分变化对排名的具体影响，可以发现某⽤户的积分从s变为s+n，积分⼩于s或者⼤于等于s+n的其他⽤户排名实际上并不会受到影响，只有积分在[s,s+n)区间内的⽤户排名会下降1位。我们可以⽤于⼀个⼤⼩为1,000,000的数组表⽰积分和排名的对应关系，其中rank[s]表⽰积分s所对应的排名。初始化时，rank数组可以由user_score表在O(n)的复杂度内计算⽽来。⽤户排名的查询和更新基于这个数组来进⾏。查询积分s所对应的排名直接返回rank[s]即可，复杂度为O(1)；当⽤户积分从s变为s+n，只需要把感应钎焊
rank[s]到rank[s+n-1]这n个元素的值增加1即可，复杂度为O(n)。
算法特点
优点：积分排名数组⽐区间树更简单，易于实现；排名查询复杂度为O(1)；排名更新复杂度O(n)，在积分变化不⼤的情况下⾮常⾼效。
缺点：当n⽐较⼤时，需要更新⼤量元素，效率不如算法3。
总结
上⾯介绍了⽤户积分排名的⼏种算法，算法1简单易于理解和实现，适⽤于⼩规模和低并发应⽤；算法3引⼊了更复杂的树形分区结构，但是O(log(n))的复杂度性能优越，可以应⽤于海量规模和⾼并发；
算法4采⽤简单的排名数组，易于实现，在积分变化不⼤的情况下性能不亚于算法3。本问题是⼀个开放性的问题，相信⼀定还有其他优秀的算法和解决⽅案，欢迎探讨！
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议