Би било добре да знаем за какъв вид данни говорим. Колко потребители съществуват? Колко средно ще бъдат онлайн? Как е съотношението на „видени потребители“ в сравнение с всички потребители (рядко спрямо плътно)?
Промяна на вашия алгоритъм Не пускайте първия, а изберете произволен елемент от набора онлайн потребители. Това трябва да подобри балансирането и може да помогне за амортизираната сложност в зависимост от съотношението на тези два набора!
Алтернативен алгоритъм (по-структуриран; все още лош в най-лошия случай; трябва да е добър, ако се вижда )
- Дръжте виждани като балансирано дърво (O(log n) вмъкване)
- Дръжте онлайн като балансирано дърво.
- Докато не са избрани достатъчно потребители:
- Търсете първата празнина в виждано (напр. [0,1,3,7] -> 2; O(log n) според SO-връзка)
- Търсене на първия потребител>=gap-value (O(log n))
- Ако потребител
- -> изберете
- Иначе
- -> добавете избрана-гап-стойност временно (за този момент; модел-решение колко често да се актуализира онлайн ) за виждан ИЛИ ограничете търсенето по някакъв начин до> избрана-пропусква стойност (O(log n))
В зависимост от данните, това трябва да работи много добре, ако данните са огромни и виждани е рядък!
