Ungewollte Größen bei Ausgabe von Zufallszahlen

CStoll

Arijum schrieb:

Hier nun der fertige funktionierende Code:

Und das Array für deine Zahlen ist immer noch zu klein - du reservierst Platz für 5 Werte, quetschst danach aber 7 Werte hinein.
(und ich habe keine Ahnung, was regulär in dem Speicher steht, den die beiden überschüssigen Elemente überschreiben)

ipsec

Im Übrigen wählst du von allen Möglichkeiten, doppelte Zahlen auszuschließen, die mit Abstand ineffizienteste. Ich skizziere mal eine effiziente Variante:
1. Lege einen Conatiner mit den Elementen 1 bis 49 an.
2. Wähle zufällig eine Zahl aus diesem Container im Bereich 1-49. Vertausche (swap) diese Zahl mit der letzten im Container. (Beispiel: 3 wurde gewählt -> der Container enthält nun 1, 2, 49, 4, ..., 48, 3). Die 3 ist deine erste Lottozahl.
3. Wähle zufällig eine Zahl aus dem Container im Bereich 1-48 und vertausche sie mit der vorletzten Zahl. Das ist deine zweite Lottozahl.
4. Wähle zufällig eine Zahl aus dem Container im Bereich 1-47 und vertausche sie mit der vorvorletzten Zahl. Das ist deine dritte Lottozahl.
5. Fahre nach dem Muster fort, bis du 7 Zahlen hast.

volkard

ipsec schrieb:

Im Übrigen wählst du von allen Möglichkeiten, doppelte Zahlen auszuschließen, die mit Abstand ineffizienteste.

Ich gehe davon aus, daß das kleine break noch seinen Weg in die Suchschleife findet.
Die erste Zahl trifft immer.
Die zweite mit Wahrscheinlichkeit 48/49.
Die dritte mit Wahrscheinlichkeit 47/49.
usw.
Also braucht man durchschnittlich 1+49/48+49/47+49/46+49/45+49/44 mal raten.
Also 6.33 mal. Ach, soo viel schlimmer als Dein Weg, der erstmal 49 Zahlen füllen muß, wird es schon nicht sein.
Man braucht 6.33 mal statt 6 mal rand().
Und man braucht 21.77 Arrayzugriffe statt 61.

Manchmal macht es mich traurig, daß hier so oft die Anfänger verrissen werden, und zwar immer von Neulingen mit nur zwei bis drei Jahren Erfahrung mit schwacher Faktenlage.

ipsec

Es lang mir fern, irgendetwas zu verreissen, vielmehr wollte ich Möglichkeiten aufzeigen, wie man es besser machen kann. Und wenn man von O(n²) auf O(n) kommt und einen Algorithmus mit deterministischer Laufzeit hat anstelle eines, der potentiell nie terminiert, ist das m.E. eine deutliche Verbesserung, auch wenn bei 7 aus 49 der Unterschied selten spürbar sein wird.

Und darüber hinaus mag ich zwar erst seit 4 Jahren hier angemeldet sein, mit C++ habe ich aber schon länger zu tun.

volkard

ipsec schrieb:

Es lang mir fern, irgendetwas zu verreissen,

Er hat Mühe, die native Lösung zu schaffen, da braucht er sicher kein
Im Übrigen wählst du von allen Möglichkeiten, doppelte Zahlen auszuschließen, die mit Abstand ineffizienteste.

vielmehr wollte ich Möglichkeiten aufzeigen, wie man es besser machen kann.

Haste wohl nicht geschafft, wie ich nachgewiesen habe.

Und wenn man von O(n²) auf O(n) kommt

Wenn Dein O(n) lahmer ist als sein O(n²), dann ist das akademischer Unfug.

und einen Algorithmus mit deterministischer Laufzeit hat anstelle eines, der potentiell nie terminiert,

Auch ein wenig weltfremd.

ist das m.E. eine deutliche Verbesserung, auch wenn bei 7 aus 49 der Unterschied selten spürbar sein wird.

Egal, welche nun schneller ist, seine ist sicher nicht die von allen Lösungen ineffizienteste.

Wie kommst du eigentlich auf die Rechnung zum Erwartungswert? Sie würde auch noch ein endliches Ergebnis für 50 aus 49 ergeben, wo Unendlich herauskommen müsste.

Geraten und nachgemessen. Übereinstimmung.

#include <iostream>
using namespace std;

int main (int argc, const char * argv[])
{
    double randCount=0,arrayCount=0,runCount=0;
	for(;;) {
		int zahlen[6];
		for(int i=0; i<6; ++i) {
nochmal:
			int n=rand()%49+1;
			++randCount;
			for(int j=0; j<i; ++j){
                ++arrayCount;
				if(zahlen[j]==n) {
					goto nochmal;
				}
			}
            ++arrayCount;
			zahlen[i]=n;
		}
		++runCount;
		cout<<randCount/runCount<<'\t'<<arrayCount/runCount<<'\n';
	}
}

Und darüber hinaus mag ich zwar erst seit 4 Jahren hier angemeldet sein, mit C++ habe ich aber schon länger zu tun.

Für Dich speziell hätte ich die Jahre wohl höher legen sollen. Aber allgemein scheint so bei 2 bis 3 Erfahrungsjahren das Maximum des von mir angesprochenen Problems zu liegen.

Die Mecker geht auch kaum an Dich. Du warst nur gerade da, um ein Problem anzusprechen, das mich seit Jahren juckt.

volkard

Wie kommst du eigentlich auf die Rechnung zum Erwartungswert? Sie würde auch noch ein endliches Ergebnis für 50 aus 49 ergeben, wo Unendlich herauskommen müsste.

Mal schauen...
49/49 + 49/48 + 49/47 + 49/ 46 + ... + 49/3 + 49/2 + 49/1 + 49/0
Naja, Unendlich würde ich nicht sagen, sondern Undefiniert.

Mitleid

ipsec schrieb:

Es lang mir fern, irgendetwas zu verreissen, vielmehr wollte ich Möglichkeiten aufzeigen, wie man es besser machen kann. Und wenn man von O(n²) auf O(n) kommt und einen Algorithmus mit deterministischer Laufzeit hat anstelle eines, der potentiell nie terminiert, ist das m.E. eine deutliche Verbesserung, auch wenn bei 7 aus 49 der Unterschied selten spürbar sein wird....

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert. Und da "der Algorithmus" hier keine variable Eingabe hat würde mich mal interessieren was hier dein n sein soll?

SeppJ

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Und da "der Algorithmus" hier keine variable Eingabe hat würde mich mal interessieren was hier dein n sein soll?

Ahh, da ist mit ipsec ein bisschen der innere Programmierer durchgebrannt, der ein Problem immer so abstrakt wie möglich behandelt. Du weißt sicherlich selbst, was er mit n meint. Und sein Algorithmus ist sicher auch für sehr viele Fälle von X Zahlen aus Y der beste. Nur bei dem X/Y Verhältnis des konkreten Problems 6 aus 49 ist er schlechter als der naive Algorithmus (der für allgemeine X und Y tatsächlich sehr ineffizient werden kann).

Mitleid

SeppJ schrieb:

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Die Annahme, dass rand() sich standardkonform verhält reicht.

SeppJ schrieb:

...Du weißt sicherlich selbst, was er mit n meint. ...

Nö. Erklärs mir.

Ich hab die vorgeschlagenen Lösungen und meinen eigenen Ansatz (von dem ich mir mehr erhofft hatte ) mal gegeneinander gebencht; nach jeder Ziehung wird die Summe zusammengerechnet, um 1. den Optimizer zu überlisten und 2. die Benutzung der gezogenen Zahlen zu simulieren, die ja nachträglich zu erwarten ist. std::set verliert hier natürlich etwas; wenn euch die Benutzung der gezogenen Zahlen nicht interessiert, sind die Ergebnisse für den std::set-Ansatz dementsprechend wertlos. Code:

#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>

#include <cstdlib>
#include <ctime>

int const TURNS = 10000000;

int main() {
  std::clock_t bench[5];
  long sum = 0;

  std::srand(std::time(0));

  bench[0] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    std::set<int> s;

    do {
      s.insert(std::rand() % 49 + 1);
    } while(s.size() < 6);

    sum += std::accumulate(s.begin(), s.end(), 0);
  }

  bench[1] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    int numbers[] = {  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
                      11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
                      21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
                      31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
                      41, 42, 43, 44, 45, 46, 47, 48, 49, 50 };

    for(int j = 0; j < 6; ++j) {
      std::swap(numbers[j], numbers[std::rand() % (49 - j) + j]);
    }

    sum += std::accumulate(numbers, numbers + 6, 0);
  }

  bench[2] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    int werte[6];
    for(int j = 0; j < 6; ++j) {
      bool keep_going = true;

      while(keep_going) {
        werte[j] = std::rand() % 49 + 1;
        keep_going = false;

        for(int k = 0; k < j; ++k) {
          if(werte[k] == werte[j]) {
            keep_going = true;
            break;
          }
        }
      }
    }

    sum += std::accumulate(werte, werte + 6, 0);
  }

  bench[3] = std::clock();

  for(int i = 0; i < TURNS; ++i) {
    bool already_used[50] = {};
    int werte[6];

    for(int j = 0; j < 6; ++j) {
      int x;

      do {
        x = std::rand() % 49 + 1;
      } while(already_used[x]);

      werte[j] = x;
      already_used[x] = true;
    }

    sum += std::accumulate(werte, werte + 6, 0);
  }

  bench[4] = std::clock();

  std::cout << sum << '\n'
            << "std::set:  " << double(bench[1] - bench[0]) / CLOCKS_PER_SEC << '\n'
            << "ipsec:     " << double(bench[2] - bench[1]) / CLOCKS_PER_SEC << '\n'
            << "TE:        " << double(bench[3] - bench[2]) / CLOCKS_PER_SEC << '\n'
            << "bool-Feld: " << double(bench[4] - bench[3]) / CLOCKS_PER_SEC << '\n';
}

Ergebnis mit gcc 4.6.1 und -O3:

6000173451
std::set:  7.08
ipsec:     0.96
TE:        1.13
bool-Feld: 1.11

Bei niedrigeren Optimierungsstufen ist das Ergebnis weniger günstig für ipsec. Ich vermute, dass der gcc hier die komplette Schleife ausklappt, weil die Zahl der Durchläufe zur Compilezeit bekannt ist - im Gegensatz zu den anderen Ansätzen.

SeppJ

Mitleid schrieb:

SeppJ schrieb:

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Die Annahme, dass rand() sich standardkonform verhält reicht.

Ganz sicher nicht. Laut Standard liefert rand() einfach nur Pseudozufallszahlen zwischen 0 und RAND_MAX. Streng genommen ist noch nicht einmal die Verteilung vorgegeben, aber selbst wenn man von Gleichverteilung ausgeht reicht das nicht. Eher im Gegenteil. Damit der Algorithmus terminiert, müsste garantiert sein, dass in endlicher Zeit mehr als 5 verschiedene Zahlen gezogen werden. Das wäre der Qualität der Zufallszahlen abträglich.

seldon schrieb:

Bei niedrigeren Optimierungsstufen ist das Ergebnis weniger günstig für ipsec. Ich vermute, dass der gcc hier die komplette Schleife ausklappt, weil die Zahl der Durchläufe zur Compilezeit bekannt ist - im Gegensatz zu den anderen Ansätzen.

Das ist ja auch sein volles Recht, das so zu machen. Letztendlich interessiert doch nur die volloptimierte Variante. Danke für den Test. Das bool-Feld und ipsec würde ich nach mehreren Durchläufen bei mir, die deine Ergebnisse auch mit anderen Compilern bestätigen, als gleich ansehen. Beide dicht gefolgt vom TE.

volkard

int werte[6];
		for(int j = 0; j < 6; ++j) {
nochmal:
			int z = std::rand() % 49 + 1;
			for(int k = 0; k < j; ++k)
				if(werte[k] == z) {
					goto nochmal;
				}
			werte[j]=z;
		}

std::set:  3.94
ipsec:     0.83
TE:        0.73
bool-Feld: 0.75
goto:      0.7

Mitleid

SeppJ schrieb:

Mitleid schrieb:

SeppJ schrieb:

Mitleid schrieb:

Ich denke man kann aufgrund der Implementierung von rand() zeigen, dass der Algorithmus auf jeden Fall terminiert.

Und die wäre?

Die Annahme, dass rand() sich standardkonform verhält reicht.

Ganz sicher nicht. Laut Standard liefert rand() einfach nur Pseudozufallszahlen zwischen 0 und RAND_MAX. Streng genommen ist noch nicht einmal die Verteilung vorgegeben, aber selbst wenn man von Gleichverteilung ausgeht reicht das nicht. Eher im Gegenteil. Damit der Algorithmus terminiert, müsste garantiert sein, dass in endlicher Zeit mehr als 5 verschiedene Zahlen gezogen werden. Das wäre der Qualität der Zufallszahlen abträglich.

Der Standard garantiert dir, dass für einen bestimmten, mit srand() angenommenen Startwert die Folge der mit rand() erzeugten Pseudozufallszahlen identisch ist. Somit wird das ein endliches Problem, welches sich für jeden Fall wunderbar durchprobieren lässt. Der Beweis der Terminierung kann also stets locker erbracht werden.

SeppJ

Das ist doch Unsinn! Das hat mit der Standardkonformität der Implementierung überhaupt gar nichts zu tun! Du probierst für jede Implementierung einfach nur aus, ob der Algorithmus terminiert. Aber weder garantiert dir der Standard an sich, dass der Algorithmus durch die vorgegebenen Eigenschaften von rand() immer terminiert, noch kennst du die Implementierung und musst für jede davon den Algorithmus erneut testen. Super Beweis!

Und schönerweise hast du damit sogar schon gezeigt, wie der Gegenbeweis läuft: Ich muss nur einen einzigen Startwert finden, der in einer Endlosschleife endet. Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren? Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

volkard

SeppJ schrieb:

Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren?

Ich würde darauf wetten. Das heißt, ich würde den Algo des Threaderstellers ohne Schmerzen in Produktivcode verwenden.

Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

Ja, deswegen kann der Standard hier nichts garantieren.

SeppJ

volkard schrieb:

SeppJ schrieb:

Es gibt sehr viele Startwerte und sehr viele Implementierungen von rand(). Willst du wirklich da drauf wetten, dass die wirklich alle für alle Startwerte terminieren?

Ich würde darauf wetten. Das heißt, ich würde den Algo des Threaderstellers ohne Schmerzen in Produktivcode verwenden.

Ok, bei 6 aus 49 stehen die Chancen noch recht gut . Aber wie wäre es mit 32000 aus 32767?

edit: Beziehungsweise da würdest du sicherlich ipsecs Algorithmus nehmen, wegen der Laufzeit.

Ach, immer diese pragmatischen Lösungen. Da kann man nie mal richtig schön theoretisieren.

Dobi

SeppJ schrieb:

Aber wie wäre es mit 32000 aus 32767?

Also ich würd in dem Fall lieber die 767 Zahlen, die nicht vorkommen, ziehen.

Mitleid

SeppJ schrieb:

Das ist doch Unsinn! Das hat mit der Standardkonformität der Implementierung überhaupt gar nichts zu tun! Du probierst für jede Implementierung einfach nur aus, ob der Algorithmus terminiert. Aber weder garantiert dir der Standard an sich, dass der Algorithmus durch die vorgegebenen Eigenschaften von rand() immer terminiert, noch kennst du die Implementierung und musst für jede davon den Algorithmus erneut testen. Super Beweis!

Hm, ich weiß nicht, was es da zu lamentieren gibt. Der Standard GARANTIERT, dass da niemals ein echter Zufalls ins Spiel kommen kann. Mehr braucht man nicht.

SeppJ schrieb:

...Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

Da dein "geschwächtes" rand() die Werte ebenfalls reproduzierbar berechnen MUSS um standardkonform zu sein, hast du an der Stelle aber nichts gewonnen.

Man muss auch nicht wetten. Wenn UINT_MAX eine akzeptable Größe hat lässt man das durchprobieren und hat den wasserdichten Beweis, dass das Programm hält. Wenn nicht sieht man sich halt rand() genauer an und fährt einen formalen Beweis. Wo ist das Problem?

SeppJ

Mitleid schrieb:

SeppJ schrieb:

...Zur Not kann ich mir sogar mein eigenes, standardkonformes rand() schreiben, welches mit Absicht eine Implementierungsschwäche enthält.

Da dein "geschwächtes" rand() die Werte ebenfalls reproduzierbar berechnen MUSS um standardkonform zu sein, hast du an der Stelle aber nichts gewonnen.

uint32_t interner_zustand = 1;
bool nimm_dumme_werte;

void my_srand(uint32_t seed)
{
 interner_zustand=seed;
 if (seed == 123456789) 
  nimm_dumme_werte = true;
}

uint32_t my_rand()
{
 if (!nimm_dumme_werte) 
  return interner_zustand = 1664525*interner_zustand + 1013904223;
 return (interner_zustand = 1664525*interner_zustand + 1013904223) % 5;
}

Sollte standardkonform sein. Wenn du etwas findest, was dagegen spricht, bessere ich gerne nach. Leider hat mein Zufallsgenerator ein ganz ungünstiges Verhalten, wenn der seed 123456789 war . Tja, solche Dinge passieren eben.

edit: Ups, laut Standard muss der Generator ohne srand so laufen, als hätte man srand(1) gemacht.
@volkard unter mir (falls du dies noch liest, was ich nicht annehme ), bei dir muss das auch noch geändert werden. Übrigens viel schöner als mein doch sehr konstruierter Generator . Ich hatte mit dem Gedanken gespielt einen LCG mit ungünstigem Multiplikator zu nehmen (Zweierpotenzen sollten sehr kurze Periode haben), aber das war mir zu viel Arbeit.

volkard

Und hier ist's doch glatt aus Versehen passiert.

uint64_t interner_zustand=4711;

void my_srand(uint64_t seed)
{
   interner_zustand=seed;
}

uint32_t my_rand()
{
   interner_zustand=1967773755*(interner_zustand&0xffffffff)+(interner_zustand>>32);
   return x;
}

Das Biest liefert normalerweise sehr hübschen Zufall, bestehtz auch die die-hard-Tests. Außer, man ruft my_srand(0) auf. Dann ist es tot.