Es wäre gut zu wissen, um welche Art von Daten es sich handelt. Wie viele Benutzer gibt es? Wie viele werden durchschnittlich online sein? Wie ist das Verhältnis von "gesehenen Benutzern" im Vergleich zu allen Benutzern (sparse vs. dense)?
Änderung Ihres Algorithmus Platzieren Sie nicht das erste, sondern wählen Sie ein zufälliges Element aus der Menge der Online-Benutzer. Dies sollte das Balancing verbessern und je nach Verhältnis dieser beiden Sätze zu amortisierter Komplexität beitragen!
Alternativer Algorithmus (strukturierter; immer noch schlechter Worst-Case; sollte gut sein, wenn er spärlich gesehen wird )
- Halten Sie sich gesehen als balancierter Baum (Einfügung von O(log n))
- Bleiben Sie online als ausgeglichener Baum.
- Während nicht genügend Benutzer ausgewählt wurden:
- Suche nach der ersten Lücke in gesehen (zB [0,1,3,7] -> 2; O(log n) nach SO-link)
- Suche nach erstem Benutzer>=Lückenwert (O(log n))
- Wenn Benutzer
- -> auswählen
- Sonst
- -> Gewählten Lückenwert vorübergehend hinzufügen (für diesen Moment; Modellentscheidung, wie oft online aktualisiert werden soll ) gesehen ODER begrenzen Sie die Suche irgendwie auf>gewählter-Lückenwert (O(log n))
Abhängig von den Daten sollte dies sehr gut funktionieren, wenn die Daten sehr groß sind und gesehen werden ist spärlich!
