ConcurrentSkipListMap tri: Peut-il être fait par compareTo de la valeur?

Question

Dans un jeu, je suis en train de tenir une liste des utilisateurs et avoir triés par, pour que je puisse interroger la liste à tout moment et retour donné (par exemple) les utilisateurs haut de dix par score. Cette liste doit être thread-safe. J'enVision en utilisant la chaîne de USERNAME en tant que clé et la valeur serait un objet utilisateur qui implémente Comparable et possède des propriétés telles que displayName et le score. serait donc l'objet utilisateur une méthode compareTo qui compare l'attribut de score pour déterminer sa position.

Je cherche à utiliser un ConcurrentSkipListMap pour cela, mais comme je peux le dire, la carte (par opposition à l'ensemble) utilise la clé trier. Je voudrais avoir la liste triée par la propriété score de l'objet utilisateur, mais toujours utiliser une carte parce que je dois être en mesure d'accès à tout utilisateur donné et modifier leur attribut score d'un fil.

Il ne semble pas que l'utilisation de mon propre pour la clé Comparator résoudrait mon problème, car je doute que j'aurais accès à la valeur associée à titre de comparaison. Je pourrais utiliser un ConcurrentSkipListSet mais l'accès à la liste pour modifier un score de chaque utilisateur serait (j'imagine) une opération coûteuse (en raison de la nécessité de itérer à chaque fois).

que quelqu'un soit en mesure de proposer comment y parvenir?

Answer 1

Non, je ne pense pas que vous pouvez. Le comparateur utilisé pour la commande est le même que celui utilisé pour l'indexation. Vous aurez probablement à maintenir 2 collections. Un pour garder l'ordre des scores de l'utilisateur par le nom pour faire référence aux utilisateurs.

Answer 2

get(key) dépend du comparateur (pour être en mesure de localiser la clé). Vous proposez un comparateur qui dépendrait de get(key) (pour accéder à la valeur mappée d'une clé basée sur un que pour comparer). Que nécessairement conduit à une récursion infinie et débordement de la pile (sur le côté lumineux, vous envoyez des messages sur le site Web droit !!)

Answer 3

Michael est juste, vous ne pouvez pas avoir votre gâteau et le manger aussi;)

Je pense que vous avez 3 choix:

1. Utiliser une carte afin que les mises à jour sur le score d'un utilisateur sont rapides, et vous payez le prix lors du tri pour trouver les meilleurs scores.
2. Utilisez un SortedSet qui trie par score que trouver les meilleurs scores est rapide, mais vous devez payer le prix lors de la mise à jour des scores de l'utilisateur
3. Maintenir deux structures de données, de sorte que vous pouvez avoir le meilleur de 1 et 2. Par exemple, vous avez vos données réelles dans un ensemble triée par le score, mais aussi de maintenir un mappage de nom d'utilisateur à l'index dans le jeu ou similaire . De cette façon, vous avez toujours les scores triés, et mettre à jour le score d'un utilisateur est juste une recherche, et non une recherche. Le prix que vous payez pour cela est maintenant, vous êtes maintenant des informations en double en deux endroits, et surtout compte tenu de l'accès simultané, il peut être difficile d'assurer les deux lieux sont toujours mis à jour synch.

Je ne formulions des hypothèses sur ce qui est plus rapide entre 1 et 2. Je les essayer à la fois avec votre utilisation prévue et la mesure de voir ce qui est le pire.

Si vous êtes uniquement intéressé dans le top n scores, puis il y a la possibilité de simplement maintenir cette liste séparément. Alors que votre carte de nom d'utilisateur pour marquer pour tout le monde, mais aussi de maintenir un petit ensemble des scores supérieurs (et leurs utilisateurs). Chaque fois que vous ajoutez / mise à jour le score de quelqu'un, il suffit de cocher le score contre la liste de pointage de haut, et si elle est plus grand que le plus petit là, il suffit d'ajouter et de buter l'inférieur. Ceci est similaire à la suggestion 3 ci-dessus, mais il est moins frais généraux et peut-être plus facile à entretenir.