Bylo by dobré vědět, o jakém druhu dat mluvíme. Kolik uživatelů existuje? Kolik jich bude v průměru online? Jaký je poměr „viděných uživatelů“ ve srovnání se všemi uživateli (řídký vs. hustý)?
Úprava vašeho algoritmu Nevybírejte první, ale vyberte náhodný prvek ze sady online uživatelů. To by mělo zlepšit vyvážení a může pomoci s amortizovanou složitostí v závislosti na poměru těchto dvou sad!
Alternativní algoritmus (více strukturovaný; v nejhorším případě stále špatný; měl by být dobrý, pokud ho vidíte )
- Zůstaňte viděni jako vyvážený strom (vložení O(log n))
- Zůstaňte online jako vyrovnaný strom.
- Ačkoli nebylo vybráno dostatečné množství uživatelů:
- Vyhledejte první mezeru v viděno (např. [0,1,3,7] -> 2; O(log n) podle SO-linku)
- Vyhledat prvního uživatele>=hodnota mezery (O(log n))
- Pokud uživatel
- -> vybrat
- Jinak
- -> přidat zvolenou hodnotu mezery dočasně (pro tuto chvíli; model – rozhodnutí, jak často aktualizovat online ) vidět NEBO nějak omezit vyhledávání na> hodnotu zvolené mezery (O(log n))
V závislosti na datech by to mělo fungovat velmi dobře, pokud jsou data obrovská a viditelná je řídký!