ConcurrentSkipListMap Sortierung: Kann es durch den compareTo Wert getan werden?

Question

In einem Spiel, ich versuche, eine Liste von Benutzern zu halten und haben es nach Punkten sortiert, so dass ich die Liste zu einem bestimmten Zeitpunkt und Rückkehr (zum Beispiel) abfragen könnte den Top Ten der Benutzer nach Punkten. Diese Liste soll Thread-sicher sein. Ich stelle mir vor mit dem Username String als Schlüssel und der Wert wäre ein Benutzerobjekt sein, das Vergleichbare implementiert und verfügt über Eigenschaften wie display und Punktzahl. Das User-Objekt müßte daher eine compareTo Methode, die die Partitur Attribut vergleichen würde seine Position zu bestimmen.

Ich suche eine ConcurrentSkipListMap für diesen bei Verwendung, aber so gut ich kann sagen, die Karte (im Gegensatz zu dem Set Gegensatz) verwendet den Schlüssel zu sortieren. Ich mag die Liste durch die Partitur Eigenschaft des Benutzerobjekts sortiert haben, aber immer noch eine Karte verwenden, weil ich jeder beliebigen Benutzer in der Lage Zugriff sein muß und ihre Gäste aus einem Thread-Attribut ändern.

Es scheint nicht, dass mein eigenen Komparator für den Schlüssel würde mein Problem lösen, wie ich bezweifle, dass ich Zugriff auf den zugehörigen Wert für den Vergleich haben würde. Ich könnte eine ConcurrentSkipListSet verwenden, aber die Liste den Zugriff auf einen einzelnen Benutzer-Score zu ändern wäre (ich könnte mir vorstellen) eine teure Operation (aufgrund der Notwendigkeit, jedes Mal zu wiederholen).

Würde jemand in der Lage sein, empfehlen, wie dies zu erreichen?

Answer 1

Nein, ich glaube nicht, Sie können. Der Komparator jeweilige Ausführung ist das gleiche für die Indizierung verwendet. Sie werden wahrscheinlich zwei Sammlungen zu halten haben. Ein für die Bestellung von Benutzer-Noten zu halten, die für nach dem Namen der Nutzer betreffen.

Answer 2

get(key) hängt von dem Komparator (in der Lage sein den Schlüssel zu finden). Sie schlagen vor, einen Komparator, der auf get(key) (für den Zugriff auf den abgebildeten Wert eines Schlüssels ein vergleichen basiert auf dem) abhängen. Dass notwendigerweise führt zu unendlicher Rekursion und Stack-Überlauf (auf der hellen Seite, sind Sie auf der richtigen Website veröffentlichen !!)

Answer 3

Michael ist richtig, Sie können den Kuchen nicht essen und ihn auch;)

Ich glaube, Sie haben drei Möglichkeiten:

1. Verwenden Sie eine Karte, so dass Aktualisierungen einer Punktzahl des Benutzers sind schnell, und Sie zahlen den Preis beim Sortieren die höchste Punktzahl zu finden.
2. Verwenden Sie ein SortedSet dass Art von Partitur, so dass die höchste Punktzahl zu finden ist schnell, aber Sie müssen den Preis zahlen, wenn der Benutzer Partituren Aktualisierung
3. Pflegen zwei Datenstrukturen, so dass Sie das Beste aus 1 und 2 beispielsweise haben, können Sie Ihre realen Daten in eine Reihe nach Punkten sortiert, dann aber auch eine Zuordnung von Benutzernamen Index in die Menge oder ähnliches halten . So können Sie immer die sortierten Noten haben, und ein Benutzer Punktzahl Aktualisierung ist nur eine Lookup, nicht eine Suche. Der Preis, den Sie dafür bezahlen ist jetzt Sie einige doppelten Informationen an zwei Stellen pflegen und vor allem gleichzeitigen Zugriff bedenken, kann es schwierig sein, beide Orte gewährleistet werden immer synchron aktualisiert.

Ich würde keine Annahmen darüber, welche schneller ist zwischen 1 und 2. Ich würde versuchen, sie beide mit Ihrer erwarteten Nutzung und messen, um zu sehen, was schlimmsten ist.

Wenn Sie wirklich nur in der Top-n-Noten interessiert sind, dann gibt es die Möglichkeit, nur separat diese Liste zu halten. So haben Sie Ihre Karte von Benutzername für alle zu erzielen, sondern auch eine kleine Gruppe des Top-Scores (und deren Nutzer) halten. Jedes Mal, wenn Sie / update jemandes Partitur hinzufügen, überprüfen Sie die Punktzahl gegen die Top-Score-Liste, und wenn es größer als der kleinste dort, fügen Sie ihn einfach und stoßen die untere ab. Dies ist ähnlich Vorschlag 3 oben, ist aber weniger Overhead und vielleicht leichter zu pflegen.