python - ¿Cómo hacer un seguimiento de las clasificaciones de los jugadores?

algorithm python-3.x

Question

Tengo una clase de Player con un atributo de score :

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

Este puntaje aumenta / disminuye a medida que el jugador tiene éxito / no logra los objetivos. Ahora necesito decirle al jugador su rango de la cantidad total de jugadores con algo así como

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

Primero pensé en tener una lista de todos los jugadores, y siempre que algo le ocurra a un jugador:

1. Verifico si su puntaje aumentó o disminuyó
2. encontrarlo en la lista
3. moverlo hasta que su puntaje esté en el lugar correcto

Pero esto sería extremadamente lento. Puede haber cientos de miles de jugadores, y un jugador puede restablecer su propia puntuación a 0 lo que significaría que tendría que mover a todos después de él en la pila. Incluso encontrar al jugador sería O (n).

Lo que estoy buscando es una solución de alto rendimiento. El uso de RAM no es tan importante, aunque se debe usar el sentido común. ¿Cómo podría mejorar el sistema para que sea mucho más rápido?

Información actualizada: estoy almacenando los datos de un jugador en una base de datos MySQL con SQLAlchemy cada vez que deja el servidor de juegos, y lo cargo cada vez que se une al servidor. Estos se manejan a través ''player_join'' y ''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()

Además, el puntaje del jugador se actualiza al ''player_kill'' evento ''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

El problema que tiene es que quiere actualizaciones en tiempo real contra una base de datos, lo que requiere una consulta db cada vez. Si en cambio mantiene una lista de puntajes en la memoria y la actualiza a una frecuencia más razonable (por ejemplo, una vez por hora, o incluso una vez por minuto, si sus jugadores están realmente preocupados por su rango), entonces los jugadores todavía experimentarán real- el progreso del tiempo frente a un rango de puntaje, y realmente no pueden decir si hay un retraso corto en las actualizaciones.

Con una lista ordenada de puntajes en la memoria, puede obtener instantáneamente el rango del jugador (donde al instante, me refiero a la búsqueda O (lg n) en la memoria) a costa de la memoria en la memoria caché, y por supuesto, el tiempo para actualizar la memoria caché cuando quieras. En comparación con una consulta db de 100k registros cada vez que alguien quiere echar un vistazo a su rango, esta es una opción mucho mejor.

Al elaborar en la lista ordenada, debe consultar el archivo db para obtenerla, pero puede seguir utilizándola durante un tiempo. Tal vez almacene el last_update y vuelva a consultar el db solo si esta lista es "muy antigua". Así que actualizas rápidamente al no intentar actualizar todo el tiempo, sino lo suficiente como para sentirme en tiempo real.

Para encontrar el rango de alguien casi instantáneamente, utiliza el módulo bisect, que admite la búsqueda binaria en una lista ordenada. Los puntajes se ordenan cuando los obtienes.

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)

Esto dice que un puntaje 7 es el rango 4, que es correcto.

Answer 2

Ese tipo de información se puede extraer utilizando la función sort_by de SQLAlchemy. Si realiza una consulta como:

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

Tendrás la lista de Jugadores ordenada por su puntuación. Tenga en cuenta que cada vez que hace esto, realiza una E / S con la base de datos, que puede ser bastante lenta en lugar de guardar las variables de python de datos.

Answer 3

Los conjuntos ordenados de Redis ayudan con esta situación exacta (la documentación usa tablas de clasificación como el uso del ejemplo) http://redis.io/topics/data-types-intro#redis-sorted-sets

• Los comandos clave que te importan son ZADD (actualizar rango del jugador) y ZRANK (obtener rango para un jugador específico). Ambas operaciones son de complejidad O (log (N)).

Redis se puede usar como un caché de clasificación de jugadores. Cuando se inicia la aplicación, rellene redis a partir de los datos SQL. Al actualizar los puntajes de los jugadores en mysql también se actualiza el redis.

Si tiene múltiples procesos / subprocesos de servidor y pueden activar actualizaciones de puntaje de jugador al mismo tiempo, también debe tener en cuenta la condición de actualización de actualización de mysql / redis, por ejemplo:

• solo actualiza redis desde un disparador DB; o
• actualizaciones de puntaje de jugador serializado; o
• deje que los datos se desincronicen temporalmente y realice otra actualización de caché después de un retraso; o
• deje que los datos se desincronicen temporalmente y realice una reconstrucción completa de la memoria caché a intervalos fijos