In modo efficiente la selezione di un insieme di elementi casuali da una lista collegata

Question

Dire di avere una lista di numeri di lunghezza N. N è molto grande e non so in anticipo il valore esatto di N.

Come posso fare in modo più efficiente di scrivere una funzione che ritorna k completamente numeri casuali dall'elenco?

Answer 1

C'è un molto bello ed efficiente algoritmo per questo utilizzando un metodo chiamato serbatoio di campionamento.

Vorrei iniziare dando il suo storia:

Knuth chiama questo Algoritmo R su p.144 della sua edizione del 1997 di Seminumerical Algoritmi (volume 2 di The Art of Computer Programming), e fornisce un po ' di codice per lì.Knuth attributi, l'algoritmo di Alan G.Waterman.Nonostante una lunga ricerca, non sono stato in grado di trovare Waterman documento originale, se esiste, quale può essere il motivo per cui è più spesso di vedere Knuth citato come fonte di questo algoritmo.

McLeod e Bellhouse, 1983 (1) fornire una più approfondita discussione di Knuth così come il primo pubblicato le prove (che io sappia) che l'algoritmo funziona.

Vitter 1985 (2) le recensioni Algoritmo di R e quindi presenta un ulteriore tre algoritmi che forniscono lo stesso risultato, ma con una torsione.Piuttosto che fare una scelta di includere o saltare ogni nuovo elemento, il suo algoritmo predetermina il numero di elementi in entrata per essere ignorato.Nel suo test (che, in verità, non ora) questo è diminuito il tempo di esecuzione drammaticamente, evitando la generazione di numeri casuali e al confronto su ogni numero del prossimo.

In pseudocodice l'algoritmo è:

Let R be the result array of size s
Let I be an input queue

> Fill the reservoir array
for j in the range [1,s]:
  R[j]=I.pop()

elements_seen=s
while I is not empty:
  elements_seen+=1
  j=random(1,elements_seen)       > This is inclusive
  if j<=s:
    R[j]=I.pop()
  else:
    I.pop()

Nota che ho appositamente scritto il codice per evitare di specificare la dimensione dell'input.Questo è uno dei cool proprietà di questo algoritmo:si può eseguire senza bisogno di conoscere la dimensione dell'input in anticipo e ancora si assicura che ogni elemento incontro ha una uguale probabilità di finire in R (che è, non c'è nessun bias).Inoltre, R contiene una fiera e un campione rappresentativo degli elementi l'algoritmo è considerata in ogni momento.Questo significa che è possibile utilizzare questo come un online algoritmo.

Perché fa questo lavoro?

McLeod e Bellhouse (1983) fornire una prova utilizzando la matematica di combinazioni.È abbastanza, ma sarebbe un po ' difficile ricostruire qui.Pertanto, ho generato una prova alternativa che è più facile da spiegare.

Si procede attraverso la prova per induzione.

Dire che si desidera generare un insieme di s elementi e che abbiamo già visto n>s elementi.

Supponiamo che il nostro attuale s gli elementi sono già stati scelti con probabilità s/n.

Dalla definizione di algoritmo, abbiamo scelto elemento n+1 con probabilità s/(n+1).

Ogni elemento già parte di un set di risultati è una probabilità 1/s di essere sostituito.

La probabilità che un elemento dall' n-visto il set di risultati è sostituito nel n+1-visto il set di risultati è quindi (1/s)*s/(n+1)=1/(n+1).Al contrario, la probabilità che un elemento non viene sostituito è 1-1/(n+1)=n/(n+1).

Così, il n+1-visto il risultato di un set contiene un elemento o una parte di n-visto il risultato di un set e non è stata sostituita---questa probabilità è (s/n)*n/(n+1)=s/(n+1)---o se l'elemento è stato scelto---con probabilità s/(n+1).

La definizione dell'algoritmo ci dice che il primo s gli elementi sono inclusi automaticamente come prima n=s i membri del set di risultati.Pertanto, il n-seen risultato set include ogni elemento con s/n (=1) probabilità che ci dà la necessaria base per l'induzione.

Riferimenti

1. McLeod, A.Ian, e David R.Bellhouse."Un comodo algoritmo per il disegno di un semplice campione casuale." Journal of the Royal Statistical Society.Serie C (Statistica Applicata) 32.2 (1983):182-184.(Link)

2. Vitter, Jeffrey S."Il campionamento casuale con un serbatoio". ACM Transactions on Software Matematici (TOM) 11.1 (1985):37-57.(Link)

Answer 2

Questo è chiamato un Serbatoio Di Campionamento problema.La soluzione più semplice è quello di assegnare un numero casuale per ogni elemento della lista, come potete vedere, quindi, mantenere la parte superiore (o inferiore) di k elementi, come ordinato dal numero casuale.

Answer 3

Vorrei suggerire:Prima di trovare il tuo k numeri casuali.Ordinare loro.Poi la traversata sia per la lista collegata e casuale di numeri di una volta.

Se in qualche modo non so la lunghezza della lista collegata (come?), poi si può prendere il primo k in un array, poi per il nodo r, generare un numero casuale nell'intervallo [0, r), e se è minore di k, sostituire il rth elemento dell'array.(Non del tutto convinto che non bias...)

Più che altro:"Se fossi in te, non sarei a partire da qui." Sei sicuro di lista collegata è giusto per il vostro problema?Non c'è una migliore struttura di dati, come un buon vecchio array list.

Answer 4

Se non si conosce la lunghezza della lista, allora si dovrà attraversare il completo per garantire casuale denti.Il metodo che ho utilizzato in questo caso è quello descritto da Tom Hawtin (54070).Durante l'attraversamento della lista di mantenere k elementi che formano la vostra selezione casuale a quel punto.(Inizialmente si aggiunge solo il primo k elementi che si incontrano.) Poi, con probabilità k/i, la sostituzione di un elemento casuale dalla selezione con l' iesimo elemento della lista (es.l'elemento che si trovi, in quel momento).

È facile mostrare che questo dà una selezione casuale.Dopo aver visto m elementi (m > k), abbiamo che il primo e il m elementi della lista sono parte di una selezione casuale con una probabilità k/m.Che questo inizialmente ha, è banale.Quindi per ogni elemento m+1, si è messo in proprio la selezione (sostituzione di un elemento casuale) con probabilità k/(m+1).Ora c'è bisogno di dimostrare che tutti gli altri elementi, inoltre, hanno probabilità k/(m+1) di essere selezionato.Abbiamo che la probabilità è k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (cioèla probabilità che un elemento nell'elenco volte la probabilità che esso è ancora lì).Con il calcolo si può semplicemente mostrare che questo è uguale a k/(m+1).

Answer 5

Bene, dovete sapere che N è in fase di runtime almeno, anche se questo comporta fare un extra pass la lista di contarli.Il più semplice algoritmo per farlo è quello di scegliere solo un numero casuale in N e rimuovere l'elemento ripetuto k volte.O, se è ammessa la restituzione ripetere i numeri, non rimuovere la voce.

A meno che non si dispone di un MOLTO grande N, e a severi requisiti di prestazioni, questo algoritmo viene eseguito con O(N*k) la complessità, che dovrebbe essere accettabile.

Edit:Nevermind, Tom Hawtin metodo è il modo migliore.Selezionare i numeri casuali prima, quindi scorrere l'elenco una volta.Stessa complessità teorica, penso, ma molto meglio previsto runtime.

Answer 6

Perché non si può solo fare qualcosa di simile

List GetKRandomFromList(List input, int k)
  List ret = new List();
  for(i=0;i<k;i++)
    ret.Add(input[Math.Rand(0,input.Length)]);
  return ret;

Sono sicuro che non intendi qualcosa che semplice, in modo che si può specificare ulteriormente?