如何跟踪玩家的排名？

Question

我有一个 Player class 和 score 属性：

class Player(game_engine.Player):

    def __init__(self, id):
        super().__init__(id)
        self.score = 0

此得分increases/decreases为玩家succeeds/fails做的目标。现在我需要告诉玩家他在玩家总数中的排名，例如

print('Your rank is {0} out of {1}')

首先我想到了所有玩家的列表，每当玩家发生任何事情时：

我看看他的分数是涨了还是跌了
在列表中找到他
移动他直到他的得分在正确的位置

但这会非常慢。可能有数十万玩家，一个玩家可以将自己的分数重置为 0，这意味着我必须将堆栈中的每个人都移到他之后。即使找到玩家也是 O(n)。

我正在寻找的是一个高性能的解决方案。 RAM 的使用并不是那么重要，尽管应该使用常识。我怎样才能使系统运行得更快？

更新信息： 每次他离开游戏服务器时，我都会使用 SQLAlchemy 将玩家的数据存储到 MySQL 数据库中，并在他每次加入服务器时加载它.这些是通过 'player_join' 和 'player_leave' 事件处理的：

@Event('player_join')
def load_player(id):
    """Load player into the global players dict."""
    session = Session()
    query = session.query(Player).filter_by(id=id)
    players[id] = query.one_or_none() or Player(id=id)

@Event('player_leave')
def save_player(id):
    """Save player into the database."""
    session = Session()
    session.add(players[id])
    session.commit()

此外，玩家的分数会在 'player_kill' 事件时更新：

@Event('player_kill')
def update_score(id, target_id):
    """Update players' scores upon a kill."""
    players[id].score += 2
    players[target_id].score -= 2

Answer 1

你遇到的问题是你想要对数据库进行实时更新，这每次都需要一个数据库查询。如果你在内存中维护一个分数列表，并以更合理的频率更新它（比如说每小时一次，或者甚至一分钟一次，如果你的玩家真的关心他们的排名），那么玩家仍然会体验到真实的 -时间进度与分数排名，他们无法真正判断更新是否存在短暂滞后。

有了内存中的排序分数列表，您可以立即获得玩家的排名（这里的瞬间，我的意思是在内存中进行 O(lg n) 查找），但要以缓存内存为代价，当然还有是时候更新缓存了。与每次有人想查看他们的排名时都要查询 100k 条记录相比，这是一个更好的选择。

详解sorted list，需要查询db获取，不过可以继续使用一段时间。也许您存储了 last_update，并且仅当此列表为 "too old" 时才重新查询数据库。因此，您可以快速更新，而不是一直尝试更新，而只是感觉像是实时的。

为了近乎即时地找到某人的排名，您使用了 bisect 模块，它支持在排序列表中进行二进制搜索。当你得到分数时，分数会被排序。

from bisect import bisect_left

# suppose scores are 1 through 10
scores = range(1, 11)

# get the insertion index for score 7
# subtract it from len(scores) because bisect expects ascending sort
# but you want a descending rank
print len(scores) - bisect_left(scores, 7)

这表示 7 分是第 4 位，这是正确的。

Answer 2

可以使用 SQLAlchemy 的 sort_by 函数提取此类信息。如果您执行如下查询：

leaderboard = session.query(Player).order_by(Player.score).all()

您将获得按分数排序的玩家列表。请记住，每次执行此操作时，您都会对数据库执行 I/O，这可能会相当慢，而不是保存数据 python 变量。

Answer 3

Redis 排序集有助于解决这种情况（文档使用排行榜作为示例用法）http://redis.io/topics/data-types-intro#redis-sorted-sets

您关心的关键命令是 ZADD（更新玩家排名）和 ZRANK（获取特定玩家的排名）。两个操作都是 O(log(N)) 复杂度。

Redis可以作为玩家排名的缓存。当您的应用程序启动时，从 SQL 数据填充 redis。在 mysql 中更新玩家分数时也会更新 redis。

如果您有多个服务器 processes/threads 并且它们可以同时触发玩家分数更新，那么您还应该考虑 mysql/redis 更新竞争条件，例如：

只从数据库触发器更新redis；或
序列化球员得分更新；或
让数据暂时不同步，延迟后再做一次缓存更新；或
让数据暂时不同步并以固定的时间间隔进行完整的缓存重建

如何跟踪玩家的排名？

How to keep track of players' rankings?

python

algorithm

ranking

rank

python-3.x