3. Ungewollte Größen bei Ausgabe von Zufallszahlen

Ungewollte Größen bei Ausgabe von Zufallszahlen

  • ?

    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.

    0
  • Mod

    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.

    0
  • V
     

    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
    0
  • M

    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.

    0
  • Mod

    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.

    0
  • V

    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.

    0
  • Mod

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

    0
  • D

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

    0
  • M

    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?

    0
  • Mod

    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.

    0
  • V

    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.

    0

  • SeppJ schrieb:

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

    Dann zieht man halt einfach die 767 aus 32767 die man nicht braucht. EDIT: oops, wurde ja schon erwähnt, überlesen /EDIT

    BTW: bei der "vector + rausnehmen" Variante muss man ja mit wechselndem Modulo-Wert arbeiten. Kann das nicht - je nach Generator - die "Qualität der Gleichverteilung" beeinflussen?

    0
  • V

    hustbaer schrieb:

    Kann das nicht - je nach Generator - die "Qualität der Gleichverteilung" beeinflussen?

    http://en.wikipedia.org/wiki/Fisher–Yates_shuffle#Modulo_bias

    0
  • Mod

    hustbaer schrieb:

    BTW: bei der "vector + rausnehmen" Variante muss man ja mit wechselndem Modulo-Wert arbeiten. Kann das nicht - je nach Generator - die "Qualität der Gleichverteilung" beeinflussen?

    Wenn du auf solche Kleinigkeiten guckst, dann hast du das gleiche Problem aber auch bei der naiven Methode, da 49 keine Zweierpotenz ist. Oder verstehe ich gerade nicht wo drauf du hinaus willst? Du meinst doch, dass man RAND_MAX verschiedene Zahlen nicht gleichmäßig auf 49, 48, 37 usw. Container verteilen kann, oder? Falls ja, wieso sollte das was ausmachen, wenn die Containerzahl sich ändert? Das wird doch sogar tendenziell eher besser, weil jedes Mal andere Container den Vorteil abbekommen.

    0

  • Ne, den Teil dass 2^blubb nicht durch 49 teilbar ist meine ich gar nicht. Das lässt sich ja wie in dem Artikel beschrieben relativ easy fixen, indem man halt Zahlen die >= N * floor(2^blubb / N) sind verwirft.

    Trotzdem arbeitet man nicht mit einem fixen Modulo-Wert.

    Angenommen ein Generator macht mit Modulo 100 schön gleichverteilte Werte. Und auch mit Modulo 99 und Modulo 98 uswusf.
    Also quasi die Folge rgn(100), rgn(100), rgn(100), rgn(100), rgn(100), rgn(100), ... hat ne schöne Verteilung, die Folge rgn(99), rgn(99), rgn(99), rgn(99), rgn(99), rgn(99), ... ebenso etc.

    Das heisst aber doch noch lange nicht, dass auch die Folge rgn(100), rgn(99), rgn(98), rgn(97), rgn(96), rgn(95), ... "schön" verteilt ist. Oder doch?
    (Der Begriff "gleichverteilt" ist hier ja vermutlich nicht mehr anwendbar, aber ich denke ihr wisst was ich mit "schön" meine)

    Ich weiss bloss nicht, ob es Generatoren gibt die einerseits "gut genug" sind um überhaupt ne brauchbare Gleichverteilung zu liefern und "Modulo safe" sind, andereseits aber "schlecht genug" sind um mit wechselndem Modulo Probleme zu machen.

    BTW: das primäre Problem mit Modulo in Verbindung mit rand() ist wohl, dass rand() so oft als LCG implementiert ist, und daher die untersten paar Bits des Ergebnisses total für die Tonne sind wenn man einfach Modulo rechnet. Wurde aber sicher schon erwähnt.

    0

  • SeppJ schrieb:

    Das wird doch sogar tendenziell eher besser, weil jedes Mal andere Container den Vorteil abbekommen.

    Nö, den Vorteil haben immer die ersten. Wechseln tut bloss wie viele und wie stark. Der letzte hat aber immer die Arschkarte (ausgenommen die paar Durchläufe wo N grad ne Zweierpotenz ist).

    0
  • M

    @Sepp & Volkard

    Dass Funktionen rand() konstruierbar sind für die das Programm nicht hält, ändert nichts an der Beweisbarkeit der Terminierung. Worauf wollt ihr hinaus?

    0
  • V

    Mitleid schrieb:

    @Sepp & Volkard
    Dass Funktionen rand() konstruierbar sind für die das Programm nicht hält, ändert nichts an der Beweisbarkeit der Terminierung. Worauf wollt ihr hinaus?

    Daß die Aussage, der Standard garantiere eine Terminierung einfach falsch ist.

    0
  • M

    volkard schrieb:

    Daß die Aussage, der Standard garantiere eine Terminierung einfach falsch ist.

    Schön. Nur hat niemand diese Aussage ausgesagt.

    0
  • V

    Mitleid schrieb:

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

    0
Anmelden zum Antworten