Selezione efficiente di un insieme di elementi casuali da un elenco collegato

Supponiamo di avere un elenco collegato di numeri di lunghezza N N è molto grande e non conosco in anticipo il valore esatto di N

Come posso scrivere in modo più efficiente una funzione che restituirà k numeri completamente casuali dalla lista?

C’è un algoritmo molto carino ed efficiente per questo usando un metodo chiamato campionamento del serbatoio .

Lasciatemi iniziare dandoti la sua storia :

Knuth chiama questo Algorithm R a p. 144 della sua edizione 1997 di Seminumerical Algorithms (volume 2 di The Art of Computer Programming), e fornisce un codice per questo lì. Knuth attribuisce l’algoritmo ad Alan G. Waterman. Nonostante una lunga ricerca, non sono stato in grado di trovare il documento originale di Waterman, se esiste, il che potrebbe essere il motivo per cui vedrai la citazione di Knuth come fonte di questo algoritmo.

McLeod e Bellhouse, 1983 (1) forniscono una discussione più approfondita di Knuth e la prima prova pubblicata (di cui sono a conoscenza) che l’algoritmo funziona.

Vitter 1985 (2) recensisce Algorithm R e poi presenta altri tre algoritmi che forniscono lo stesso risultato, ma con una svolta. Piuttosto che fare una scelta per includere o saltare ogni elemento in entrata, il suo algoritmo predetermina il numero di elementi in arrivo da saltare. Nei suoi test (che, ovviamente, non sono aggiornati) questo ha ridotto drasticamente il tempo di esecuzione evitando la generazione di numeri casuali e confronti su ciascun numero in arrivo.

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 scritto in modo specifico il codice per evitare di specificare la dimensione dell'input. Questa è una delle fantastiche proprietà di questo algoritmo: puoi eseguirlo senza dover conoscere prima la dimensione dell'input e ti assicura comunque che ogni elemento che incontri ha una uguale probabilità di finire in R (cioè, non c'è bias). Inoltre, R contiene un campione equo e rappresentativo degli elementi che l'algoritmo ha considerato in ogni momento. Questo significa che puoi usare questo come un algoritmo online .

Perché funziona?

McLeod e Bellhouse (1983) forniscono una prova usando la matematica delle combinazioni. È carino, ma sarebbe un po 'difficile ricostruirlo qui. Pertanto, ho generato una prova alternativa che è più facile da spiegare.

Procediamo attraverso la prova per induzione.

Diciamo che vogliamo generare un insieme di elementi s e che abbiamo già visto gli elementi di n>s .

Supponiamo che i nostri attuali elementi s siano già stati scelti con probabilità s/n .

Con la definizione dell'algoritmo, scegliamo l'elemento n+1 con probabilità s/(n+1) .

Ogni elemento già parte del nostro set di risultati ha una probabilità 1/s di essere sostituito.

La probabilità che un elemento dal set di risultati n -se venga sostituita nel set di risultati al di sotto di n+1 è quindi (1/s)*s/(n+1)=1/(n+1) . Viceversa, la probabilità che un elemento non venga sostituito è 1-1/(n+1)=n/(n+1) .

Quindi, il set di risultati n+1 -seen contiene un elemento sia che fosse parte del set di risultati n -seen che non sia stato sostituito --- 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 i primi elementi s sono automaticamente inclusi come i primi n=s membri del set di risultati. Pertanto, il set di risultati n-seen include ogni elemento con s/n (= 1) probabilità dandoci il caso base necessario per l'induzione.

Riferimenti

  1. McLeod, A. Ian e David R. Bellhouse. "Un comodo algoritmo per disegnare un semplice campione casuale." Ufficiale della Royal Statistical Society. Serie C (statistiche applicate) 32.2 (1983): 182-184. ( Link )

  2. Vitter, Jeffrey S. "Campionamento casuale con un serbatoio." Transazioni ACM su software matematico (TOMS) 11.1 (1985): 37-57. ( Link )

Questo è chiamato un problema di campionamento del serbatoio . La soluzione semplice consiste nell’assegnare un numero casuale a ciascun elemento dell’elenco mentre lo vedi, quindi mantenere gli elementi k in alto (o in basso) come ordinato dal numero casuale.

Suggerirei: prima trova i tuoi k numeri casuali. Ordinali Quindi attraversa sia la lista collegata che i tuoi numeri casuali una volta.

Se in qualche modo non conosci la lunghezza della tua lista collegata (come?), Allora potresti prendere la prima k in una matrice, quindi per il nodo r, generare un numero casuale in [0, r), e se questo è meno di k, sostituisci l’ultimo elemento dell’array. (Non del tutto convinto che non sia un pregiudizio …)

A parte questo: “Se fossi in te, non avrei intenzione di partire da qui.” Sei sicuro che la lista collegata sia adatta al tuo problema? Non esiste una struttura dati migliore, come una buona vecchia lista di array piatti.

Se non si conosce la lunghezza dell’elenco, sarà necessario completarlo per garantire scelte casuali. Il metodo che ho usato in questo caso è quello descritto da Tom Hawtin ( 54070 ). Mentre attraversi la lista mantieni k elementi che formano la tua selezione casuale fino a quel punto. (Inizialmente si aggiungono solo i primi k elementi che si incontrano.) Quindi, con probabilità k/i , si sostituisce un elemento casuale dalla selezione con l’elemento iesimo della lista (cioè l’elemento in cui ci si trova, in quel momento).

È facile dimostrare che questo dà una selezione casuale. Dopo aver visto m elementi ( m > k ), abbiamo che ognuno dei primi m elementi della lista fa parte della tua selezione casuale con una probabilità k/m . Ciò che inizialmente detiene è banale. Quindi per ogni elemento m+1 , lo metti nella tua selezione (sostituendo un elemento casuale) con probabilità k/(m+1) . Ora devi mostrare che anche tutti gli altri elementi hanno probabilità k/(m+1) di essere selezionati. Abbiamo che la probabilità è k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (cioè la probabilità che l’elemento si trovasse nella lista dei tempi probabilità che sia ancora lì). Con il calcolo puoi mostrare chiaramente che questo è uguale a k/(m+1) .

Bene, è necessario sapere quale N è in fase di esecuzione almeno, anche se ciò comporta un ulteriore passaggio sull’elenco per contarli. L’algoritmo più semplice per farlo è quello di scegliere un numero casuale in N e rimuovere quell’elemento, ripetuto k volte. Oppure, se è ansible restituire numeri ripetuti, non rimuovere l’articolo.

A meno che non si disponga di N molto grandi e di requisiti di prestazioni molto rigorosi, questo algoritmo funziona con complessità O(N*k) , che dovrebbe essere accettabile.

Edit: Nevermind, il metodo di Tom Hawtin è molto meglio. Seleziona prima i numeri casuali, poi attraversa l’elenco una volta. La stessa complessità teorica, penso, ma runtime atteso molto meglio.

Perché non puoi semplicemente fare qualcosa del genere

 List GetKRandomFromList(List input, int k) List ret = new List(); for(i=0;i 

Sono sicuro che non intendi qualcosa di così semplice, quindi puoi specificarlo ulteriormente?