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

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?

SeppJ

Fricky667 schrieb:

du tust ja gerade so, als hätte ich dir etwas schlimmes angetan. alles klar bei dir?

Du strapazierst die Gesamtqualität des Forums, indem du zu sämtlichen Themen schlecht durchdachte Antworten gibst (oft ohne überhaupt den Thread gelesen zu haben), die korrigiert werden müssen. Wenn man dich korrigiert, liest du die Erklärungen nicht, sondern wiederholst deinen Quatsch. Beispiel dieser Thread: Die Diskussion hätte allerspätestens bei wobs Korrektur enden müssen, der sehr genau erklärt, warum die Lösung schlecht ist.

Fricky667 schrieb:

lass das man den OP entscheiden, ob er meinen vorschlag akzeptabel findet.

Denkst du?

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.

Aber all dies habe ich auch schon 3x gesagt. Ich habe sogar schon einmal den TE zitiert um dir zu zeigen, dass deine Variante ausdrücklich nicht gewünscht war. Du wiederholst deinen Quatsch trotzdem noch. Erinnert mich sehr an einen ehemaligen User, den du kennen dürftest...

Fricky667

SeppJ schrieb:

Fricky667 schrieb:

du tust ja gerade so, als hätte ich dir etwas schlimmes angetan. alles klar bei dir?

Du strapazierst die Gesamtqualität des Forums, indem du zu sämtlichen Themen schlecht durchdachte Antworten gibst

Ich bin halt nur ein unwissender Forenuser, wie die meisten anderen hier, und schreibe nur was mein begrenzter Erkenntnisvorrat bieten kann. Wenn Diskussion außerhalb der Lehrmeinung hier unerwünscht sind, dann lass es mich wissen.

Was sagt eigentlich Marc++us zu Typen wie dir? Oder ist der nicht mehr Admin? Kommt mir fast so vor ...

Columbo

Fricky667 schrieb:

Was sagt eigentlich Marc++us zu Typen wie dir?

SeppJ ist eines der wertvollsten Mitglieder dieses Forums, und sein Verhalten läuft i.d.R. eine kalkulierte Linie zwischen professioneller Zurückhaltung und angemessener Kritik. Nichts, was er angesprochen hat, ist unwahr.

Ich bin halt nur ein unwissender Forenuser, wie die meisten anderen hier

Das ist Ok. Der Punkt ist, dass Du Unsinn redest, und dann nach einer Erklärung anderer Forenuser versuchst, die Unsinnigkeit Deiner Aussage zu relativieren. Bspw.

Mein Vorschlag hängt nun mal stark von der Performance der shuffle-Implementation ab.

Nein. Weil Dein Vorschlag rein von der Komplexität völliger Quatsch ist. Da hängt nichts von konkreten Implementierungen ab.

du tust ja gerade so, als hätte ich dir etwas schlimmes angetan.

Ja, Du bist nämlich unfähig, aus deinen Fehlern zu lernen. Das hat dich jetzt unbeliebt gemacht, und entsprechend ist SeppJs Antwort gereizt. Nächstes mal solltest Du erst antworten, wenn Du überzeugt bist, die Thematik durchdacht zu haben.

Fricky667

Arcoth schrieb:

Das hat dich jetzt unbeliebt gemacht, und entsprechend ist SeppJs Antwort gereizt.

der muss sich halt ein bisschen am riemen reißen. dann geht das.

Columbo

Fricky667 schrieb:

Arcoth schrieb:

Das hat dich jetzt unbeliebt gemacht, und entsprechend ist SeppJs Antwort gereizt.

der muss sich halt ein bisschen am riemen reißen. dann geht das.

Gönn Dir erstmal 'n Duden, Diggi.

Fricky667

Arcoth schrieb:

Fricky667 schrieb:

Arcoth schrieb:

Das hat dich jetzt unbeliebt gemacht, und entsprechend ist SeppJs Antwort gereizt.

der muss sich halt ein bisschen am riemen reißen. dann geht das.

Gönn Dir erstmal 'n Duden, Diggi.

kein akt, gibts umsonst im inet.

SeppJ

Fricky667 schrieb:

kein akt, gibts umsonst im inet.

Für dich ist ein Wörterbuch umsonst, für alle anderen gratis.

Fricky667

SeppJ schrieb:

Fricky667 schrieb:

kein akt, gibts umsonst im inet.

Für dich ist ein Wörterbuch umsonst, für alle anderen gratis.

jetzt lass mal das hassen sein, kumpel. make love not war.

temi

Vielleicht lässt sich ja daraus etwas machen?

http://preshing.com/20121224/how-to-generate-a-sequence-of-unique-random-integers/

Kommt vermutlich darauf an, wie die Qualität der Zufallszahlen sein soll.

Leider verstehe ich (noch) nicht, wie campers Vorschlag funktioniert, aber immer wieder interessant hier mitzulesen.

camper

temi schrieb:

Leider verstehe ich (noch) nicht, wie campers Vorschlag funktioniert, aber immer wieder interessant hier mitzulesen.

Im Prinzip ist das auch nur eine Variantion von SeppJs Algorithmus, mit dem Unterschied, dass nicht eine Liste der noch ziehbaren Zahlen geführt wird, sondern eine, die die gezogenen Zahlen enthält, also praktisch eine Liste der Lücken in SeppJs Liste. Nimmt man noch SeppJs Optimierungsvorschlag hinzu, könnte man einfach eine map benutzen, die bereits gezogenen Zahlen auf solche abbildet, die nicht mehr durch den Primäroutput des Generators erreicht werden können:

template <typename URBG>
vector<int> get_random_sequence(URBG& g, int N, int M) {
    assert( M <= N );
    vector<int> result;
    unordered_map<int, int> q;
    for ( int m = 0; m < M; ++m ) {
        int x = uniform_int_distribution( 0, N - 1 - m )( g );
        auto last = q.find( N - 1 - m );
        auto map_to = last == q.end() ? N - 1 - m : last->second;
        auto [it, insert_success] = q.try_emplace( x, map_to );
        if ( !insert_success ) {
            x = it->second;
            it->second = map_to;
        }
        if ( last != q.end() {
            q.erase( last );
        }
        result.push_back( x );
    }
    return result;
}