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

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.

Fricky667

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::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.

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*

SeppJ

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.

Fricky667

SeppJ schrieb:

Nur weil andere Leute dir auch erklären(!), dass dein Vorschlag Quatsch ist, sind die anderen Leute nicht ich. Dein Vorschlag ist Quatsch.

bleib locker, alter. der vorschlag ist cool, weil total easy. nur die taktzyklenzähler werden eventuell damit hadern. mach doch 'n benchmark.

SeppJ

Fricky667 schrieb:

SeppJ schrieb:

Nur weil andere Leute dir auch erklären(!), dass dein Vorschlag Quatsch ist, sind die anderen Leute nicht ich. Dein Vorschlag ist Quatsch.

bleib locker, alter. der vorschlag ist cool, weil total easy. nur die taktzyklenzähler werden eventuell damit hadern. mach doch 'n benchmark.

Quatsch, mal wieder. Es war explizit nach effizienten Lösungen gefragt. Es braucht auch keinen Benchmark, wob hat erklärt, wieso dein Lösung immer schlechter ist. Aber nichts von alledem hast du gelesen. Mal wieder.

Fricky667

SeppJ schrieb:

Fricky667 schrieb:

SeppJ schrieb:

Nur weil andere Leute dir auch erklären(!), dass dein Vorschlag Quatsch ist, sind die anderen Leute nicht ich. Dein Vorschlag ist Quatsch.

bleib locker, alter. der vorschlag ist cool, weil total easy. nur die taktzyklenzähler werden eventuell damit hadern. mach doch 'n benchmark.

Quatsch, mal wieder. Es war explizit nach effizienten Lösungen gefragt. Es braucht auch keinen Benchmark, wob hat erklärt, wieso dein Lösung immer schlechter ist. Aber nichts von alledem hast du gelesen. Mal wieder.

lass das man den OP entscheiden, ob er meinen vorschlag akzeptabel findet. du tust ja gerade so, als hätte ich dir etwas schlimmes angetan. alles klar bei dir?