Migliore struttura dati per l'elenco ordinato degli utenti connessi

-3

Ho tre attributi per un utente: connectionId (ad es. "sd4-h4sdg-u4j-a2rr3"), userName e placeInLine .

Non riesco a pensare a una singola struttura dati che gestirà il mio scenario di consentire solo a un singolo utente di lavorare su una determinata risorsa di pagina Web e di far avanzare la linea di persone mentre ogni utente attivo lascia la propria connessione. Sto usando C # / SignalR con jQuery.

Quando un utente (Adam) colpisce la pagina, se questa struttura dati proposta è vuota, arriva a interagire con la pagina. Il prossimo utente che arriva (Bob) mentre Adam sta lavorando viene messo in linea. Quindi salviamo il suo userName, connectionId e mettiamo in linea come 1 . Carl arriva e viene messo in riga, ottenendo placeInLine=2 . David è 3 , ecc.

Ora, in un mondo perfetto, tutti aspetteranno pazientemente il proprio turno e verranno avvisati quando l'utente davanti a loro si disconnette, in modo che possa avere il proprio turno sulla pagina. In questo scenario, un Queue funzionerebbe. Tuttavia: se Carl lascia, non possiamo semplicemente rimuoverlo dal Queue poiché si trova nel mezzo [B, C, D] . Voglio che questo codice venga ridimensionato, quindi ricostruire una coda con ogni modifica non è un'opzione.

Se usassi Dictionary , potrei avere userName come chiave, con un valore di placeInLine . Ma in questo scenario, non posso ottenere il prossimo utente, poiché Get() avviene tramite Key. Se placeInLine int è la chiave, non riesco a rimuovere un utente in base al nome utente poiché Remove() viene eseguito anche con la chiave.

Sono ingenuo per presupporre che questo dovrebbe essere possibile con una singola struttura dati?

    
posta JacobIRR 18.01.2018 - 01:22
fonte

1 risposta

3

Ciò che scegli potrebbe dipendere dal particolare carico che anticipi.

Ma inizierei con un Queue semplice. Possibilmente esteso con un ingenuo O (n) complessità Remove(item) . In alternativa, utilizza Dictionary o Map per indicizzare gli utenti "rimossi". Man mano che pop() elementi escono da Queue , ignora gli utenti "rimossi" e re pop() .

Potresti potenzialmente eseguire ulteriori micro-ottimizzazioni, ma sono già scettico sul fatto che la complessità dell'aggiunta di un indice sia un'ottimizzazione necessaria. Probabilmente non mi preoccuperei se non avessi una strong evidenza che il n nel mio metodo O (n) Remove() sarà significativo.

    
risposta data 18.01.2018 - 04:06
fonte

Leggi altre domande sui tag