Sarebbe bene sapere di che tipo di dati stiamo parlando. Quanti utenti esistono? Quanti saranno in media online? Com'è il rapporto tra "utenti visti" rispetto a tutti gli utenti (sparsi e densi)?
Modifica del tuo algoritmo Non visualizzare il primo, ma scegli un elemento casuale dall'insieme degli utenti online. Ciò dovrebbe migliorare il bilanciamento e può aiutare con la complessità ammortizzata a seconda del rapporto tra questi due insiemi!
Algoritmo alternativo (più strutturato; nel peggiore dei casi ancora negativo; dovrebbe essere buono se visto) )
- Mantieni visto come albero bilanciato (inserimento O(log n))
- Mantieni online come un albero equilibrato.
- Anche se non sono stati scelti abbastanza utenti:
- Cerca il primo spazio vuoto in visto (es. [0,1,3,7] -> 2; O(log n) secondo SO-link)
- Cerca il primo utente>=gap-value (O(log n))
- Se l'utente
- -> scegli
- Altro
- -> aggiungi il valore del gap scelto temporaneamente (per questo momento; modello-decisione con quale frequenza aggiornare online ) a visto OPPURE limitare la ricerca in qualche modo a> valore-gap-scelto (O(log n))
A seconda dei dati, questo dovrebbe funzionare molto bene se i dati sono enormi e visti è scarso!
