python - 如何跟踪玩家的排名？

Question

我有一个带有 score 属性的 Player 类:

class Player(game_engine.Player):

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

随着玩家成功/未能完成目标，该分数会增加/减少。现在我需要告诉玩家他在玩家总数中的排名，例如

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

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

1. 我检查他的分数是增加还是减少
2. 在列表中找到他
3. 移动他直到他的分数在正确的位置

但这会非常慢。可能有数十万玩家，玩家可以将自己的分数重置为 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

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

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

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

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

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