Lust auf einen Coding contest? Zahlen ohne zurücklegen ziehen

[otze]

Hi,

Erinnert ihr euch noch an die Coding Contests die wir früher mal hatten? Ich denke, ich habe ein hübsches Projekt entdeckt.

Die Aufgabe ist simpel, implementiere die folgenden Funktionen:

//1.
template<class Rng>
std::vector<unsigned int> drawUniqueSubset(unsigned int k, unsigned int n, Rng& rng);
//2.
template<class Rng>
std::vector<unsigned int> drawUniqueSubsetOrdered(unsigned int k, unsigned int n, Rng& rng);

Genaue Definition:

drawUniqueSubset zieht aus der Menge der natürlichen zahlen 0,...,n-1 ein zufälliges subset der Größe 1<=k<n und gibt es zurück. Das subset enthält keine doppelten elemente und ist nicht notwendigerweise sortiert. Der Zufallszahlengenerator rng liefert die notwendigen Zufallszahlen.

drawUniqueSubsetOrdered hat das folgende verhalten:

std::vector<unsigned int> result = drawUniqueSubset(k,n, rng);
std::sort(result.begin(),result.end());

Auswertung: Zuallererst zählt korrektheit. Darüber hinaus wird nach Geschwindigkeit bewertet.

Für n=10^3, n=10^4 und n=10^6 werden k-Werte zwischen k=0.01*n und k=0.99*n gewählt und die Laufzeit für jeden k-Wert über mehrere iterationen gemittelt.
Gewinner für ein n ist der Algorithmus, der die geringste Gesamtlaufzeit über alle k-Werte hat. Es ist möglich, einen Algorithmus für nur einen n-Wert einzureichen, aber nicht für einen Bereich der k-Werte.

Ich hoffe, das klingt spannend genug. Weckt das Interesse?

[hustbaer]

Ich weiss nicht, für mich klingt das nicht besonders spannend.
Bei drawUniqueSubsetOrdered kann man vielleicht noch ein bisschen was optimieren. Aber drawUniqueSubset...
Da wird der gewinnen der es schafft die Werte am schnellsten in den Vektor reinzubekommen.

[unspannend]

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(unsigned int k, unsigned int n, Rng& rng)
{
  return draw_select<true>(k, n, rng);
}

template<class Rng>
std::vector<unsigned int> drawUniqueSubsetOrdered(unsigned int k, unsigned int n, Rng& rng)
{
  return draw_select<false>(k, n, rng);
}

[unspannend]

Oh, gerade gemerkt: Das reserve stimmt nicht ganz. Das v.reserve(k); bitte in den else-Zweig verschieben und im if ein v.reserve(n); vor das iota_n.

[unspannend]

Ok, die Bedingung war auch falsch. Hier die korrigierte Version mit Messung: http://ideone.com/aDdIpx

[Jester]

Darf man zufällig immer dieselbe Teilmenge zurückgeben?

[otze]

Jester schrieb:

Darf man zufällig immer dieselbe Teilmenge zurückgeben?

Nein, die Wahrscheinlichkeit für eine Zahl im set zu sein, sollte für alle zahlen gleich sein.

@hustbaer
In der Tat halte ich die zweite Version für einfacher, weil weniger möglich ist.

Ich kenne einen schnelleren Algorithmus als unspannend nennt.

//edit erst gerade gesehen, dass die Bedingung falsch war und ich im falschen Zweig hin. Trotzdem nicht optimal. Da geht noch was.

[otze]

Ich habe gerade nochmal die Versionen getestet und würde nochmal n um ne größenordnung eröhen dann sieht man hübsche unterschiede zwischen allen algorithmen die mir eingefallen sind.

Und dann bin ich momentan bis zu factor 25 schneller als unspannend

[Jester]

otze schrieb:

Jester schrieb:

Darf man zufällig immer dieselbe Teilmenge zurückgeben?

Nein, die Wahrscheinlichkeit für eine Zahl im set zu sein, sollte für alle zahlen gleich sein.

Ah, auch kein Problem. Ich ziehe die erste Zahl zufällig und gebe dann die k nachfolgenden aus.

[cooky451]

Ich denke die Zeitmessung, der RNG und am besten die komplette main() Funktion sollten für alle gleich und damit vorgegeben sein.

[Fytch]

Jester schrieb:

Ah, auch kein Problem. Ich ziehe die erste Zahl zufällig und gebe dann die k nachfolgenden aus.

dumme frage aber: haben wir dann nicht eine quasi-binomialverteilung (bei dem aber in der mitte (bei der maximalen wahrscheinlichkeit) k elemente sind)?

edit: ahh, ist mir eben in den sinn gekommen, dass man einfach eine beliebige startzahl in [0, n) ziehen kann und bei einfügen der k elemente im falle des erreichens von n einfach wieder bei 0 anfangen kann... patsch.

[Jester]

asfdlol schrieb:

Jester schrieb:

Ah, auch kein Problem. Ich ziehe die erste Zahl zufällig und gebe dann die k nachfolgenden aus.

dumme frage aber: haben wir dann nicht eine quasi-binomialverteilung (bei dem aber in der mitte (bei der maximalen wahrscheinlichkeit) k elemente sind)?

edit: ahh, ist mir eben in den sinn gekommen, dass man einfach eine beliebige startzahl in [0, n) ziehen kann und bei einfügen der k elemente im falle des erreichens von n einfach wieder bei 0 anfangen kann... patsch.

genau. auch sortierst ist damit kein problem. aber ich nehme an, dass die Regeln wohl nochmal geändert werden.

[otze]

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.

[volkard]

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.

[otze]

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.

[volkard]

otze schrieb:

Meine "optimale" Lösung enthält keinen Fischer-Yates.

Auch nicht bei k==n?

[otze]

volkard schrieb:

otze schrieb:

Meine "optimale" Lösung enthält keinen Fischer-Yates.

Auch nicht bei k==n?

nope

[Jester]

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.

[otze]

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

[Jester]

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!