Come si genera in modo efficiente un elenco di interi non ripetibili di K tra 0 e un N superiore associato

La domanda fornisce tutti i dati necessari: che cos’è un algoritmo efficiente per generare una sequenza di numeri interi non ripetitivi di K all’interno di un dato intervallo [0, N-1] . L’algoritmo banale (che genera numeri casuali e, prima di aggiungerli alla sequenza, cercandoli per vedere se erano già lì) è molto costoso se K è grande e abbastanza vicino a N.

L’algoritmo fornito in Selezione efficiente di un insieme di elementi casuali da una lista collegata sembra più complicato del necessario e richiede qualche implementazione. Ho appena trovato un altro algoritmo che sembra fare il lavoro bene, purché tu conosca tutti i parametri rilevanti, in un unico passaggio.

Il modulo casuale della libreria Python lo rende estremamente facile ed efficace:

from random import sample print sample(xrange(N), K) 

sample funzione di sample restituisce una lista di elementi unici K scelti dalla sequenza data.
xrange è un “list emulator”, cioè si comporta come un elenco di numeri consecutivi senza crearlo in memoria, il che lo rende super-veloce per compiti come questo.

In The Art of Computer Programming, Volume 2: Algoritmi seminali, terza edizione , Knuth descrive il seguente algoritmo di campionamento di selezione:

Algoritmo S (tecnica di campionamento della selezione). Per selezionare n record a caso da un set di N, dove 0

S1. [Inizializza.] Imposta t ← 0, m ← 0. (Durante questo algoritmo, m rappresenta il numero di record selezionati finora, e t è il numero totale di record di input che abbiamo trattato).

S2. [Genera U.] Genera un numero casuale U, uniformsmente distribuito tra zero e uno.

S3. [Test.] Se (N – t) U ≥ n – m, andare al passo S5.

S4. [Seleziona.] Selezionare il record successivo per il campione e aumentare m e t di 1. Se m

S5. [Salta.] Salta il prossimo record (non includerlo nel campione), aumenta t di 1 e torna al punto S2.

Un’implementazione potrebbe essere più facile da seguire rispetto alla descrizione. Ecco un’implementazione Common Lisp che seleziona n membri casuali da una lista:

 (defun sample-list (n list &optional (length (length list)) result) (cond ((= length 0) result) ((< (* length (random 1.0)) n) (sample-list (1- n) (cdr list) (1- length) (cons (car list) result))) (t (sample-list n (cdr list) (1- length) result)))) 

Ed ecco un'implementazione che non usa la ricorsione e che funziona con tutti i tipi di sequenze:

 (defun sample (n sequence) (let ((length (length sequence)) (result (subseq sequence 0 n))) (loop with m = 0 for i from 0 and u = (random 1.0) do (when (< (* (- length i) u) (- nm)) (setf (elt result m) (elt sequence i)) (incf m)) until (= mn)) result)) 

In realtà è ansible farlo nello spazio proporzionale al numero di elementi selezionati, piuttosto che alle dimensioni del set da cui si sta selezionando, indipendentemente dalla proporzione del set totale che si sta selezionando. Lo fai generando una permutazione casuale, quindi selezionandola in questo modo:

Scegli un codice a blocchi, come TEA o XTEA. Usa il piegamento XOR per ridurre la dimensione del blocco alla potenza minima di due più grande rispetto al set da cui stai selezionando. Usa il seme casuale come chiave del codice. Per generare un elemento n nella permutazione, crittografare n con il codice. Se il numero di uscita non è nel tuo set, crittografalo. Ripeti fino a quando il numero è all’interno del set. In media dovrai fare meno di due cifrature per numero generato. Questo ha il vantaggio aggiunto che se il tuo seme è crittograficamente sicuro, così è la tua intera permutazione.

Ho scritto su questo in modo molto più dettagliato qui .

Il seguente codice (in C, origine sconosciuta) sembra risolvere il problema estremamente bene:

  /* generate N sorted, non-duplicate integers in [0, max[ */ int *generate(int n, int max) { int i, m, a; int *g = (int *)calloc(n, sizeof(int)); if ( ! g) return 0; m = 0; for (i=0; i 

Qualcuno sa dove posso trovare altre gemme come questa?

Genera un array 0...N-1 riempito a[i] = i .

Quindi mescola i primi elementi K

Mischiare le carte:

  • Inizia J = N-1
  • Scegli un numero casuale 0...J (per esempio, R )
  • scambia a[R] con a[J]
    • poiché R può essere uguale a J , l’elemento può essere scambiato con se stesso
  • sottrarre 1 da J e ripetere.

Infine, prendi K ultimi elementi.

Questo essenzialmente seleziona un elemento casuale dall’elenco, lo sposta fuori, quindi preleva un elemento casuale dall’elenco rimanente e così via.

Funziona in tempo O (K) e O (N) , richiede memoria O (N) .

La parte che si sposta è chiamata Fisher-Yates shuffle o Knuth’s shuffle , descritta nel secondo volume di The Art of Computer Programming.

Accelerare l’algoritmo banale memorizzando i numeri K in un archivio di hashing. Conoscere K prima di iniziare elimina tutta l’inefficienza dell’inserimento in una mappa hash, e ottieni comunque il vantaggio di una rapida ricerca.

La mia soluzione è orientata al C ++, ma sono sicuro che potrebbe essere tradotta in altre lingue poiché è piuttosto semplice.

  • Innanzitutto, genera una lista concatenata con elementi K, che va da 0 a K
  • Quindi finché l’elenco non è vuoto, genera un numero casuale compreso tra 0 e la dimensione del vettore
  • Prendi quell’elemento, spingilo in un altro vettore e rimuovilo dall’elenco originale

Questa soluzione prevede solo due iterazioni di loop e nessuna ricerca nella tabella hash o qualcosa del genere. Quindi nel codice attuale:

 // Assume K is the highest number in the list std::vector sorted_list; std::vector random_list; for(int i = 0; i < K; ++i) { sorted_list.push_back(i); } // Loop to K - 1 elements, as this will cause problems when trying to erase // the first element while(!sorted_list.size() > 1) { int rand_index = rand() % sorted_list.size(); random_list.push_back(sorted_list.at(rand_index)); sorted_list.erase(sorted_list.begin() + rand_index); } // Finally push back the last remaining element to the random list // The if() statement here is just a sanity check, in case K == 0 if(!sorted_list.empty()) { random_list.push_back(sorted_list.at(0)); } 

Passaggio 1: genera l’elenco di numeri interi.
Passaggio 2: Esegui Knuth Shuffle .

Si noti che non è necessario mescolare l’intera lista, poiché l’algoritmo Knuth Shuffle consente di applicare solo n shuffles, dove n è il numero di elementi da restituire. Generare la lista richiederà tempo in proporzione alla dimensione della lista, ma è ansible riutilizzare la lista esistente per eventuali esigenze di shuffling future (supponendo che le dimensioni rimangano le stesse) senza necessità di rimescolare l’elenco parzialmente mescolato prima di riavviare l’algoritmo shuffling.

L’algoritmo di base per Knuth Shuffle è che inizi con un elenco di numeri interi. Quindi, si scambia il primo numero intero con qualsiasi numero nell’elenco e si restituisce il primo (intero) primo intero. Quindi, si scambia il secondo intero con qualsiasi numero nell’elenco (tranne il primo) e si restituisce il secondo (intero) intero intero. Poi … ecc …

Questo è un algoritmo assurdamente semplice, ma fai attenzione a includere l’elemento corrente nell’elenco quando esegui lo scambio o interromperà l’algoritmo.

La versione Campionamento serbatoio è piuttosto semplice:

 my $N = 20; my $k; my @r; while(<>) { if(++$k <= $N) { push @r, $_; } elsif(rand(1) <= ($N/$k)) { $r[rand(@r)] = $_; } } print @r; 

Sono $ N le file selezionate a caso da STDIN. Sostituisci le cose <> / $ _ con qualcos'altro se non stai usando le righe da un file, ma è un algoritmo piuttosto semplice.

Se la lista è ordinata, per esempio, se vuoi estrarre elementi K da N, ma non ti importa del loro ordine relativo, viene proposto un algoritmo efficiente nel documento An Efficient Algorithm for Sequential Random Sampling (Jeffrey Scott Vitter, Transazioni ACM su software matematico , Vol. 13, No. 1, marzo 1987, pagine 56-67.).

modificato per aggiungere il codice in c ++ usando boost. Ho appena scritto e potrebbero esserci molti errori. I numeri casuali provengono dalla libreria boost, con un seme stupido, quindi non fare nulla di serio con questo.

 /* Sampling according to [Vitter87]. * * Bibliography * [Vitter 87] * Jeffrey Scott Vitter, * An Efficient Algorithm for Sequential Random Sampling * ACM Transactions on MAthematical Software, 13 (1), 58 (1987). */ #include  #include  #include  #include  #include  #include  #include  #include  #include  using namespace std; // This is a typedef for a random number generator. // Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand typedef boost::minstd_rand base_generator_type; // Define a random number generator and initialize it with a reproducible // seed. // (The seed is unsigned, otherwise the wrong overload may be selected // when using mt19937 as the base_generator_type.) base_generator_type generator(0xBB84u); //TODO : change the seed above ! // Defines the suitable uniform ditribution. boost::uniform_real<> uni_dist(0,1); boost::variate_generator > uni(generator, uni_dist); void SequentialSamplesMethodA(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method A. { int top=NK, S, curr=0, currsample=-1; double Nreal=N, quot=1., V; while (K>=2) { V=uni(); S=0; quot=top/Nreal; while (quot > V) { S++; top--; Nreal--; quot *= top/Nreal; } currsample+=1+S; cout << curr << " : " << currsample << "\n"; Nreal--; K--;curr++; } // special case K=1 to avoid overflow S=floor(round(Nreal)*uni()); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } void SequentialSamplesMethodD(int K, int N) // Outputs K sorted random integers out of 0..N, taken according to // [Vitter87], method D. { const int negalphainv=-13; //between -20 and -7 according to [Vitter87] //optimized for an implementation in 1987 !!! int curr=0, currsample=0; int threshold=-negalphainv*K; double Kreal=K, Kinv=1./Kreal, Nreal=N; double Vprime=exp(log(uni())*Kinv); int qu1=N+1-K; double qu1real=qu1; double Kmin1inv, X, U, negSreal, y1, y2, top, bottom; int S, limit; while ((K>1)&&(threshold S) {bottom=Nreal-Kreal; limit=NS;} else {bottom=Nreal+negSreal-1.; limit=qu1;} for(int t=N-1;t>=limit;t--) {y2*=top/bottom;top--; bottom--;} if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv)) {//Accept ! Vprime=exp(log(uni())*Kmin1inv); break; } Vprime=exp(log(uni())*Kmin1inv); } // Step D5: Select the (S+1)th record currsample+=1+S; cout << curr << " : " << currsample << "\n"; curr++; N-=S+1; Nreal+=negSreal-1.; K-=1; Kreal-=1; Kinv=Kmin1inv; qu1-=S; qu1real+=negSreal; threshold+=negalphainv; } if (K>1) {SequentialSamplesMethodA(K, N);} else { S=floor(N*Vprime); currsample+=1+S; cout << curr << " : " << currsample << "\n"; } } int main(void) { int Ntest=10000000, Ktest=Ntest/100; SequentialSamplesMethodD(Ktest,Ntest); return 0; } $ time ./sampling|tail 

dà il seguente valore sul mio portatile

 99990 : 9998882 99991 : 9998885 99992 : 9999021 99993 : 9999058 99994 : 9999339 99995 : 9999359 99996 : 9999411 99997 : 9999427 99998 : 9999584 99999 : 9999745 real 0m0.075s user 0m0.060s sys 0m0.000s 

Questo codice Ruby mostra il metodo Reservoir Sampling, Algorithm R. In ogni ciclo, seleziono n=5 numeri interi casuali da [0,N=10) :

 t=0 m=0 N=10 n=5 s=0 distrib=Array.new(N,0) for i in 1..500000 do t=0 m=0 s=0 while m=nm then t=t+1 else distrib[s]+=1 m=m+1 t=t+1 end #if s=s+1 end #while if (i % 100000)==0 then puts i.to_s + ". cycle..." end end #for puts "--------------" puts distrib 

produzione:

 100000. cycle... 200000. cycle... 300000. cycle... 400000. cycle... 500000. cycle... -------------- 250272 249924 249628 249894 250193 250202 249647 249606 250600 250034 

tutti i numeri interi compresi tra 0 e 9 sono stati scelti con quasi la stessa probabilità.

È essenzialmente l’algoritmo di Knuth applicato alle sequenze arbitrarie (infatti, quella risposta ha una versione LISP di questo). L’algoritmo è O (N) nel tempo e può essere O (1) in memoria se la sequenza è in streaming come mostrato nella risposta di @ MichaelCramer .

Ecco un modo per farlo in O (N) senza spazio aggiuntivo. Sono abbastanza sicuro che questa non è una distribuzione puramente casuale, ma probabilmente è abbastanza vicina per molti usi.

 /* generate N sorted, non-duplicate integers in [0, max[ in O(N))*/ int *generate(int n, int max) { float step,a,v=0; int i; int *g = (int *)calloc(n, sizeof(int)); if ( ! g) return 0; for (i=0; imax) { g[i]=max; //fix up overflow max=g[i--]-1; } return g; } 

Questo è il codice Perl. Grep è un filtro e, come sempre, non ho testato questo codice.

 @list = grep ($_ % I) == 0, (0..N); 
  • I = intervallo
  • N = Upper Bound

Ottieni solo i numeri che corrispondono al tuo intervallo tramite l’operatore modulo.

 @list = grep ($_ % 3) == 0, (0..30); 

restituirà 0, 3, 6, … 30

Questo è pseudo codice Perl. Potrebbe essere necessario modificarlo per farlo compilare.