如何跟踪球员的排名？

Question

我有Player一个score属性类:

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 sort sets帮助解决了这个问题(文档使用排行榜作为示例用法)http://redis.io/topics/data-types-intro#redis-sorted-sets

• 您关心的关键命令是ZADD(更新玩家等级)和ZRANK(获得特定玩家的等级).两个操作都是O(log(N))复杂度.

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

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

• 仅从DB触发器更新redis; 要么
• 序列化球员得分更新; 要么
• 让数据暂时不同步,并在延迟后再次进行缓存更新; 要么
• 让数据暂时不同步,并以固定的时间间隔执行完整的缓存重建