Wie generiert man effizient eine Liste von K sich nicht wiederholenden ganzen Zahlen zwischen 0 und einer Obergrenze N [Duplikat]
https://stackoverflow.com/questions/158716
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Auf diese Frage gibt es hier bereits eine Antwort:
Die Frage liefert alle notwendigen Daten:Was ist ein effizienter Algorithmus zum Generieren einer Sequenz von? K sich nicht wiederholende ganze Zahlen innerhalb eines bestimmten Intervalls [0,N-1].Der triviale Algorithmus (Zufallszahlen generieren und vor dem Hinzufügen zur Sequenz nachsehen, ob sie bereits vorhanden sind) ist sehr teuer K ist groß und nah genug an N.
Der in bereitgestellte Algorithmus Effiziente Auswahl einer Reihe zufälliger Elemente aus einer verknüpften Liste scheint komplizierter als nötig zu sein und erfordert eine gewisse Implementierung.Ich habe gerade einen anderen Algorithmus gefunden, der den Job offenbar gut erledigt, solange man alle relevanten Parameter in einem einzigen Durchgang kennt.
Lösung
Das Zufallsmodul Aus der Python -Bibliothek ist es extrem einfach und effektiv:
from random import sample
print sample(xrange(N), K)
sample Die Funktion gibt eine Liste von k eindeutigen Elementen zurück, die aus der angegebenen Sequenz ausgewählt wurden.
xrange ist ein "List-Emulator", dh es verhält sich wie eine Liste aufeinanderfolgender Zahlen, ohne ihn im Speicher zu erstellen, was es für Aufgaben wie diese superschnell macht.
Andere Tipps
Im Die Kunst der Computerprogrammierung, Band 2: Seminumerische Algorithmen, dritte Ausgabe, Knuth beschreibt den folgenden Auswahl -Abtastalgorithmus:
Algorithmus S (Auswahltechnik). So wählen Sie N -Datensätze zufällig aus einem Satz n aus, wobei 0 <n ≤ N.
S1. [Initialisieren] Setzen Sie T ← 0, m ← 0. (Während dieses Algorithmus repräsentiert M die Anzahl der bisher ausgewählten Datensätze, und T ist die Gesamtzahl der Eingabebestellen, mit denen wir uns befasst haben.)
S2. [Generieren Sie U.] Erzeugen Sie eine zufällige Zahl u, die gleichmäßig zwischen Null und einem verteilt ist.
S3. [Test.] Wenn (n - t) u ≥ n - m, fahren Sie mit Schritt S5 fort.
S4. [SELECT.] Wählen Sie den nächsten Datensatz für die Probe aus und erhöhen Sie M und T um 1. Wenn M <n, gehen Sie zu Schritt S2. Andernfalls ist die Probe vollständig und der Algorithmus endet.
S5. [Überspringen.] Überspringen Sie den nächsten Datensatz (geben Sie sie nicht in die Probe ein), erhöhen Sie T um 1 und kehren Sie zu Schritt S2 zurück.
Eine Implementierung kann einfacher zu folgen sein als die Beschreibung. Hier ist eine gemeinsame LISP -Implementierung, die n zufällige Mitglieder aus einer Liste auswählt:
(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))))
Und hier ist eine Implementierung, die keine Rekursion verwendet und mit allen Arten von Sequenzen funktioniert:
(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))
Es ist tatsächlich möglich, dies im Raum proportional zur Anzahl der ausgewählten Elemente zu tun, anstatt die Größe des Satzes, aus dem Sie sich auswählen, unabhängig davon, welcher Anteil Ihres Gesamtsatzes Sie auswählen. Sie tun dies, indem Sie eine zufällige Permutation generieren und dann so ausgewählt werden:
Wählen Sie eine Blockchiffer, wie z. TEE oder Xtea. Verwenden XOR FALTING Um die Blockgröße auf die kleinste Leistung von zwei größer als der Satz zu reduzieren, aus dem Sie auswählen. Verwenden Sie den zufälligen Samen als Schlüssel zur Chiffre. Um ein Element n in der Permutation zu erzeugen, verschlüsseln Sie n mit der Chiffre. Wenn sich die Ausgabennummer nicht in Ihrem Satz befindet, verschlüsseln Sie dies. Wiederholen Sie, bis sich die Nummer innerhalb des Satzes befindet. Im Durchschnitt müssen Sie weniger als zwei Verschlüsse pro generierte Zahl durchführen. Dies hat den zusätzlichen Vorteil, dass wenn Ihr Samen kryptografisch sicher ist, ebenso Ihre gesamte Permutation.
Ich habe darüber viel detaillierter geschrieben hier.
Der folgende Code (in C, unbekannter Ursprung) scheint das Problem sehr gut zu lösen:
/* 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;
}
Weiß jemand, wo ich weitere Juwelen wie dieses finden kann?
Ein Array erzeugen 0...N-1 gefüllt a[i] = i.
Dann mischen Sie den ersten K Artikel.
Mischen:
- Anfang
J = N-1 - Wählen Sie eine Zufallszahl aus
0...J(sagen,R) - Tauschen
a[R]mita[J]- seit
Rkann gleich seinJ, Das Element kann mit sich selbst getauscht werden
- seit
- subtrahieren
1ausJund wiederholen.
Schließlich nehmen Sie K letzte Elemente.
Dies wählt im Wesentlichen ein zufälliges Element aus der Liste aus, bewegt es aus, wählt dann ein zufälliges Element aus der verbleibenden Liste aus und so weiter.
Arbeitet in OK) und AN) Zeit, erfordert AN) Lagerung.
Der Mischteil heißt Fisher-yates Shuffle oder Knuths Shuffle, beschrieben im 2. Band von Die Kunst der Computerprogrammierung.
Beschleunigen Sie den trivialen Algorithmus, indem Sie die K -Zahlen in einem Hashing -Geschäft aufbewahren. Wenn Sie k wissen, bevor Sie anfangen, werden die Ineffizienz des Einfügens in eine Hash-Karte weggeworfen, und Sie erhalten immer noch den Vorteil einer schnellen Suche.
Meine Lösung ist C ++ orientiert, aber ich bin sicher, sie könnte in andere Sprachen übersetzt werden, da sie ziemlich einfach ist.
- Generieren Sie zunächst eine verknüpfte Liste mit K -Elementen, die von 0 bis k wechseln
- Generieren Sie dann, solange die Liste nicht leer ist, eine Zufallszahl zwischen 0 und der Größe des Vektors
- Nehmen Sie dieses Element, drücken Sie es in einen anderen Vektor und entfernen Sie es aus der ursprünglichen Liste
Diese Lösung umfasst nur zwei Schleifen -Iterationen und keine Hash -Tabellen -Lookups oder irgendetwas der Art. Also im tatsächlichen Code:
// 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));
}
Schritt 1: Generieren Sie Ihre Liste der Ganzzahlen.
Schritt 2: Durchführen Knuth Shuffle.
Beachten Sie, dass Sie nicht die gesamte Liste mischen müssen, da Sie mit dem Knuth Shuffle -Algorithmus nur N -Mischungen anwenden können, wobei n die Anzahl der Elemente zur Rückgabe ist. Das Erstellen der Liste dauert weiterhin proportional zur Größe der Liste, aber Sie können Ihre vorhandene Liste für zukünftige Mischungsanforderungen wiederverwenden (vorausgesetzt, die Größe bleibt gleich), ohne dass die teilweise gemischte Liste vor dem Neustart des Mischungsalgorithmus vorgeschoben werden muss.
Der grundlegende Algorithmus für Knuth Shuffle ist, dass Sie mit einer Liste von Ganzzahlen beginnen. Dann tauschen Sie die erste Ganzzahl mit einer beliebigen Zahl in der Liste aus und geben die aktuelle (neue) erste Ganzzahl zurück. Dann tauschen Sie die zweite Ganzzahl mit einer beliebigen Zahl in der Liste (außer der ersten) und geben die aktuelle (neue) zweite Ganzzahl zurück. Dann ... etc ...
Dies ist ein absurd einfacher Algorithmus, aber achten Sie darauf, dass Sie beim Ausführen des Swaps den aktuellen Element in die Liste aufnehmen, oder Sie werden den Algorithmus brechen.
Die Reservoir -Sampling -Version ist ziemlich einfach:
my $N = 20;
my $k;
my @r;
while(<>) {
if(++$k <= $N) {
push @r, $_;
} elsif(rand(1) <= ($N/$k)) {
$r[rand(@r)] = $_;
}
}
print @r;
Das sind $ n zufällig ausgewählte Reihen von Stdin. Ersetzen Sie das Zeug <>/$ _ durch etwas anderes, wenn Sie keine Zeilen aus einer Datei verwenden, aber es ist ein ziemlich einfacher Algorithmus.
Wenn die Liste sortiert ist, zum Beispiel, wenn Sie K -Elemente aus N extrahieren möchten, sich jedoch nicht um ihre relative Reihenfolge kümmern, wird in der Zeitung ein effizienter Algorithmus vorgeschlagen Ein effizienter Algorithmus für die sequentielle Zufallsabtastung (Jeffrey Scott Vitter, ACM -Transaktionen auf mathematischer Software, Vol. 13, Nr. 1, März 1987, Seiten 56-67.).
bearbeitet So fügen Sie den Code in C ++ mit Boost hinzu. Ich habe es gerade eingegeben und es könnte viele Fehler geben. Die zufälligen Zahlen stammen aus der Boost -Bibliothek mit einem dummen Samen, also machen Sie damit nichts Ernstes.
/* 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
gibt das folgende Ouptut auf meinem Laptop
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
Dieser Ruby -Code zeigt die Reservoir -Probenahme, Algorithmus r Methode. In jedem Zyklus wähle ich aus n=5 einzigartige zufällige ganze Zahlen von [0,N=10) Angebot:
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
Ausgang:
100000. cycle...
200000. cycle...
300000. cycle...
400000. cycle...
500000. cycle...
--------------
250272
249924
249628
249894
250193
250202
249647
249606
250600
250034
Alle Ganzzahl zwischen 0 und 9 wurden mit nahezu gleicher Wahrscheinlichkeit ausgewählt.
Es ist im Wesentlichen Knuths Algorithmus angewendet auf willkürliche Sequenzen (in der Tat hat diese Antwort eine Lisp -Version davon). Der Algorithmus ist AN) zeitlich und kann sein O (1) im Speicher, wenn die Sequenz wie in gezeigt in sie gestreamt wird @Michaelcramers Antwort.
Hier ist eine Möglichkeit, dies in O (n) ohne zusätzlichen Speicher zu tun. Ich bin mir ziemlich sicher, dass dies keine rein zufällige Verteilung ist, aber es ist wahrscheinlich nah genug für viele Verwendungen.
/* 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;
}
Dies ist Perl -Code. Grep ist ein Filter, und wie immer habe ich diesen Code nicht getestet.
@list = grep ($_ % I) == 0, (0..N);
- I = Intervall
- N = Obergrenze
Holen Sie sich nur Zahlen, die Ihrem Intervall über den Modul -Operator entsprechen.
@list = grep ($_ % 3) == 0, (0..30);
wird 0, 3, 6, ... 30 zurückkehren
Dies ist Pseudo -Perl -Code. Möglicherweise müssen Sie es optimieren, um es zusammenzustellen.
