Lust auf einen Coding contest? Zahlen ohne zurücklegen ziehen
-
Jester schrieb:
genau. auch sortierst ist damit kein problem. aber ich nehme an, dass die Regeln wohl nochmal geändert werden.
Ja, dann extra für dich:
Für mathematiker und nitpicker gelten die folgenden Regeln:
Sei M die Menge aller möglichen subsets der größe k mit elementen aus 0,1,2,...,n-1 in denen jedes element nur genau einmal vorkommt. drawUniqueSubset zieht gleichverteilt ein zufälliges element aus |M| unter zuhilfename des random number generators Rng. Insbesodnere gilt für alle elemente x aus |M| p(x)=1/|M|.Eine Einsendung gilt nur als gültig, wenn sie
a) beweisbar gleichverteilt ist, unter der Annahme dass der Rng echter zufall ist
b) Die Implementierung der Verteilung unter zuhilfename echtes zufalls die BigCrush Testsuite besteht, wenn ein beliebiges bijektives mapping m:M->N genommen wird, welche die elemente aus M auf die elemente 0,1,|M|-1 abbildet.Für nicht nitpicker gelten die vorher genannten regeln.
-
Es wird nicht interessanter. Zwischen Fischer-Yates und dem
while(not schonDa())die beste Grenze ausmessen. Noch den einen oder anderen trivialen Algo dazwischenwerfen. Und den schlechtesten schnellsten PRNG finden, der für seinen Bereich gerade noch den Test besteht.
-
Die optimale Lösung enthält keinen Fischer-Yates. Sie enthält auch kein Set und keine hash-table. Und das macht die Aufgabe interessant, weil die optimale Lösung eben all das nicht ist, was man glaubt was sie sein sollte. Sicher, es reicht nicht für länger als einen Abend - aber sie war auch nicht für mir mehr gedacht. Sie soll auch keinen Basher oder Volkard länger als eine halbe Stunde fordern, aber sie soll für die Breite zugänglich sein. Also habe ich so 1-2h eingeplant.
Die genaue Definition war extra für Jaster um sein krankhaftes-falsch-verstehen-wollen zu beenden. Mir persönlich reicht alles, was sich wie die ersten k elemente von shuffle zurückgeben verhält.
-
otze schrieb:
Meine "optimale" Lösung enthält keinen Fischer-Yates.
Auch nicht bei k==n?
-
volkard schrieb:
otze schrieb:
Meine "optimale" Lösung enthält keinen Fischer-Yates.
Auch nicht bei k==n?
nope
-
otze schrieb:
Die genaue Definition war extra für Jaster um sein krankhaftes-falsch-verstehen-wollen zu beenden. Mir persönlich reicht alles, was sich wie die ersten k elemente von shuffle zurückgeben verhält.
Entschuldige mal. Ich habe hier jemand gesehen, der offensichtlich nicht in der Lage ist eine vernünftige Aufgabenstellung zu schreiben, die auch nur halbwegs präzise ist. (Ich empfehle Sudoku spielen, das soll eine super Übung sein). Also habe ich weitergeholfen, indem ich die richtigen Fragen gestellt habe. Ich hätte natürlich auch heimlich still und leise den Code zusammenkloppen können und das einreichen -- jetzt kann das nicht mehr so leicht passieren; nicht mehr von mir und auch nicht mehr von jemand anderem (auch wenn mir einige Regeln noch immer nicht klar sind).
Also: gern geschehen. Vielleicht kriegst Du es nächstes mal ja alleine hin!
Und dran bleiben: mathematisch präzises schreiben lernt man nicht an einem Tag. 
-
Ich fand die meisten Mathematiker ja immer komisch. Während die Physiker aus einer natürlichsprachlichen Erklärung fast immer das komplett richtige Problem mit Lösung ableiten können (wibei sie natürlich bei Randpunkten eine freundliche Frage stellen), streiten sich die Mathematiker stundenlang über einen halbsatz, der am Ende nichtmal für die Lösung bedeutsam ist. Hauptsache, der formalismus ist korrekt
-
Du magst das lustig finden, aber mir ist die Aufgabenstellung immer noch nicht 100% klar. (Und das obwohl ich kein mathematiker bin). Nochmal ganz explizit: wie werden gleichverteilung und performance gegeneinander abgewogen? Ist eine implementierung nur dann korrekt wenn sie 100% gleichverteilt ist, und wäre demnach rand()%100 eine schlechte möglichkeit um sich Zahlen von 0--99 zu besorgen oder nicht? Das hättest du sogar fast beantwortet, wenn du es nicht als (kindische) sonderregel für "nitpicker" deklariert hättest. Nur weiß ich dadurch halt immer noch nicht was die eigentlich geltenden "vorher genannte Regeln" sind.
Es mag ja sein, dass mancher sich das ganz wunderbar aus dem Text erschließt. Ich wette aber, dass sich dabei unterschiedliche leute auch gelegentlich sehr unterschiedliche Dinge erschließen. Und durch die unpräzise Fragestellung merkt das auch lange keiner. Genau deswegen habe ich mir angewöhnt bei Fragestellungen so lange nachzufragen bis ich sie verstanden habe. Was Du offensichtlich drollig findest ist für mich einfach nur Effizienz; was soll ich meine Zeit und Energie auf eine falsche Variante einer Problemstellung konzentrieren? Sowas ist meist in 5 Minuten geklärt, während Arbeit an der falschen Fragestellung mitunter Tage und Wochen an Arbeitszeit verbrät.
Das hat übrigens auch nix mit übermäßiger Formalisierung zu tun. Hättest du dazugeschrieben, dass eine lösung nur dann gilt, wenn alle Teilmengen exakt gleich wahrscheinlich sind, oder nur wenn dies bis auf minimale Abweichungen der Fall ist, dann hätte ich bescheid gewusst. Man kann sowas durchaus auch ohne starke Formalisierung beschreiben. Aber machen sollte man es. Man kann aber natürlich auch mit dem schimpfen, der merkt dass die Fragestellung nicht so eindeutig ist, wie man selber denkt. -- Was bildet der Arsch sich ein!
-
Was ist mit der Dummie-Lösung? Also k Zahlen aus dem RNG ziehen und dabei in einem Bitset die bereits vorgekommenen markieren (und dann bei einer Zweitziehung überspringen)?
Das hätte ich in Kombination mit einem Shuffle für größere k genommen, ist aber anscheinend nicht die Lösung.
-
Edit: Alles Quatsch, hatte einen Fehler im Code.
-
So, jetzt aber:
#include <algorithm> #include <iomanip> #include <iostream> #include <random> #include <set> #include <unordered_set> #include <vector> namespace unspannend_detail { template <typename T> void reserve(std::set<T>&, size_t) {} template <typename T> void reserve(std::unordered_set<T>& s, size_t n) { s.reserve(n); } template<bool Sorted, class Rng> std::vector<unsigned int> draw_select(unsigned int k, unsigned int n, Rng& rng) { std::vector<unsigned> v; v.reserve(k); if (3*k > 20*n) // Experimentell bestimmt! k/n > 3/20 = 0.15 { for (unsigned i=0; i<n; ++i) v.push_back(i); // iota_n while (k--) { int del = std::uniform_int_distribution<unsigned>(0, k)(rng); std::swap(v[del], v.back()); v.pop_back(); } if (Sorted) std::sort(v.begin(), v.end()); } else { typename std::conditional<Sorted, std::set<unsigned>, std::unordered_set<unsigned> >::type set; reserve(set, k); std::uniform_int_distribution<unsigned> dis(0, n-1); while (set.size() != k) set.insert(dis(rng)); v.assign(set.begin(), set.end()); } return v; } } template<class Rng> std::vector<unsigned int> drawUniqueSubset_unspannend(unsigned int k, unsigned int n, Rng& rng) { return unspannend_detail::draw_select<false>(k, n, rng); } template<class Rng> std::vector<unsigned> drawUniqueSubset_Arcoth(unsigned k, unsigned n, Rng& rng) { using namespace std; uniform_int_distribution<unsigned> dis(0, n - 1); vector<unsigned> rval; rval.reserve(k); if( float(k)/n < 0.6 ) // geschätzt! { vector<bool> previous(n); while( k-- ) { unsigned i; do i = dis(rng); while( previous[i] ); previous[i] = true; rval.push_back(i); } } else { for( unsigned i = dis(rng); i != n && k != 0; ++i, --k ) rval.push_back(i); for( unsigned i = 0; k != 0; ++i, --k ) rval.push_back(i); shuffle( begin(rval), end(rval), rng ); } return rval; } #include <ctime> template<typename PRNG> void test_against( std::vector<unsigned>(*first )(unsigned, unsigned, PRNG&), std::vector<unsigned>(*second)(unsigned, unsigned, PRNG&) ) { PRNG prng(std::random_device{}()); for( unsigned N = 100000; N < 10000000; N *= 2.5 ) { std::cout << "\nN = " << N << '\n'; auto now = clock(); for( float k_fac = 0.01; k_fac < 1; k_fac += 0.01 ) first(k_fac * N, N, prng); auto time_first = clock() - now; std::cout << "\tfirst needs " << std::setw(11) << std::right << time_first << ",\n"; now = clock(); for( float k_fac = 0.01; k_fac < 1; k_fac += 0.01 ) second(k_fac * N, N, prng); auto time_second = clock() - now; std::cout << "\tsecond needs " << std::setw(11) << std::right << time_second << "\n"; std::cout << "\n\tfirst/second = " << float(time_first)/time_second*100 << "%\n"; } } int main() { std::cout << "\n** LINEAR CONGRUENCY GENERATOR **\n\n"; test_against( drawUniqueSubset_Arcoth <std::minstd_rand>, drawUniqueSubset_unspannend<std::minstd_rand> ); std::cout << "\n\n** MERSENNE TWISTER **\n\n"; test_against( drawUniqueSubset_Arcoth <std::mt19937>, drawUniqueSubset_unspannend<std::mt19937> ); }Läuft mit Clang 3.4 mit -O3 und gibt folgendes aus:
** LINEAR CONGRUENCY GENERATOR ** N = 100000 first needs 148951, second needs 848336 first/second = 17.558% N = 250000 first needs 356256, second needs 2674922 first/second = 13.3184% N = 625000 first needs 927288, second needs 9211660 first/second = 10.0665% N = 1562500 first needs 2270358, second needs 27444058 first/second = 8.27268% N = 3906250 first needs 6663331, second needs 76202754 first/second = 8.74421% N = 9765625 first needs 19572171, second needs 203421893 first/second = 9.62147% ** MERSENNE TWISTER ** N = 100000 first needs 215800, second needs 806042 first/second = 26.7728% N = 250000 first needs 363053, second needs 2655339 first/second = 13.6726% N = 625000 first needs 885865, second needs 9239554 first/second = 9.58775% N = 1562500 first needs 2337987, second needs 28214382 first/second = 8.28651% N = 3906250 first needs 7117921, second needs 79105437 first/second = 8.99802% N = 9765625 first needs 21726353, second needs 230246943 first/second = 9.43611%Geht bestimmt von der Implementierung noch optimierter; Otzes Variante ist seiner Aussage nach dann etwa noch doppelt so schnell wie die hier.
Edit: Gerade erst bemerkt, dass ja die Shuffle-Variante nicht gleichverteilt ist...
Damit ist Otzes Methode deutlich schneller als die von Volkard vorgeschlagene.
