C-在网页游戏中,如何快速准确的计算某个人在全服中的排名?

发布于 2017-01-23 06:27:54 字数 64 浏览 1353 评论 4

在网页游戏中,经常会用到一些排排行榜,但是对于上千万的用户,如果快速的计算出一个比较准确的排行版以及每个人的排名?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

晚风撩人 2017-06-30 23:22:11

实时排行的话:redis的sorted set结构。

想挽留 2017-05-10 11:30:57

游戏中做实时排行的确意义不大,用Mysql就哦了,做定点更新。
不过做实时排名系统用 Redis的zset做这个轻而易举。

分享一篇介绍Redis的zset的数据结构的,转自 淘宝核心系统团队博客
Redis的zset本身就是一种支持排序的集合,而zset的实现,则使用了skip list数据结构。Skip list是一种多层次的有序链表,通过随机地选择层数来实现插入、查找和删除都是O(logn)的时间复杂度(和平衡树同样的效率,但实现比平衡树简单很多)。关于skip list的具体介绍可以参见William Pugh的论文:Skip Lists: A Probabilistic Alternative to Balanced Trees 。下面我们来分析一下redis中skip list的实现。
Redis中skip list主要有zskiplist和zskiplistNode两个数据结构:

typedef struct zskiplistNode {
robj *obj;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;

其中zskiplistNode中包含一个zskiplistLevel数组,数组的大小根据节点所在的层数(level)决定。backward指针是为了方便向后遍历而对skip list做的改进。

主要的API有:

zslCreate 创建一个zskiplist,并添加一个具有最高层数ZSKIPLIST_MAXLEVEL(代码中定义为32)的节点来管理分层的链表。
zslInsert 插入一个节点到zskiplist,并调整每一个层级的链表都是有序的。
zslDelete 从zskiplist删除一个节点,并调整剩余节点在每个层级都是有序的。
zslRandomLevel 为新加入的节点随机产生一个不超过ZSKIPLIST_MAXLEVEL的层数。
zslInsert和zslDelete函数都需要首先查找到合适的位置或节点,查找的代码很简单,直接包含在了这两个函数内:

x = zsl->header;
for (i = zsl->level-1; i >= 0; i–) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
compareStringObjects(x->level[i].forward->obj,obj) < 0))) {
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}

查找是从zskiplist现有的最高层开始向前,并在查找的过程中根据规则转向低层的链表继续,一直到skip list的最低层为止。同时看到redis的实现中允许相同的score存在(这时按对象的字符串进行比较),但不允许具有相同值的对象并存(集合的特性)。

下面通过一个例子来说明skip list的建立过程。

按顺序执行下列语句:

zslInsert(zsl, 5, obj1);              //level=1;
zslInsert(zsl, 3, obj2);              //level=2;
zslInsert(zsl, 4, obj3);              //level=1;
zslInsert(zsl, 1, obj4);              //level=3;
zslInsert(zsl, 2, obj5);              //level=1;

现在的zsl结构如下图所示,其中 level array 的数组下标是为了图例更直观,实际不占存储空间。为了保证图例的简洁,backward的指针没有画出,对应level 0红色指针相反方向的指针。

夜无邪 2017-03-26 12:34:45

如果不需要实时的话,可以创建一个排行表,用名次做主键,用户ID做索引,查某玩家排名用此表查,不要每次都根据规则去排序然后再计算排名。这个表定期更新就行了。实时的话,同楼上用redis,不过大部分游戏对排行不要求实时,没太大意义。

瑾兮 2017-02-17 15:04:33

这个应该要结合具体情况来进行操作,网页游戏大部分都是根据等级或者装备等特定的某些东西来进行排名。
处理的时候直接以一个大顶堆的方式计算存储,当一个满级玩家的这些参与排名的元素发生改变更新的时候,使用新值去堆中查找,看是否满足排名显示的条件即可。

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文