前面一篇文章介绍了一种基于树形的实时排行榜实现，在较大规模数据下表现良好。但其并不适用于每个场景，尤其在区间较大，但实际数据记录数并不多的情况下，因为它的节点数是与区间相关的，大量的内存耗费在节点上。
针对这种场景，有一种更好的算法，即分桶式。其具体原理引用云风文章的一段话描述：
陌陌争霸中用于排名的分数区间不大，也就是 0 分到 5000 分。而参与排名的人数众多，数以百万计。对百万用户做插入排序，每个插入即使是 O(N) 的也不可接受。可事实是大量玩家的分数相同，都是并列排名的。所以我们只需要做 5000 个桶，每个桶里仅记录这个分数有多少个人就可以了。
当玩家分数变迁，把原来的桶减一，新的桶加一。这个操作就是 O(1) 的。
而排行榜的查询仅需要把当前分数靠前的桶累加，就能获知查询者的名次。对于上百万玩家，看到哪些人和你并列的人的名字是没有意义的。这个查询虽然是 O(n) 复杂度，但 n 只有区区 5000 ，还可以做 cache 以应对查询频率远高于更新频率的情况。
真正需要精确知道人名的是榜单的前 200 个人，而对前 200 个人做插入排序也很快，所以并不会造成性能问题。
其实可以看到，云风描述的应用场景和我描述的是两个方向的，区别就在于是否需要精确计算每个玩家的排名，分桶式在这两种场景下都适用。
算法很简单，按照惯例，直接展示代码，完整代码请参看文末。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
public class LeaderboardPile<Extra extends LeaderboardPileExtra> {
class LeaderboardBucket {
public int lowerKey = 0;
public int upperKey = 0;
public int number = 0;
public ArrayList<Extra> extraList = new ArrayList<Extra>();
}
private int lowerKey = 0;
private int upperKey = 0;
private int bucketNumber = 0;
private ArrayList<LeaderboardBucket> buckets = new ArrayList<LeaderboardBucket>();
public void setup(int lowerKey, int upperKey, int bucketNumber) {
assert (upperKey - lowerKey) / bucketNumber > 0;
assert (upperKey - lowerKey) % bucketNumber == 0;
this.lowerKey = lowerKey;
this.upperKey = upperKey;
this.bucketNumber = bucketNumber;
setupBucket();
}
public void insert(int key, Extra extra) {
insertIntoBucket(key, extra);
}
public void remove(int key, Extra extra) {
removeFromBucket(key, extra);
}
public void change(int oldKey, int newKey, Extra extra) {
remove(oldKey, extra);
insert(newKey, extra);
}
public int getRanking(int key, Extra extra) {
return getRankingOfBucket(key, extra) + 1;
}
public LeaderboardPileData getRankingN(int n) {
LeaderboardPileData data = null;
int ranking = n;
int bucketIndex = 0;
for (LeaderboardBucket bucket : buckets) {
if (ranking > bucket.number) {
ranking -= bucket.number;
bucketIndex += 1;
} else {
break;
}
}
if (bucketIndex < 0 || bucketIndex >= bucketNumber) {
return data;
}
LeaderboardBucket bucket = buckets.get(bucketIndex);
if (bucket == null) {
return data;
}
if (ranking <= 0 || ranking > bucket.number) {
return data;
}
for (Extra extra : bucket.extraList) {
ranking -= 1;
if (ranking <= 0) {
data = new LeaderboardPileData();
data.key = extra.key;
data.ranking = n;
data.extra = extra;
break;
}
}
return data;
}
public ArrayList<LeaderboardPileData> getTopN(int n) {
ArrayList<LeaderboardPileData> dataList = new ArrayList<LeaderboardPileData>();
int count = 0;
for (LeaderboardBucket bucket : buckets) {
for (Extra extra : bucket.extraList) {
LeaderboardPileData data = new LeaderboardPileData();
data.ranking = ++count;
data.key = extra.key;
data.extra = extra;
dataList.add(data);
if (count >= n) {
return dataList;
}
}
}
return dataList;
}
private void setupBucket() {
if (lowerKey > upperKey) {
return;
}
for (int index = 0; index < bucketNumber; ++index) {
LeaderboardBucket bucket = new LeaderboardBucket();
bucket.lowerKey = getBucketLowerKey(index);
bucket.upperKey = getBucketUpperKey(index);
bucket.number = 0;
bucket.extraList.clear();
buckets.add(bucket);
}
}
private void insertIntoBucket(int key, Extra extra) {
final int bucketIndex = getBucketIndex(key);
LeaderboardBucket bucket = buckets.get(bucketIndex);
if (bucket != null) {
extra.key = key;
bucket.extraList.add(extra);
bucket.extraList.sort((Extra left, Extra right) -> left.compareTo(right));
bucket.number += 1;
}
}
private void removeFromBucket(int key, Extra extra) {
final int bucketIndex = getBucketIndex(key);
LeaderboardBucket bucket = buckets.get(bucketIndex);
if (bucket != null) {
extra.key = key;
bucket.extraList.remove(extra);
bucket.extraList.sort((Extra left, Extra right) -> left.compareTo(right));
bucket.number -= 1;
}
}
private int getRankingOfBucket(int key, Extra extra) {
int ranking = 0;
final int bucketIndex = getBucketIndex(key);
for (int index = 0; index < bucketIndex; ++index) {
LeaderboardBucket bucket = buckets.get(index);
if (bucket != null) {
ranking += bucket.number;
}
}
LeaderboardBucket bucket = buckets.get(bucketIndex);
if (bucket != null) {
extra.key = key;
ranking += getBucketRanking(bucket, extra);
}
return ranking;
}
private int getBucketLowerKey(int index) {
final int bucketLowerKey = getBucketUpperKey(index + 1) + 1;
return bucketLowerKey;
}
private int getBucketUpperKey(int index) {
final int stepKey = getStepKey();
final int bucketUpperKey = upperKey - stepKey * index;
return bucketUpperKey;
}
private int getBucketIndex(int key) {
if (key < lowerKey) {
return bucketNumber - 1;
}
if (key > upperKey) {
return 0;
}
final int stepKey = getStepKey();
final int diffKey = upperKey - key;
final int index = diffKey / stepKey;
return index;
}
private int getBucketRanking(LeaderboardBucket bucket, Extra extra) {
int ranking = 0;
for (Extra bucketExtra : bucket.extraList) {
if (extra.compareTo(bucketExtra) > 0) {
ranking += 1;
} else {
break;
}
}
return ranking;
}
public int getStepKey() {
final int stepKey = (upperKey - lowerKey + 1) / bucketNumber;
return stepKey;
}
}
|
采用这种做法，需要在服务器启动时重新构建排行树，先确定排行区间，然后依次插入每个玩家数据。运行期间，玩家数据等改变时，先删除旧的排行，再插入新的排行。
该算法在面对数据分布不均、同区间玩家过多情况时，性能会大幅退化，可将ArrayList替换为更高效的数据结构，或变通需求。
公共库仓库：JMetazion
服务器示例仓库：JGameDemo