Come si fa a generare in modo efficiente un elenco di K non la ripetizione di numeri interi compresi tra 0 e un limite superiore N [duplica]
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
A questa domanda ha già una risposta qui:
La domanda che dà tutti i dati necessari:che cosa è un algoritmo efficiente per generare una sequenza di K non ripetere interi all'interno di un determinato intervallo di [0,N-1].Il banale algoritmo di generazione di numeri casuali e, prima di aggiungere la sequenza, guardare in su per vedere se erano già lì) è molto costoso se K è grande e abbastanza vicino a N.
L'algoritmo fornito in In modo efficiente la selezione di un insieme di elementi casuali da una lista collegata sembra più complicato del necessario, e richiede un po ' di attuazione.Ho appena trovato un altro algoritmo che sembra fare il lavoro bene, purché si conoscono tutti i parametri pertinenti, in un unico passaggio.
Soluzione
Il modulo random dalla libreria Python rende estremamente semplice ed efficace:
from random import sample
print sample(xrange(N), K)
sample la funzione restituisce un elenco di K elementi scelti dalla data sequenza.
xrange è un elenco "emulatore", cioèsi comporta come un elenco di numeri consecutivi senza creare nella memoria, che lo rende super-veloce per compiti come questo.
Altri suggerimenti
In The Art of Computer Programming, Volume 2:Seminumerical Algoritmi, Terza Edizione, Knuth descrive la seguente selezione algoritmo di campionamento:
Algoritmo di S (Selezione della tecnica di campionamento).Per selezionare n record a caso da un insieme di N, dove 0 < n ≤ N
S1.[Inizializza.] Set 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 affrontato.)
S2.[Generare U.] Generare un numero casuale U, uniformemente distribuita tra zero e uno.
S3.[Test.] Se (N – t)U ≥ n – m, andare al passaggio S5.
S4.[Selez.] Selezionare il record successivo per il campione, e aumentare la m e t a 1.Se m < n, andare al passaggio S2;altrimenti il campione è completa e l'algoritmo termina.
S5.[Skip.] Salta il record successivo (non includere nel campione), aumentare la t di 1, e tornare al passo S2.
Un'implementazione può essere più facile da seguire rispetto alla descrizione.Qui è un Common Lisp implementazione di selezionare n i membri casuale da un elenco:
(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))))
E qui è un'implementazione che non utilizza 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)
(- n m))
(setf (elt result m) (elt sequence i))
(incf m))
until (= m n))
result))
In realtà è possibile fare questo in spazio proporzionale al numero di elementi selezionati, piuttosto che la dimensione del set di scegliere, a prescindere di quale percentuale del totale del set che si sta selezionando.A tale scopo è generare una permutazione casuale, quindi selezionando come questo:
Scegli un blocco di cifratura, come TÈ o XTEA.Utilizzare XOR pieghevole per ridurre la dimensione del blocco per la più piccola potenza di due più grande del set di scegliere.Utilizzare il seme casuale, come chiave del cifrario.Per generare un elemento n nella permutazione, crittografare n con la crittografia.Se il numero di uscita non è nel vostro set di crittografia.Ripetere fino a quando il numero è all'interno del set.In media, si dovrà fare a meno di due cifrature al numero generato.Questo ha il vantaggio che se il seme è crittograficamente sicuro, così è la tua permutazione.
Ho scritto su questo in modo molto più dettagliato qui.
Il seguente codice (in C, di origine sconosciuta) sembra risolvere il problema molto 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<max; i++) {
a = random_in_between(0, max - i);
if (a < n - m) {
g[m] = i;
m ++;
}
}
return g;
}
Qualcuno sa dove posso trovare più gemme come questa?
Generare una matrice 0...N-1 pieno a[i] = i.
Poi rimescola il primo K elementi.
Mischiare:
- Inizio
J = N-1 - Scegliere un numero casuale
0...J(per dire,R) - swap
a[R]cona[J]- dal
Rpuò essere uguale aJ, l'elemento può essere scambiato con sé
- dal
- sottrarre
1daJe ripetere.
Infine, prendere K ultimi elementi.
Questo essenzialmente sceglie un elemento casuale dall'elenco, sposta, poi sceglie un elemento casuale dall'elenco rimanente, e così via.
Opere in O(K) e O(N) tempo, richiede O(N) di archiviazione.
Il rimescolamento parte è chiamata Fisher-Yates shuffle o Knuth shuffle, descritto nel 2 ° volume di The Art of Computer Programming.
Accelerare il banale algoritmo memorizzando i K numeri in un hash store.Sapendo K prima di iniziare toglie tutta l'inefficienza di inserimento in una mappa hash, e ancora ottenere il beneficio di fast look-up.
La mia soluzione è C++ orientato, ma sono sicuro che potrebbe essere tradotta in altre lingue, dal momento che è abbastanza semplice.
- Prima di tutto, generare un elenco collegato con K elementi, che va da 0 a K
- Quindi fintanto che la lista non è vuota, generare un numero casuale tra 0 e la dimensione del vettore
- Prendere l'elemento, spingere in un altro vettore, e rimuoverlo dalla lista originale
Questa soluzione comporta solo due iterazioni del ciclo, e non la tabella di hash per ricerche o qualcosa del genere.Così nel codice vero e proprio:
// Assume K is the highest number in the list
std::vector<int> sorted_list;
std::vector<int> 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:Generare la vostra lista di interi.
Passaggio 2:Eseguire Knuth Shuffle.
Nota che non c'è bisogno di mescolare l'intero elenco, dal momento che il Knuth algoritmo di riproduzione Casuale consente di applicare solo n mischia, dove n è il numero di elementi di tornare.A generare l'elenco richiederà ancora del tempo proporzionale alla dimensione della lista, ma si può riutilizzare l'esistente elenco per l'eventuale rimescolamento esigenze (supponendo che la risoluzione rimane la stessa) senza bisogno di preshuffle parzialmente mescolati elenco prima di riavviare l'algoritmo di mescolamento.
L'algoritmo di base per la riproduzione Casuale Knuth è che si inizia con un elenco di numeri interi.Quindi, si scambiano il primo numero intero con qualsiasi numero in lista e restituisce la corrente (nuovo) primo numero intero.Quindi, si scambia il secondo numero con un numero nell'elenco (tranne la prima) e restituisce la corrente (nuovo) secondo numero intero.Poi...ecc...
Questo è un assurdamente semplice algoritmo, ma attenzione che includono l'elemento corrente nella lista quando si esegue l'operazione di swap o si rompono le algoritmo.
Il Serbatoio di Campionamento versione è abbastanza semplice:
my $N = 20;
my $k;
my @r;
while(<>) {
if(++$k <= $N) {
push @r, $_;
} elsif(rand(1) <= ($N/$k)) {
$r[rand(@r)] = $_;
}
}
print @r;
Che è $N selezionati in modo casuale righe da STDIN.Sostituire il <>/$_ roba con qualcosa d'altro, se non si usano le righe da un file, ma è piuttosto semplice algoritmo.
Se l'elenco è ordinato, per esempio, se si desidera estrarre K elementi di N, ma non si preoccupano loro ordine relativo, un efficiente algoritmo proposto nel libro Un Algoritmo Efficiente per Sequenziale Campionamento Casuale (Jeffrey Scott Vitter, ACM Transactions on Software Matematici, Vol.13, N.1, Marzo 1987, Pagine 56-67.).
a cura aggiungere il codice in c++ utilizzando boost.Ho appena digitato e ci potrebbero essere molti errori.I numeri casuali vengono dalla libreria boost, con una stupida seme, in modo da non fare qualcosa 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 <stdlib.h>
#include <string.h>
#include <math.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <boost/random/linear_congruential.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/uniform_real.hpp>
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<base_generator_type&, boost::uniform_real<> > 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=N-K, 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<N))
{
Kmin1inv=1./(Kreal-1.);
while(1)
{//Step D2: generate X and U
while(1)
{
X=Nreal*(1-Vprime);
S=floor(X);
if (S<qu1) {break;}
Vprime=exp(log(uni())*Kinv);
}
U=uni();
negSreal=-S;
//step D3: Accept ?
y1=exp(log(U*Nreal/qu1real)*Kmin1inv);
Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real));
if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true
//step D4 Accept ?
y2=0; top=Nreal-1.;
if (K-1 > S)
{bottom=Nreal-Kreal; limit=N-S;}
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
ha pronunciato la seguente ouptut 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 mette in mostra il Serbatoio Di Campionamento, L'Algoritmo Di R metodo.In ogni ciclo, sono in grado di selezionare n=5 unica numeri interi casuali da [0,N=10) gamma:
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<n do
u=rand()
if (N-t)*u>=n-m 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
output:
100000. cycle...
200000. cycle...
300000. cycle...
400000. cycle...
500000. cycle...
--------------
250272
249924
249628
249894
250193
250202
249647
249606
250600
250034
tutti i valori interi compresi tra 0 a 9 sono stati scelti con quasi la stessa probabilità.
Sostanzialmente si tratta di L'algoritmo di Knuth applicato a sequenze arbitrarie (anzi, la risposta è un LISP versione di questo).L'algoritmo è O(N) nel tempo e possono essere O(1) in memoria se la sequenza è in streaming in esso, come mostrato in @MichaelCramer risposta.
Ecco un modo per farlo in O(N) senza l'extra storage.Sono abbastanza sicuro che questo non è un fatto puramente casuale distribuzione, ma probabilmente abbastanza vicino 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; i<n; i++) {
step = (max-v)/(float)(n-i);
v+ = floating_pt_random_in_between(0.0, step*2.0);
if ((int)v == g[i-1]){
v=(int)v+1; //avoid collisions
}
g[i]=v;
}
while (g[i]>max) {
g[i]=max; //fix up overflow
max=g[i--]-1;
}
return g;
}
Questo è il Codice del Perl.Grep è un filtro, e come sempre io non l'ho provato questo codice.
@list = grep ($_ % I) == 0, (0..N);
- I = intervallo di
- N = Limite Superiore
Solo ottenere i numeri che corrispondono ai tuoi intervallo tramite l'operatore di modulo.
@list = grep ($_ % 3) == 0, (0..30);
restituisce 0, 3, 6, ...30
Questa è la pseudo codice Perl.Potrebbe essere necessario modificarlo per farlo compilare.
