m unterschiedliche zufällig Zahlen aus 0 bis n ziehen, c++ funktion?
-
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 gezogen1. 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 <= xDas ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.
-
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.
-
RandomName schrieb:
camper schrieb:
Eine Modifikation vermeidet wiederholtes Ziehen:
N=Anzahl Zahlen (0 ... N-1)
M=Anzahl zu ziehen
m=Anzahl bereits gezogen1. 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 <= xDas ist nicht mehr 100% uniform zufall aber schaut nicht schlecht aus, danke.
Erklärung?
-
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.
-
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.
-
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].
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 gezogen1. 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 <= xDas 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.
-
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].
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?
-
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
-
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 wurdeGeht 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.
-
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 wurdeGeht 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.
-
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)?
-
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.
-
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::shuffledas 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.
-
wob schrieb:
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::shuffledas 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.
Bist du ein Doppelaccount von SeppJ?
Mein Vorschlag hängt nun mal stark von der Performance der shuffle-Implementation ab. Ich behaupte ja nicht, dass mein Vorschlag superschnell ist. Aber er ist straight-forward. schritt 1, 2, 3, und fertig. Für den Noob absolut easy zu implementieren.
Überhaupt finde ich es sehr befremdlich, dass sich C++ Coder um Taktzyklen scheren. Das ist im Grunde eine Bankrotterklärung an C, Mother of all modern computer languages, *GG*
-
Fricky667 schrieb:
Bist du ein Doppelaccount von SeppJ?
Nur weil andere Leute dir auch erklären(!), dass dein Vorschlag Quatsch ist, sind die anderen Leute nicht ich. Dein Vorschlag ist Quatsch. Wenn du den Erklärungen zuhören würdest, könntest du vielleicht sogar etwas lernen.
Mein Vorschlag hängt nun mal stark von der Performance der shuffle-Implementation ab. Ich behaupte ja nicht, dass mein Vorschlag superschnell ist. Aber er ist straight-forward. schritt 1, 2, 3, und fertig. Für den Noob absolut easy zu implementieren.
Hast du den Thread gelesen? Oder wenigstens die Eingangsfrage? Es geht um Perfomance und absolut nicht um deinen Noob-Müll:
randomName schrieb:
Es gibt ja std::random_shuffle, die shuffelt aber alle 100 Zahlen. Wenn ich nun aber 1000 aus 1.000.000 haben möchte ist das viel Arbeit umsonst.
Du hast zudem die Erklärung von wob offensichtlich nicht gelesen
random_shuffle macht einfach viel zu viel Arbeit umsonst, weil es ganz etwas anderes tut, als hier gesucht wird. Da hilft keine noch so effiziente Implementierung. 10^10 Zahlen zu mischen dauert auf egal welche Weise eine Ewigkeit. Wenn du den Erklärungen ausnahmsweise mal zuhören würdest, könntest du vielleicht sogar etwas lernen.Überhaupt finde ich es sehr befremdlich, dass sich C++ Coder um Taktzyklen scheren. Das ist im Grunde eine Bankrotterklärung an C, Mother of all modern computer languages, *GG*
Quatsch, mal wieder.