m unterschiedliche zufällig Zahlen aus 0 bis n ziehen, c++ funktion?

SeppJ

RandomName schrieb:

Caligulaminus schrieb:

Oder einfach so lange Zufallszahlen in ein (unordered_)set stecken, bis .size() == m ?

Das enspricht von der Laufzeit her Schlangenmensch's Vorschlag oder?
Edit: Scheint zumindest im Average case besser zu sein.

Das ist nur eine andere Implementierung, Schlangenmensch hat schließlich nicht gesagt, wie genau die Prüfung stattfinden soll. Für sehr kleine m (sagen wir mal < 100) ist vermutlich eine lineare Suche ganz ok, für größere Mengen dann eben Divide&Conquer wie beim Set. Oder man kann ja auch ein unordered_set heran ziehen, das sollte immer ganz ok sein.

Eine Fallunterscheidung, je nachdem wie groß sie sind ist auch doof.

Wieso? Ist doch clever, je nach Bedarf einen besser geeigneten Algorithmus zu wählen.

Und wäre halt gut wenn man vorher sagen kann, wie lang es dauert. Schlangenmensch's Vorschlag kann ja, wenn man unglaubliches Pech hat Ewigkeiten dauern.

Wenn absolut perfekte Vorhersagekraft nötig ist, ist Schlangenmenschs Methode nicht geeignet, aber ich behaupte mal, dass du dir das Leben selber unnötig schwer machst, wenn du diese verlangst. Ist es wirklich relevant, wenn Schlangenmenschs Methode in 0.000001% aller Fälle länger braucht als erwartet? Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

camper

RandomName schrieb:

Das enspricht von der Laufzeit her Schlangenmensch's Vorschlag oder?
Edit: Scheint zumindest im Average case besser zu sein.

Kommt darauf, wie du feststellst, ob eine Zahl bereits gezogen wurde.

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Schritt 2 könnte man für hinreichend kleine M einfach per sortierter Liste handhaben => O(M*M); für größere M könnte ein balancierter Suchbaum, der sich die Anzahl der (direkten und indirekten) Kindknoten merkt, verwendet werden => O(M*log(M)) mit rel. großem k

SeppJ schrieb:

Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

Aber verbraucht viel Platz. Aber ich glaub ich werde es trotzdem nehmen, 10 Millionen Integer sind auch nur 40Megabyte. Copmuter soll sich mal nicht so anstellen.
Hhmm, aber in einen Durchlauf wird das nicht nur einmal gemacht. Bei 10Millionen müsste er ca. 100Mio Werte initialisieren, dann wärn wir schon bei 400MB für z.B 10k Zufallswerte, macht 40KB pro Zahl.

camper schrieb:

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Das ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.

SeppJ

RandomName schrieb:

SeppJ schrieb:

Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

Aber verbraucht viel Platz. Aber ich glaub ich werde es trotzdem nehmen, 10 Millionen Integer sind auch nur 40Megabyte. Copmuter soll sich mal nicht so anstellen.
Hhmm, aber in einen Durchlauf wird das nicht nur einmal gemacht. Bei 10Millionen müsste er ca. 100Mio Werte initialisieren, dann wärn wir schon bei 400MB für z.B 10k Zufallswerte, macht 40KB pro Zahl.

Kommt auf die Details an. Wenn es nicht parallel geschieht und die Grundmenge immer gleich sein sollte, kann man die alte Liste weiter verwenden. Man muss die Zahlen ja nicht wirklich löschen, es reicht schließlich, die gezogenen Zahlen ans Ende zu sortieren und dann die ober Schranke für die Zufallszahl um eins zu verringern.

Bei 10k Werten würde ich einfach die Methode von Schlangenmensch benutzen, wenn Speicherplatz wirklich ein Problem ist.
~~
Noch eine andere Idee, die ausnutzt, dass deine Wertemenge natürliche Zahlen sind: Man nehme die Methode von Schlangenmensch. Wenn man eine Zahl zieht, die es schon gab, dann zieht man keine komplett neue Zahl, sondern sucht (in beide Richtungen) nach der nächsten ungezogenen Zahl und nimmt stattdessen diese. Wenn mich nicht alles täuscht, sollte dies die Verteilung der gezogenen Zahlen nicht beeinflussen,~~ aber man vermeidet so die Gefahr, dass der Algorithmus gegen Ende sehr lange sucht, wenn er 999,999 Zahlen aus 1,000,000 ziehen soll.

edit: Habe campers Vorschlag nicht gesehen, der so ähnlich ist wie meine Modifikation von Schlangenmenschs Methode. campers Vorschlag ist besser als meine Modifikation. Ich sehe gerade nicht, wieso campers Methode die Verteilung stören sollte.
edit2: Meine Methode war doch nicht gleichverteilt. Ich unterstütze campers Vorschlag.

camper

RandomName schrieb:

camper schrieb:

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Das ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.

Erklärung?

scrontch

RandomName schrieb:

SeppJ schrieb:

Meine Methode ist übrigens von der Laufzeit her perfekt vorhersagbar.

Aber verbraucht viel Platz. Aber ich glaub ich werde es trotzdem nehmen, 10 Millionen Integer sind auch nur 40Megabyte. Copmuter soll sich mal nicht so anstellen.
Hhmm, aber in einen Durchlauf wird das nicht nur einmal gemacht. Bei 10Millionen müsste er ca. 100Mio Werte initialisieren, dann wärn wir schon bei 400MB für z.B 10k Zufallswerte, macht 40KB pro Zahl.

Was wird nicht nur einmal gemacht? Wenn Du öfter von vorne anfangen willst, dann häng einfach die vorher gezogenen Zahlen wieder an den Vektor hinten dran. Das entspricht dem zurücklegen in die Urne.

camper

SeppJ schrieb:

Noch eine andere Idee, die ausnutzt, dass deine Wertemenge natürliche Zahlen sind: Man nehme die Methode von Schlangenmensch. Wenn man eine Zahl zieht, die es schon gab, dann zieht man keine komplett neue Zahl, sondern sucht (in beide Richtungen) nach der nächsten ungezogenen Zahl und nimmt stattdessen diese. Wenn mich nicht alles täuscht, sollte dies die Verteilung der gezogenen Zahlen nicht beeinflussen, aber man vermeidet so die Gefahr, dass der Algorithmus gegen Ende sehr lange sucht, wenn er 999,999 Zahlen aus 1,000,000 ziehen soll.

Bei dieser Methode besteht für eine Zahl, die zu einer bereits gezogenen Zahl, benachbart liegt, eine größere Wahrscheinlichkeit, gezogen zu werden, als für eine Zahl, deren Nachfolger und Vorgänger noch nicht gezogen wurden.

scrontch

Inspiriert durch camper (dessen Methode ich aber gerade nicht blicke ):
Oder arbeite einfach nur mit einem einzigen Vektor [0..N-1], bei dem sowohl die Urne [0..N-1-m] als auch das was rausgezogen wurde drin ist [N-m..N-1].

mit V[N-1-m].

Und dann m++

Wenn Du hier fertig bist und neu anfangen willst brauchst du hier gar nichts weiter tun! Einfach wieder mit m=0 von vorne anfangen.

camper schrieb:

RandomName schrieb:

camper schrieb:

Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen

1. Ziehe Zahl x 0 ... (N-1-m)
2. Beginnend bei der kleinsten bereits gezogenen Zahl: erhöhe x um 1 für jede gezogene Zahl y, mit y <= x

Das ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.

Erklärung?

Tut mir Leid ich hab y '>=' x gelesen. Mit <= sollte es passen. Danke.

Liste wiederverwenden gestaltet sich schwierig, da n sich ändert.
Muss also z.b. sicherstellen, dass keine Zahl in der Liste größer als das aktuelle n ist und auch das jedes zahl zwischen 0 und n vorhanden ist.

camper

scrontch schrieb:

Inspiriert durch camper (dessen Methode ich aber gerade nicht blicke ):
Oder arbeite einfach nur mit einem einzigen Vektor [0..N-1], bei dem sowohl die Urne [0..N-1-m] als auch das was rausgezogen wurde drin ist [N-m..N-1].

mit V[N-1-m].

Und dann m++

Wenn Du hier fertig bist und neu anfangen willst brauchst du hier gar nichts weiter tun! Einfach wieder mit m=0 von vorne anfangen.

Das ist SeppJs ursprüngliche Variante.

Hier meine in richtigem C++

template <typename URBG>
vector<int> get_random_sequence(URBG& g, int N, int M) {
    assert( M <= N );
    vector<int> result, sorted;
    for ( int m = 0; m < M; ++m ) {
        int x = uniform_int_distribution( 0, N - 1 - m )( g );
        auto it = sorted.begin();
        for ( ; it != sorted.end(); ++it ) {
            if ( y > x )
                break;
            ++x;
        }
        sorted.insert( it, x );
        result.push_back( x );
    }
}

Die Baum-Variante ist ein bisschen komplexer.

Danke für den Code, ich hatte es nach dem Lesefehler zwar schon kapiert aber kann ja nicht schaden

Hat das eigenlich auch einen Namen oder selbst ausgedacht?

camper

RandomName schrieb:

Hat das eigenlich auch einen Namen oder selbst ausgedacht?

Ja.

Zieh einfach 10 mal Zahlen zwischen 0 und 9 und addiere zur n. Zahl n*10

Fricky667

SeppJ schrieb:

Gibt es nicht fertig, aber ist leicht selber zu programmieren:
1. Liste mit den Werten, aus denen gezogen werden soll machen
2. Zufälligen Wert daraus ziehen
3. Gezogenen Wert aus der Liste entfernen
4. Schritte 2. und 3. wiederholen bis die gewünschte Anzahl Werte gezogen wurde

Geht noch einen Tick einfacher.
1. Array mit gültigen Werten befüllen.
2. random-shuffle auf diesem Array ausführen.
3. die ersten n Werte nehmen und fertig.

SeppJ

Fricky667 schrieb:

SeppJ schrieb:

Gibt es nicht fertig, aber ist leicht selber zu programmieren:
1. Liste mit den Werten, aus denen gezogen werden soll machen
2. Zufälligen Wert daraus ziehen
3. Gezogenen Wert aus der Liste entfernen
4. Schritte 2. und 3. wiederholen bis die gewünschte Anzahl Werte gezogen wurde

Geht noch einen Tick einfacher.
1. Array mit gültigen Werten befüllen.
2. random-shuffle auf diesem Array ausführen.
3. die ersten n Werte nehmen und fertig.

Wieder mal Quatsch. Dadurch hast du viel mehr Rechenaufwand, ohne jeden Zugewinn.

Fricky667

SeppJ schrieb:

Dadurch hast du viel mehr Rechenaufwand, ohne jeden Zugewinn.

Meinst du wirklich? Die STL hat doch eine Random-Shuffle-Funktion. Ist die wirklich so schlecht (aus Benutzersicht wie auch Processor-Cycles betreffend)?

Fricky667

der Aufruf ist jedenfalls recht einfach:

random_shuffle (&a[erstes_element], &a[letztes_element+1]);

das müsste mal einer benchmarken, um es mit dem SeppJ-Algorithmus laufzeitmäßig zu vergleichen. Intuitiv sehe ich keinen von beiden vorn.

wob

Fricky667 schrieb:

der Aufruf ist jedenfalls recht einfach:
random_shuffle (&a[erstes_element], &a[letztes_element+1]);

1.: Warum nicht begin(a) und end(a)?
2.: Warum eine Function der STL nehmen, die deprecated ist? --> std::shuffle

das müsste mal einer benchmarken, um es mit dem SeppJ-Algorithmus laufzeitmäßig zu vergleichen. Intuitiv sehe ich keinen von beiden vorn.

Ist nicht offensichtlich, dass SeppJs Algo schneller ist? Nimm an, du willst 1 Element aus 10^7 ziehen. Mit SeppJ musst du ein Element ziehen und bist fertig. Du müsstest dagegen erst das gesamte Array durchmischen. Offensichtlich ist das schlechter. Schauen wir uns den anderen Extremfall an, dass man alle Zahlen zieht. Dann müssen beide Algorithmen gleich viel tun und wir haben Gleichstand (zumindest ungefähr, kommt sicher auf die genaue Implementierung an). Also ist SeppJs Algo nie langsamer, aber fast immer schneller.