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

У меня есть класс 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}')

Сначала я подумал о том, чтобы иметь список всех игроков, и всякий раз, когда что-либо случается с игроком:

  • Я проверяю, увеличился или уменьшился его счет.
  • найдите его в списке
  • переместите его, пока его счет не окажется в правильном месте.

Но это было бы очень медленно. Могут быть сотни тысяч игроков, а игрок может reset собственный счет до 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

Ответы

Ответ 1

Редиссы отсортированы с помощью этой точной ситуации (документация использует платы лидеров в качестве примера использования) http://redis.io/topics/data-types-intro#redis-sorted-sets

  • Ключевыми командами, которые вам нужны, являются ZADD (рейтинг игрока игрока) и ZRANK (получить рейтинг для конкретного игрока). Обе операции - это сложность O (log (N)).

Redis может использоваться как кэш рейтинга игрока. Когда ваше приложение запустится, заполните redis из данных SQL. При обновлении очков игроков в mysql также обновляется redis.

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

  • обновлять только redis из триггера DB; или
  • серийные обновления очков; или
  • позволяют временно получать данные из синхронизации и выполнять другое обновление кеша после задержки; или
  • позволяют временно получать данные из синхронизации и выполнять полную перестройку кеша с фиксированными интервалами.

Ответ 2

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

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

Разрабатывая в отсортированном списке, вы должны запросить db, чтобы получить его, но вы можете продолжать использовать его некоторое время. Возможно, вы сохраните 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, что является правильным.

Ответ 3

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

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

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