Ho una lista di 100.000 oggetti. Ad ogni elemento di elenco è associato un "peso" che è positivo int da 1 a N.Selezione casuale di un elemento da un elenco ponderato
Qual è il modo più efficace per selezionare un elemento casuale dall'elenco? Voglio il comportamento che la mia distribuzione di elementi scelti a caso è la stessa della distribuzione dei pesi nella lista.
Ad esempio, se ho una lista L = {1,1,2,5}, voglio che il quarto elemento sia selezionato in media 5/9esima volta.
Assumendo inserimenti ed eliminazioni sono comuni in questo elenco, quindi qualsiasi approccio che utilizzi "tabelle di area integrale" dovrebbe essere aggiornato spesso, sperando che esista una soluzione con O (1) runtime e O (1) memoria aggiuntiva richiesta.
possibile ripetizione della http://stackoverflow.com/questions/2140787/select-random-k-elements-from-a-list-whose- elements-have-weights – user470379
@ user470379 Questo è diverso in quanto i pesi sono 1, 2, ..., N. – marcog
@ user470379, credo che il requisito per supportare l'inserimento e la cancellazione lo distingua. – jonderry