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

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

  • V

    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.

    0
  • O

    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.

    0
  • V

    otze schrieb:

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

    Auch nicht bei k==n?

    0
  • O

    volkard schrieb:

    otze schrieb:

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

    Auch nicht bei k==n?

    nope

    0
  • J

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

    0
  • O

    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 🤡

    0
  • J

    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!

    0

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

    0

  • Edit: Alles Quatsch, hatte einen Fehler im Code.

    0

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

    0
Anmelden zum Antworten