Det ville være godt at vide, hvilken slags data vi taler om. Hvor mange brugere findes der? Hvor mange vil i gennemsnit være online? Hvordan er forholdet mellem "sete brugere" sammenlignet med alle brugere (sparsomme vs. tætte)?
Ændring af din algoritme Pop ikke den første, men vælg et tilfældigt element fra sættet af onlinebrugere. Dette burde forbedre balanceringen og kan hjælpe med amortiseret kompleksitet afhængigt af forholdet mellem disse to sæt!
Alternativ algoritme (mere struktureret; stadig dårligt i værste fald; burde være god, hvis sees sparsomt )
- Hold dig set som et balanceret træ (O(log n) indsættelse)
- Hold dig online som et balanceret træ.
- Selv om der ikke er valgt nok brugere:
- Søg efter første hul i set (f.eks. [0,1,3,7] -> 2; O(log n) ifølge SO-link)
- Søg efter første bruger>=gap-værdi (O(log n))
- Hvis bruger
- -> vælg
- Andet
- -> tilføj valgt-gap-værdi midlertidigt (i dette øjeblik; modelbeslutning, hvor ofte der skal opdateres online ) til set ELLER begrænse søgning på en eller anden måde til> valgt-gap-værdi (O(log n))
Afhængigt af dataene burde dette fungere meget godt, hvis data er enorme og set er sparsom!