ConcurrentSkipListMap clasificar: ¿Se puede hacer por compareTo del valor?

Question

En un juego, estoy tratando de mantener una lista de usuarios y tenerlo ordenadas según la puntuación, por lo que pude consultar la lista en cualquier momento dado y de retorno (por ejemplo) los usuarios diez por puntuación. Esta lista debe ser seguro para subprocesos. Me imaginan que la cadena usuario como clave y el valor sería un objeto de usuario que implementa Comparable y tiene propiedades tales como idioma y la puntuación. Por lo tanto, el objeto de usuario tendría un método compareTo que compararía el atributo de puntuación para determinar su posición.

Estoy buscando en el uso de un ConcurrentSkipListMap para esto, pero lo mejor que se puede decir, el mapa (en contraposición al Set) utiliza la clave para una especie. Me gustaría tener la lista ordenada por puntuación de la propiedad del objeto de usuario, pero todavía utilizar un mapa porque tengo que ser capaz de acceder a un usuario concreto y modificar su atributo de puntuación de un hilo.

No parece que el uso de mi propia Comparador de la clave sería resolver mi problema, ya que dudo que tendría acceso al valor asociado para la comparación. Me vendría bien un ConcurrentSkipListSet pero el acceso a la lista para modificar la puntuación de un usuario individual sería (me imagino) una operación costosa (debido a la necesidad de repetir cada vez).

¿Hay alguien que sea capaz de sugerir cómo lograr esto?

Answer 1

No, no creo que pueda. El comparador utilizado para el pedido es el mismo que se utiliza para la indexación. Usted probablemente tendrá que mantener 2 colecciones. Uno de mantener el orden de las calificaciones de los usuarios para referirse a los usuarios por su nombre.

Answer 2

get(key) depende del comparador (a ser capaz de localizar la clave). Usted propone un comparador que dependería de get(key) (para acceder al valor de una clave asignada una comparar basa en eso). Que necesariamente conduce a la repetición infinita y desbordamiento de pila (por el lado bueno, que vaya a publicar en el sitio web de la derecha !!)

Answer 3

Michael que es correcto, no se puede tener su pastel y comérselo también;)

Creo que tienes 3 opciones:

1. Usar un mapa para que cambios a la puntuación de un usuario son rápidos, y usted paga el precio al clasificar para encontrar las puntuaciones más altas.
2. Utilice un tipo que SortedSet por puntuación de modo que la búsqueda de las puntuaciones más altas es rápido, pero hay que pagar el precio de la hora de actualizar las calificaciones de usuario
3. Mantener dos estructuras de datos, por lo que puede tener lo mejor de 1 y 2. Por ejemplo, usted tiene sus datos reales en un conjunto ordenado por puntuación, pero también mantener una asignación de nombre de usuario para indexar en el set o similares . De esta manera siempre tienen los puntajes ordenados, y actualizar la puntuación de un usuario es sólo una búsqueda, no una búsqueda. El precio que paga por esto es que ahora está manteniendo cierta información duplicada en dos lugares, y sobre todo teniendo en cuenta el acceso concurrente, puede ser difícil asegurar ambos lugares están siempre actualizados en sincronía.

No sería hacer suposiciones acerca de lo que es más rápida entre 1 y 2. les trataría tanto con su uso previsto y medir para ver qué es lo peor.

Si está realmente interesado sólo en la parte superior puntuaciones en n, entonces existe la posibilidad de simplemente mantener esa lista por separado. Así que tener su mapa de nombre de usuario para anotar para todo el mundo, sino también mantener un pequeño conjunto de las puntuaciones más altas (y sus usuarios). Cada vez que se agrega / puntuación de actualización de alguien, simplemente marque el marcador en contra de la lista de puntuación más alta, y si es más grande que el más pequeño allí, sólo tiene que añadir y polvo, bajar el inferior. Esto es similar a la sugerencia 3 anterior, pero es menos sobrecarga y quizás más fácil de mantener.