我有一个具有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}')
首先，我想到了一个所有球员的列表，每当一个球员发生任何事情:
- 我检查他的分数是增加还是减少
- 在列表中找到他
- 移动他直到他的分数在正确的位置
但是这会非常慢。这里可能有成千上万的玩家，玩家可以将自己的分数重置为0，这意味着我必须移动堆栈中的所有人。甚至找到玩家也是O(n)。
我正在寻找的是一个高性能的解决方案。RAM的使用不是很重要，尽管应该使用常识。我怎样才能改进这个系统，让它更快呢?
更新信息:我将玩家的数据存储到MySQL数据库与SQLAlchemy每次他离开gameserver，我加载它每次他加入服务器。这些是通过'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
Redis排序集帮助解决这个确切的情况(文档使用排行榜作为示例用法)http://redis.io/topics/data-types-intro#redis-sorted-sets
- 你关心的关键命令是ZADD(更新球员排名)和ZRANK(获得特定球员的排名)。两种操作的复杂度都是O(log(N))。
Redis可以用作玩家排名的缓存。当应用程序启动时，从SQL数据填充redis。当在mysql中更新玩家分数时，也要更新redis。
如果你有多个服务器进程/线程，它们可以同时触发玩家得分更新，那么你也应该考虑mysql/redis更新竞争条件，例如:
- 只从DB触发器更新redis;或
- 序列化玩家分数更新;或
- 让数据暂时不同步，并在延迟后进行另一次缓存更新;或
- 让数据暂时不同步，并以固定的间隔进行完整的缓存重建
您遇到的问题是，您希望对数据库进行实时更新，这需要每次进行db查询。如果你在内存中保留一个分数列表，并以更合理的频率更新它(游戏邦注:比如每小时一次，或者甚至每分钟一次，如果你的玩家真的关心自己的排名)，那么玩家仍然会体验到实时进度，而不是分数排名，他们无法真正分辨出更新中是否存在短暂的延迟。
使用内存中的分数排序列表，你可以立即获得玩家的排名(这里的"立即"指的是在内存中查找O(lg n)次)，这是以内存缓存为代价的，当然，当你想要更新缓存时也需要时间。与每次有人想要查看他们的排名时查询100k条记录相比，这是一个更好的选择。
详细说明排序列表，您必须查询数据库才能获得它，但您可以继续使用它一段时间。也许您存储last_update，并且仅在此列表"太旧"时才重新查询数据库。所以你可以快速更新，而不是一直更新，而只是让你感觉像是实时的。
为了几乎立即找到某人的排名，您使用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级，这是正确的。
可以使用SQLAlchemy的sort_by函数提取这类信息。如果执行如下查询:
leaderboard = session.query(Player).order_by(Player.score).all()
你将有球员的列表排序他们的分数。请记住，每次这样做时，您都会对数据库进行I/O操作，这可能会相当慢，而不是保存数据python变量。