der programmierte Zufall

[Gast]

Hallo,

vor einiger Zeit brauchte ich eine Zufallszahl von 1 bis 23. Kurz überlegt, was in der Küche so zur Verfügung steht. Münzen werfen? Würfel? Zahnstocher?

Ich entschied mich für zwei Würfel, deren Augen ich multiplizierte. Da ist dann der Zahlenraum von 1*1 bis 6*6 abgedeckt. Falls ein Ergebnis größer würde als 23, würfele ich halt noch mal.

So habe ich es gemacht, einen kleinen Gewinn verschickt. Aber irgendwie war da ein Bauchgefühl, das mir sagte, da stimmt was nicht. Und tatsächlich - die Primzahlen kann man per Multiplikation nicht darstellen. Und auch die 14, woher sollte die benötigte 7 für 2*7 herkommen?

Also ein Gedankenfehler. Wieviel Zahlen kann man per Multiplikation mit zwei Würfeln darstellen? Ich weiss es nicht auf Anhieb.

Kann es nun sein, dass auch hochstudierte Programmierer, die Betriebssysteme, Datenbanken und Programmiersprachen machen, nicht recht durchblicken? Ich hatte das Problem ja schon mal am 16.02. beschrieben, den Rat befolgt, bei MySQL SQL_NO_CACHE hinzugefügt und nicht für ausreichend empfunden. Dann alle Datensätze selektiert und per PHP ausgewählt:
mysql_data_seek( $res, rand( 0, mysql_num_rows($res)));
Es gibt immer noch "Häufungen" und "Löcher", wobei mir scheint, dass die ersten (älteren) Datensätze bevorzugt werden.

Gruß, Gast

[Encoder]

Wieviel Zahlen kann man per Multiplikation mit zwei Würfeln darstellen?

36
Dabei ists Unsinn die Zahlen zu multiplizieren. 6*2 = 2*6 = 4*3 = 3*4 usw...

6 * erster Würfel + zweiter Würfel
das gibt dir alle Zahlen zwischen 7 und 42 gleich wahrscheinlich.
6 * (erster - 1) + zweiter ergibt 1 bis 36

[Gunnar Bittersmann]

@@Encoder:

nuqneH

6 * erster Würfel + zweiter Würfel

Wobei die Unterscheidung zwischen erster und zweiter Würfel bedeutend ist.

Also entweder würfelt man nacheinander (dann braucht man nur einen Würfel) oder man hat einen roten und einen blauen Würfel* und rechnet

6 * roter Würfel + blauer Würfel

Qapla'

* andere Unterscheidungsmerkmale sind denkbar

[Steel]

Hi!

Naja. dass 6x6 36 ist, darauf komm ja sogar ich grad noch so. ;)

Und falls dich die Zufallsfunktion einer Sprache nicht zufrieden stellt, dann programmier ne Statisitk. Nimm z.B. einen sechsseitigen Wuerfel. 'Wuerfle" den so 10.000 Mal und wenn da dann deutliche Luecken sind, machste das ein paar mal. (gern eine woche lang jeden Tag einige male) Wenn Du dann immer noch die gleichen Luecken hast, pruefe deinen Code oder lass ihn pruefen und dir zeigen was daran defekt ist, und mach das ganze nochmal. Sollte das jetzt wirklich immer wieder die gleichen Luecken geben hast Du eine Sprache  mit sclechter Randomfunktion.

Dir wurde allerding auch schon gesagt, dass es gar nicht moeglich ist, so echte Zufallszahlen zu generieren.

[Gast]

Dir wurde allerding auch schon gesagt, dass es gar nicht moeglich ist, so echte Zufallszahlen zu generieren.

Tja, ich denke jetzt darüber nach, die Datensätze einfach knallhart nacheinander zu zeigen. Der erste Besucher bekommt Satz 1, der nächste Satz 2 und so weiter. Dann bekommt jeder "scheinbar" einen zufälligen Datensatz und die Verteilung ist gerecht(er).

Muss mir natürlich irgendwo die letzte Nummer merken. In einer Textdatei?

[Gast]

Habe nochmal nachgedacht über das Werfen von Münzen. Eine digitale Lösung, mit vier Münzen könnte ich 0000 bis 1111, also 0 bis 15 darstellen. Wären die 16 Werte wirklich gleichmäßig zufällig?

Wenn ja, kann man die Zahl der Münzen beliebig erhöhen.

Umgesetzt auf die Programmierung:

Ich lasse jeden Besucher eine "Münze" werfen. Etwa indem ich die 0 als eine gerade Sekundenzahl aus time(), die 1 als ungerade betrachte.

Nun baue ich eine digitale Zahl auf, jeder Besucher schiebt seine 1 oder 0 rechts rein. Das heisst aus bisher 011101 wird jetzt 0111010. Und diese digitale Zahl nehme ich, um einen zufälligen Datensatz zu bestimmen.

Ist das zufällig, oder habe ich was übersehen?

Gruß, Gast

[Matti Mäkitalo]

Hi,

Habe nochmal nachgedacht über das Werfen von Münzen. Eine digitale Lösung, mit vier Münzen könnte ich 0000 bis 1111, also 0 bis 15 darstellen. Wären die 16 Werte wirklich gleichmäßig zufällig?
Wenn ja, kann man die Zahl der Münzen beliebig erhöhen.

Ja, das sollte gleichverteilt sein. Weil jede einzelne Stelle zu 50% Wahrscheinlichkeit 0 oder 1 ist. Es gibt "benachbarte" Zahlen (es unterscheidet sich nur ein Bit) und diese sind dann jeweils gleich wahrscheinlich (da mit 3 festen Bits nur die 50% Wahrscheinlichkeit des letzten Bits den Ausschlag gibt). Über eine Kette von benachbarten Zahlen kannst du alle von 1 bis 16 erreichen, so dass als Folgerung alle gleichverteilt sein müssen.

Encoder meint btw. das gleiche, auch wenn es anders aussieht: mit einem (sechsseitigen) Würfel statt einer Münze bekommst du ein Stellenwertsystem mit der Basis 6 (statt 2) und kannst 36 Zahlen darstellen. Darfst nur nicht vergessen, von den Würfelzahlen 1 abzuziehen, da die Ziffern zwischen 0 und 5 sein soll.

Gruß, Gast

Bis die Tage,
Matti

[Cheatah]

Hi,

Nun baue ich eine digitale Zahl auf, jeder Besucher schiebt seine 1 oder 0 rechts rein. Das heisst aus bisher 011101 wird jetzt 0111010. Und diese digitale Zahl nehme ich, um einen zufälligen Datensatz zu bestimmen.

Ist das zufällig, oder habe ich was übersehen?

Du wirst bei einer gut besuchten Seite eine Häufung der folgenden Werte feststellen:

000000
000001
000011
000111
001111
011111
111111
111110
111100
111000
110000
100000

Je nachdem, _wie_ gut die Seite besucht ist, wird es bereits selten sein, etwas anderes als "000000" oder "111111" zu erhalten.

Cheatah

[Gast]

Hallo,

Je nachdem, _wie_ gut die Seite besucht ist, wird es bereits selten sein, etwas anderes als "000000" oder "111111" zu erhalten.

Du meinst, weil mehrere Besucher pro Sekunde zugreifen? Daran hatte ich nicht gedacht.

Dann macht es Sinn, microtime() zu verwenden?

Gast

[Cheatah]

Hi,

Dann macht es Sinn, microtime() zu verwenden?

nein. Auch diese Größe ist vorhersehbar (die gelieferten Millisekunden wachsen pro Sekunde um 1000) und damit für den Zufall extremstst[1] ungeeignet.

Warum benutzt Du nicht einfach Zufallsfunktionen, wenn Du etwas zufälliges erhalten willst? In dem Moment, wo die vorliegenden Funktionen nicht mehr genügen, bekommst Du programmatisch (also ohne spezielle Hardware) ohnehin nichts besseres hin.

Cheatah

[1] Und noch ein paar "st" hinten dran.

[ChrisB]

Hi,

Ich lasse jeden Besucher eine "Münze" werfen. Etwa indem ich die 0 als eine gerade Sekundenzahl aus time(), die 1 als ungerade betrachte.

Dann würde ich eher noch den Unix Timestamp modulo (Maxwert - 1) nehmen ...

MfG ChrisB

[Encoder]

Mal was praxisnäheres.
Um wie viele Zufallswerte geht es ungefähr?
Du könntest zum Beispiel auch die aktuelle Zeit nehmen und aus der eine Zufallszahl ableiten. Dann ist der Besucher der Zufallsgenerator, bzw. der Zeitpunkt zu dem er die Webseite abruft (es geht doch um eine?).
Die Jahreszahl dürfte da nicht unbedingt für aufregende Abwechslung sorgen, die Millisekunden schon eher.

Dann ist aner immer noch nicht alles gleichverteilt. Beispiel: mit 300 Datensätzen, 1000 ms und einer einfachen Funktion
datensatznr = ms % 300
werden die ersten 100 Datensätze öfter gezogen. Das könntest du umgehen indem du die gesamten Millisekunden der Uhr (also seit 1.1.1900 oder was die eben hergibt) verwendest.
Auch dann ist nicht 100% Gleichverteilung gegeben, aber der Fehler rechnet sich immer mehr raus und ist vielleicht doch irgendwann tolerierbar.

[Gast]

Hallo, Encoder,

Um wie viele Zufallswerte geht es ungefähr?

Zur Zeit knapp unter 100.

Das könntest du umgehen indem du die gesamten Millisekunden der Uhr (also seit 1.1.1900 oder was die eben hergibt) verwendest.

Wenn ich mal davon ausgehe, dass Zugriffe im Bereich der Tausendstelsekunden gleichverteilt sind (also 0, 233, 877, 999 kommen ebensooft vor wie 1, 578 usw), müsste doch folgende Überlegung gelten:
Das, was die Mikrosekunden in Prozent zu 999 sind, müsste die Satznummer in Prozent zu der Satzanzahl sein:

  
if ( mysql_num_rows($res) ) // null abfangen  
{  
  list($usec, $sec) = explode(" ", microtime()); // $usec = 0 .. 999  
  $mikro_pro = $usec /999 *100; // 999 = 100%  
  $satz_nr   = round(mysql_num_rows($res) *$mikro_pro /100);  
}

Beispiel: 66 Sätze
$usec $mikro_pro  $satz_nr
----- ----------  --------
000   000.00       00
025   002.50       01
500   050.05       33
999   100.00       66

Einverstanden?

Gruß, Gast

[Gast]

if ( mysql_num_rows($res) ) // null abfangen
{
  list($usec, $sec) = explode(" ", microtime()); // $usec = 0 .. 999
  $mikro_pro = $usec /999 *100; // 999 = 100%
  $satz_nr   = round(mysql_num_rows($res) *$mikro_pro /100);
}[/code]

Funzt nicht wie erwartet. $usec hat sowas wie 0.74164200

Die Beschreibung zu microtime() lautet:

"Standardmäßig gibt microtime() einen string im Format "Mikrosekunden Sekunden" zurück, wobei Sekunden die aktuelle Zeit gemessen in Sekunden seit Beginn der Unix Epoche (01. Januar 1970 00:00:00 GMT) ist und Mikrosekunden die Anzahl an Mikrosekunden ist, die seit Sekunden vergangen sind."

Ja, ich weiss, Programmieren ist wenig Logik und viel Probieren. Also probiere ich und multipliziere die Mikrosekunden mit Tausend, um Mikrosekunen zu bekommen.

[Gast]

So, nun habe ich eine Lösung, die erstmal gut aussieht:

  list($usec, $sec) = explode(" ", microtime()); // $usec = 0 .. 999  
  $video_nr  = round((mysql_num_rows($res_video)-1) *$usec); // $usec*1000 /999  
  mysql_data_seek( $res_video, $video_nr );  
  $q2 .= "usec=[".$usec."] Video [".$video_nr."] von [".mysql_num_rows($res_video)."]\n";  
  $row = mysql_fetch_array( $res_video );  

$q2 zeigt sowas wie
usec=[0.70144700] Satz [51] von [73]
usec=[0.22541200] Satz [16] von [73]

Mal sehen, ob mir in den nächsten Tagen Häufungen oder Löcher auffallen.

Danke an euch und Gruß, Gast

[Vinzenz Mai]

Hallo,

[code lang=php]  list($usec, $sec) = explode(" ", microtime()); // $usec = 0 .. 999

... warum nutzt Du nicht mt_rand()?

Freundliche Grüße

Vinzenz

[Gast]

Hallo, Vinzenz,

... warum nutzt Du nicht mt_rand()?

Weil ... da war doch was ... unter rand():
"Hinweis: Seit PHP 4.2.0 besteht keine Notwendigkeit mehr, den Zufallsgenerator für Zahlen mit srand() oder mt_srand() zu füttern, das geschieht nun automatisch."

Hatte ich wohl in den falschen Hals bekommen und verstanden, dass mt_rand() nicht mehr nötig ist.

Gruß, Gast

[Gast]

... und dann habe ich den vorgegebenen Funktionen nicht mehr vertraut, nachdem ORDER BY RAND() und rand() so versagten.

Über die Qualität von mt_rand() wird eigentlich nichts verraten, nur dass es schneller ist. Ich suche aber nicht das schnelle Problem, sondern eine Problemlösung.

[Vinzenz Mai]

Hallo,

... und dann habe ich den vorgegebenen Funktionen nicht mehr vertraut, nachdem ORDER BY RAND() und rand() so versagten.

PHPs rand() hat doch mit MySQLs RAND() überhaupt nichts zu tun!
und mt_rand() sowieso nicht.

Freundliche Grüße

Vinzenz

[Gast]

PHPs rand() hat doch mit MySQLs RAND() überhaupt nichts zu tun!
und mt_rand() sowieso nicht.

Mag sein, Schornsteinfeger und Ferkel haben auch nichts miteinander zu tun. Gemeinsam ist ihnen, dass sie mein Problem nicht lösen konnten. MySQLs RAND() bezog sich auf die Verlinkung zu meinem alten Faden, damit begann es.

Gruß, Gast

[Vinzenz Mai]

Hallo,

PHPs rand() hat doch mit MySQLs RAND() überhaupt nichts zu tun!
und mt_rand() sowieso nicht.

Mag sein, Schornsteinfeger und Ferkel haben auch nichts miteinander zu tun. Gemeinsam ist ihnen, dass sie mein Problem nicht lösen konnten. MySQLs RAND() bezog sich auf die Verlinkung zu meinem alten Faden, damit begann es.

ich kenne Deinen alten Thread, auch wenn ich mich selbst nicht daran beteiligt habe :-)

Schau' Dir doch einfach mit folgendem Skript die Verteilung der Zufallszahlen an:

  
<?php  
    header("Content-Type: text/plain");  
  
    $start = 0;          // kleinste Zufallszahl  
    $ende  = 50;         // größte Zufallszahl plus 1 :-)  
    $anzahl = 100000;    // Wie oft "würfeln" wir.  
                         // Sollte sehr viel größer als die Anzahl der  
                         // unterschiedlichen Werte sein  
  
    // initialisiere das Array für die Statistik  
    $results = array();  
    for($i = $start; $i < $ende; $i++) {  
        $results[$i] = 0;  
    }  
  
    for($i = 0; $i < $anzahl; $i++) {  
        // wir wollen die obere Grenze nicht mitnehmen.  
        $zufall = mt_rand($start, $ende - 1);  
        $results[$zufall]++;  
    }  
  
    // Ausgabe der Statistik  
    foreach ($results as $key => $value) {  
        echo $key, " kommt ", $value, "-mal vor.\n";  
    }  
?>

Ich finde die Verteilung annehmbar ausgeglichen, ganz besonders wenn man mít verschiedenen Werten für $anzahl experimentiert.

Und nun kannst Du ganz einfach wie folgt vorgehen:

a) Ermittle die Anzahl der Datensätze, die Deine Abfrage zurückliefern würde,
   z.B. mit
   SELECT SQL_CALC_FOUND_ROWS <Rest Deiner Abfrage> und anschließendem
   SELECT [link:http://dev.mysql.com/doc/refman/5.5/en/information-functions.html#function_found-rows@title=FOUND_ROWS()]

b) Ermittle nun mit PHP Deine Zufallszahl zwischen 0 und der Anzahl der
   Datensätze (ausschließlich der oberen Grenze)

c) Frage nun den gewünschten Zufallsdatensatz mit
     SELECT <Rest Deiner Abfrage> LIMIT <zufallszahl>, 1
   ab.

Du bekommst die Güte der Gleich- und Zufallsverteilung der PHP-Funktion, sparst Deinem DBMS das völlig überflüssige Sortieren der Ergebnismenge und fragst trotz alledem nur einen einzigen Datensatz ab.

Einen eigenen Zufallszahlengenerator zu schreiben, lohnt in aller Regel nicht (ja ja, hab' ich auch schon gemacht ... in Pascal auf 'nem Mainframe unter BS2000 - lange vor BS2000/OSD ...)

Freundliche Grüße

Vinzenz

[Gast]

Hallo, Vinzenz,

danke für deine Mühe und das Aufzeigen, wie man die DB-Abfrage beschleunigen kann.

[suit]

... und dann habe ich den vorgegebenen Funktionen nicht mehr vertraut, nachdem ORDER BY RAND() und rand() so versagten.

Über die Qualität von mt_rand() wird eigentlich nichts verraten, nur dass es schneller ist.

So ein Unsinn - das hatten wir grade in deinem anderen Thread. Da hab' ich mich extra bemüht, im PHP-Core die entsprechenden Stellen rausgesucht - es liegt auf der Hand dass mt_rand() bessere Zufallszahlen erzeugt (weil z.B. die Zeit und die Prozess-ID eingezogen wird): ob mt_rand() schneller ist, kann ich nicht sagen - ich würde aber eher sagen, dass das nicht so ist, weil die Funktion etwas komplizierter ist - aber das dürfte unter die Signifikanzschwelle fallen.

[Vinzenz Mai]

Hallo,

... warum nutzt Du nicht mt_rand()?

"Hinweis: Seit PHP 4.2.0 besteht keine Notwendigkeit mehr, den Zufallsgenerator für Zahlen mit srand() oder mt_srand() zu füttern, das geschieht nun automatisch."

Hatte ich wohl in den falschen Hals bekommen und verstanden, dass mt_rand() nicht mehr nötig ist.

offensichtlich: mt_rand() liefert immer noch bessere Zufallszahlen als rand(). Nur müssen beide Zufallszahlengeneratoren nicht mehr initialisiert werden (außer man benötigt dies in ganz speziellen Fällen).

Freundliche Grüße

Vinzenz

[dedlfix]

Tach!

Wieviel Zahlen kann man per Multiplikation mit zwei Würfeln darstellen?

6 Zahlen ^ 2 Würfel = 36 ist nicht die Lösung, denn es sind nur 18 Zahlen, davon einige doppelt, dreifach und vierfach.

Kann es nun sein, dass auch hochstudierte Programmierer, die Betriebssysteme, Datenbanken und Programmiersprachen machen, nicht recht durchblicken? [...] Es gibt immer noch "Häufungen" und "Löcher", wobei mir scheint, dass die ersten (älteren) Datensätze bevorzugt werden.

Beim Zufall ist eine Gleichverteilung nicht zwingend inbegriffen.

dedlfix.

[suit]

Nochmal zusammenfassend:
a) das ist ein Doppelposting :)

b) Wenn du Zufallszahlen verwenden willst, die möglichst zufällig (aber nicht eindeutig) sind, ist mt_rand() unter php die beste Wahl.

Wenn es nicht Sicherheitsrelevant sein muss, kannst du auch irrationale Zahlen ohne Perioden verwenden. Die eulersche Zahl, Pi oder Wurzel 2 eigenen sich z.B. - die Zufallswerte sind hierzwar vorhersehbar - aber du kannst die Zahl einfach in ein Stellwertsystem deiner Wahl konvertieren und durchlaufen (wenn du z.B. Zahlen von 3 bis 15 brauchst, du eins zur Bbasis 13) - sprich bei jeden Request schiebst du den Zeiger um eins weiter.

c) Wenn du auf Gleichverteilung angewiesen bist, helfen dir herkömmliche Zufallszahlengeneratoren nicht weiter - das ist, wie dir schon gesagt wurde - nicht die Aufgabe solcher Generatoren. Nach dem Gesetz der großen Zahlen wirst du das zwar vermutlich erreichen, garantiert ist das aber nicht.

Du musst, wenn es Anforderung ist (z.B. wenn du zufällig Personen in gleich große Gruppen aufteilst - Auto Team Balance in Spielen ist z.B. ein gängiger Anwendungsfall dafür - oder aber Bannerrotationsscripte, bei denen jeder Banner ein entsprechendes Kontingent besitzt), über deine Zufallszahlen Buch führen. Sprich du musst die letzten Ergebnisse in einer Liste erfassen wenn alle Werte da waren, die Liste wegschmeissen und neu beginnen.

So wie ich das sehe ist es in deinem Fall aber weder sicherheitsrelevant noch ist Gleichverteilung essentiell wichtig.