Как отслеживать рейтинги игроков?

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).

Что я ищу - это высокопроизводительное решение. Использование ОЗУ не так важно, хотя здравый смысл следует использовать. Как я могу улучшить систему намного быстрее?

Информация обновлена: Я храню данные игрока в базе данных MySQL с помощью SQLAlchemy каждый раз, когда он покидает игровой сервер, и я загружаю его каждый раз, когда он присоединяется к серверу. Они обрабатываются через '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 может использоваться как кэш-игра игрока. Когда ваше приложение запустится, заполните redis из данных SQL. При обновлении очков игроков в mysql также обновляется redis.

Если у вас есть несколько серверных процессов/потоков и они могут вызвать обновления счет игрока одновременно, то вы должны также учесть MySQL/Redis состояния гонки обновления, например:

• только обновление Redis из триггера БД; или
• серию обновления очков; или
• позволяют временно получать данные из синхронизации и выполнять другое обновление кеша после задержки; или
• позволяют получить данные временно не синхронизированы и не полный кэш восстановления через определенные промежутки времени

Answer 2

Проблема у вас есть то, что вы хотите обновления в режиме реального времени с базой данных, который требует запроса db каждый раз. Если вместо этого вы сохраните список баллов в памяти и обновите его на более разумной частоте (скажем, один раз в час или даже один раз в минуту, если ваши игроки действительно заинтересованы в их рейтинге), то игроки все равно будут испытывать реальные ошибки, времени и ранга баллов, и они не могут сказать, есть ли короткое отставание в обновлениях.

С отсортированным списком баллов в памяти вы можете мгновенно получить ранг игрока (где мгновенно, я имею в виду O (lg n) поиск в памяти) за счет кэширования памяти и, конечно, время для обновления кеша, когда захотите. По сравнению с db-запросом в 100 тыс. Записей каждый раз, когда кто-то хочет взглянуть на их ранг, это намного лучший вариант.

Разрабатывая сортированный список, вы должны запросить его, чтобы получить его, но вы можете продолжать использовать его некоторое время. Возможно, вы сохраните last_update и повторно запросите db только в том случае, если этот список «слишком старый». Таким образом, вы быстро обновляетесь, не пытаясь обновлять все время, а скорее достаточно, чтобы чувствовать себя в режиме реального времени.

Чтобы мгновенно найти чей-то рейтинг, вы используете модуль 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 3

Эту информацию можно потянуть с помощью функции sort_by SQLAlchemy. Если вы сделаете такой же запрос, как:

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

У вас будет список игроков, отсортированный по их оценке. Имейте в виду, что каждый раз, когда вы это делаете, вы выполняете ввод-вывод с базой данных, которая может быть довольно медленной, а не сохранять переменные python данных.