Il serait bon de savoir de quel type de données nous parlons. Combien d'utilisateurs existent ? Combien seront en ligne en moyenne ? Quel est le ratio "d'utilisateurs vus" par rapport à tous les utilisateurs (épars ou dense) ?
Modification de votre algorithme Ne sautez pas le premier mais choisissez un élément aléatoire parmi l'ensemble des utilisateurs en ligne. Cela devrait améliorer l'équilibrage et peut aider à amortir la complexité en fonction du rapport de ces deux ensembles !
Algorithme alternatif (plus structuré ; toujours mauvais dans le pire des cas ; devrait être bon s'il est vu clairsemé )
- Gardez vu comme un arbre équilibré (insertion O(log n))
- Gardez en ligne comme un arbre équilibré.
- Bien qu'il n'y ait pas assez d'utilisateurs sélectionnés :
- Rechercher le premier écart dans vu (e.g. [0,1,3,7] -> 2; O(log n) selon SO-link)
- Rechercher le premier utilisateur >=gap-value (O(log n))
- Si l'utilisateur
- -> choisir
- Sinon
- -> ajouter la valeur d'écart choisie temporairement (pour le moment ; modèle-décision à quelle fréquence mettre à jour en ligne ) à vu OU limiter la recherche d'une manière ou d'une autre à> valeur d'écart choisie (O(log n))
Selon les données, cela devrait très bien fonctionner si les données sont volumineuses et visibles est rare !
