2010-12-22 24 views
13

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.

+0

possibile ripetizione della http://stackoverflow.com/questions/2140787/select-random-k-elements-from-a-list-whose- elements-have-weights – user470379

+2

@ user470379 Questo è diverso in quanto i pesi sono 1, 2, ..., N. – marcog

+1

@ user470379, credo che il requisito per supportare l'inserimento e la cancellazione lo distingua. – jonderry

risposta

8

È possibile utilizzare un albero di ricerca binario aumentato per memorizzare gli elementi, insieme alla somma dei pesi in ogni sottostruttura. Questo ti consente di inserire ed eliminare elementi e pesi come preferisci. Sia il campionamento che gli aggiornamenti richiedono il tempo O (lg n) per operazione e l'utilizzo dello spazio è O (n).

Il campionamento viene eseguito generando un numero intero casuale in [1, S], dove S è la somma di tutti i pesi (S è memorizzata nella radice dell'albero) e esegue la ricerca binaria utilizzando le somme ponderate memorizzate per ogni sottostruttura.

+1

+1: qualcosa di molto simile: http://stackoverflow.com/questions/3120035/indexing-count-of-buckets/3120179#3120179. Spero che la spiegazione qui chiarirà meglio la risposta qui. –

2

Una soluzione che viene eseguita in O (n) dovrebbe iniziare selezionando il primo elemento. Quindi, per ciascun elemento successivo, tieni l'elemento che hai o lo sostituisci con quello successivo. Sia w la somma di tutti i pesi per gli elementi considerati finora. Quindi mantieni il vecchio con probabilità w/(w + x) e scegli il nuovo con p = x/(w + x), dove x è il peso dell'elemento successivo.

+0

Sì, è quello che faccio adesso. Sento che dovrebbe esserci un'ottimizzazione intelligente per evitare di guardare a tutti gli elementi ogni volta. 100.000 è molto. –

+0

Ad esempio, è possibile mantenere ordinato l'elenco, quindi in fase di ricerca è possibile saltare più elementi in determinati casi. O stabilire un sistema di partizioni o qualcosa. –

-3

Se si conosce la somma dei pesi (nel tuo caso, 9) E si utilizza una struttura di dati ad accesso casuale (lista comporta O (n) tempo di accesso), allora si può fare in fretta:

1) selezionare un elemento casuale (O (1)). Poiché esiste la possibilità di selezionare un elemento in questo passaggio, ci consente di utilizzare l'incremento num_elems* per il passaggio 2), accelerando così l'algoritmo.

2) calcolare la sua probabilità atteso: num_elems * (weight/total_weight)

3) prendere un numero casuale nell'intervallo 0..1, e se è minore di probabilità attesa, si ha l'uscita. In caso contrario, ripetere dal punto 1)

+0

@downvoter: puoi almeno spiegarti? – ruslik

+0

Non sono il downvoter, ma il problema è che il prodotto nel passaggio 2) può essere maggiore di 1. Questo overflow significa che gli elementi di peso elevato non verranno restituiti tutte le volte che dovrebbero. – antonakos

+0

@antonakos: sì, ma questo può essere risolto. La buona parte di questo algoritmo è che potrebbe essere più veloce di O (log (n)). – ruslik

3

Mi piace molto la soluzione di jonderry ma mi chiedo se questo problema abbia bisogno di una struttura complessa come l'albero di ricerca binario aumentato. E se mantenessimo due array, uno con i pesi di input, diciamo a = {1,1,2,5} e uno con i pesi cumulativi (un'idea molto simile alla soluzione di jonderry) che sarebbe b = {1,2,4 , 9}. Ora genera un numero casuale in [1 9] (per esempio x) e la ricerca binaria nell'array somma cumulativa. La posizione in cui b [i] < = x eb [i-1]> x è annotata e viene restituito un [i]. Quindi, se il numero casuale fosse 3, otterremmo i = 3, e sarebbe restituito un [3] = 2. Ciò garantisce la stessa complessità della soluzione ad albero aumentato con un'implementazione più semplice.

+0

Hai bisogno di BST perché la domanda richiede la possibilità di aggiungere e rimuovere elementi, oltre a campionarli. – jonderry

+0

Ah, non l'ho notato affatto - bella soluzione! – kyun

0

Questo è quello che ho fatto per risolverlo:

def rchoose(list1, weights): 
    ''' 
    list1 : list of elements you're picking from. 
    weights : list of weights. Has to be in the same order as the 
       elements of list1. It can be given as the number of counts 
       or as a probability. 
    ''' 

    import numpy as np 

    # normalizing the weights list 
    w_sum = sum(weights) 
    weights_normalized = [] 
    for w in weights: 
     weights_normalized.append(w/w_sum) 

    # sorting the normalized weights and the desired list simultaneously 
    weights_normalized, list1 = zip(*sorted(zip(weights_normalized, list1))) 

    # bringing the sorted tuples back to being lists 
    weights_normalized = list(weights_normalized) 
    list1 = list(list1) 

    # finalizing the weight normalization 
    dummy = []; count = 0 
    for item in weights_normalized: 
     count += item 
     dummy.append(count) 
    weights_normalized = dummy 

    # testing which interval the uniform random number falls in 
    random_number = np.random.uniform(0, 1) 
    for idx, w in enumerate(weights_normalized[:-1]): 
     if random_number <= w: 
      return list1[idx] 

    return list1[-1] 
Problemi correlati