ConcurrentSkipListMap ordinamento: Può essere fatto dal compareTo del valore?

Question

In una partita, sto cercando di mantenere un elenco di utenti e lo hanno ordinati secondo il punteggio, in modo da poter interrogare l'elenco in un dato momento e il ritorno (per esempio) gli utenti top ten secondo il punteggio. Questa lista dovrebbe essere thread-safe. Mi immagino utilizzando la stringa userName come una chiave e il valore sarebbe un oggetto d'uso, che implementa comparabili e ha proprietà quali displayName e il punteggio. L'oggetto utente avrebbe quindi un metodo compareTo che confronta l'attributo punteggio per determinarne la posizione.

Sto cercando di utilizzare un ConcurrentSkipListMap per questo, ma come meglio posso dire, la mappa (in contrapposizione al Set) utilizza la chiave di ordinamento. Mi piacerebbe avere l'elenco ordinato per la proprietà punteggio dell'oggetto d'uso, ma comunque possibile utilizzare una mappa perché ho bisogno di essere in grado di accedere qualsiasi utente e modificare il loro attributo punteggio da un filo.

E non sembra che usando il mio comparatore per la chiave avrebbe risolto il mio problema, come dubito che avrei dovuto accedere al valore associato per il confronto. Potrei usare un ConcurrentSkipListSet ma l'accesso alla lista per modificare il punteggio di un singolo utente sarebbe (mi immagino) un'operazione costosa (a causa della necessità di scorrere ogni volta).

Qualcuno dovrebbe essere in grado di suggerire come eseguire questa operazione?

Answer 1

No, non credo che si può. Il comparatore utilizzato per ordinare è lo stesso utilizzato per l'indicizzazione. Probabilmente si dovrà mantenere 2 collezioni. Uno per mantenere l'ordine dei punteggi degli utenti per il riferimento agli utenti in base al nome.

Answer 2

get(key) dipende dal comparatore (per poter individuare la chiave). Lei propone un comparatore che dipenderebbe get(key) (per accedere al valore mappato di una chiave di un CONFRONTO sulla base di questo). Che necessariamente porta alla ricorsione infinita e overflow dello stack (il lato positivo, stai scrivendo sul sito giusto !!)

Answer 3

Michael è giusto, non si può avere la botte piena e la moglie ubriaca;)

Credo che bisogna 3 scelte:

1. Utilizza una mappa in modo che gli aggiornamenti di punteggio di un utente sono veloci, e si paga il prezzo durante l'ordinamento per trovare i punteggi più alti.
2. Usa un SortedSet che sorta di punteggio in modo che trovare i punteggi più alti è veloce, ma si deve pagare il prezzo quando si aggiornano i punteggi degli utenti
3. Mantenere due strutture di dati, in modo da poter avere il meglio di 1 e 2. Ad esempio, avete i vostri dati reali in un insieme ordinati secondo il punteggio, ma poi anche mantenere una mappatura di nome utente per indicizzare il set o simili . In questo modo si ha sempre la punteggi ordinati, e l'aggiornamento il punteggio di un utente è solo una ricerca, non una ricerca. Il prezzo da pagare per questo ora si gestiscono alcune informazioni duplicate in due luoghi, e soprattutto se si considera l'accesso concorrente, può essere difficile assicurare entrambi i luoghi sono sempre aggiornati in sintonia.

Non vorrei fare ipotesi su che è più veloce tra 1 e 2. vorrei provarli entrambi fuori con l'uso previsto e misurare per vedere ciò che è peggio.

Se siete veramente interessati solo nella top n colonne sonore, poi c'è la possibilità di mantenere solo quella lista separatamente. Quindi, avere il vostro mappa di nome utente a segnare per tutti, ma anche mantenere un piccolo insieme dei migliori punteggi (ed i loro utenti). Ogni volta che si aggiunge / punteggio di aggiornamento di qualcuno, basta controllare il punteggio con l'elenco punteggio più alto, e se è più grande di quello più piccolo lì, basta inserirlo e far fuori quello inferiore. Questo è simile al suggerimento 3 di cui sopra, ma è meno overhead e forse più facile da mantenere.