Random(2) in schnell

[alzaimar]

Das riecht einfach nach stinknormaler gaußscher Normalverteilung.

Aber die Frage ('Wie viele Versuche braucht man ...') ist schon falsch gestellt. Denn die Antwort kann man so geben: "Wenn man Glück hat, reichen 15 Versuche, hat man Pech, passiert es nie". Das ist das Wesen des Zufalls.

Die korrekte Frage würde lauten: "Wie viele Versuche braucht man im Mittel, damit das Zielereginis mit einer 90%igen Wahrscheinlichkeit auftritt?". Da es sich um eine Gaußsche Glockenkurve handelt (meine Annahme), muß man 'nur' ausrechnen(!), bei welchem X die Fläche unter der Kurve 90 ergibt.
Oder so ähnlich.

Mathematiker vor! (Ich krieg komischerweise immer Denk- und Schreibstörungen , wenn eine Volltextrecherche in einem Umkreis von 15km 70%ige Treffer bei der Suche nach dem Wort 'Wahrscheinlichkeit' ergibt )

[Nikolas]

Das Ganze müsste eher eine Binomialverteilung sein. Das Problem ist aber, dass du hier nicht in beide Richtungen laufen darfst und das nach dem ersten erreichen des letzen Feldes abgebrochen wird. Diese beiden Einschränkungen machen alles etwas schwieriger :)

[Hawkeye219]

Hallo,

hier noch ein Ansatz zur Beschleunigung der Simulation: loop unrolling. Bei dieser Technik werden mehrere Schleifendurchläufe ausprogrammiert, was im aktuellen Fall die Verwaltung des zusätzlichen Bitzählers erspart. Weiterhin sollte die Anzahl der Sprungbefehle auf ein Minimum reduziert werden:

Delphi-Quellcode:

var
  [...]
  y : Byte;
begin
[...]
  Akt := Config.Start;
  if (Akt <> Config.Ziel) then
  repeat
    R := Random($10000);

    y := Ord(Odd(r));
    Inc (Akt, y - Ord(Akt > 3) shr y);
    Inc (C);  if (Akt = Config.Ziel) THEN Break;

    y := Ord(Odd(r shr 1));
    Inc (Akt, y - Ord(Akt > 3) shr y);
    Inc (C);  if (Akt = Config.Ziel) THEN Break;

    y := Ord(Odd(r shr 2));
    Inc (Akt, y - Ord(Akt > 3) shr y);
    Inc (C);  if (Akt = Config.Ziel) THEN Break;

    [...]

    y := Ord(Odd(r shr 14));
    Inc (Akt, y - Ord(Akt > 3) shr y);
    Inc (C);  if (Akt = Config.Ziel) THEN Break;

    y := Ord(Odd(r shr 15));
    Inc (Akt, y - Ord(Akt > 3) shr y);
    Inc (C);  if (Akt = Config.Ziel) THEN Break;
  until False; 
  [...]
end;

Eine solche Optimierung verbessert zwar die Laufzeit, nicht aber die Lesbarkeit des Quelltextes...

Gruß Hawkeye

[DGL-luke]

Jop, da fragt man die Stochastiker

Man kann das ganze als Bernoulli-Kette der Länge x sehen und dann die wahrscheinlcihkeit dafür ausrechnen, dass man mit diesen x Versuchen 15 Treffer landet.

Das wäre dann B(x;0,5;15) = (15 über x)0,5^x*0,5^(15-x) hmm... das lässt sich vereinfachen... (15 über x)0,5^(x+15-x) = (15 über x)0,5^15 wenn ich mich nicht irre. meine tabelle enthält leider nix für p=0,5.

[Nikolas]

Das klappt so leider nicht. Wenn du einmal daneben liegst, brauchst du zwei Treffer mehr, da deine Stufe nach unten gesetzt wird. Mit 15 Treffern landest du nicht auf Stufe 15, sondern sonstwo (z.B. auf der Null, wenn du immer abwechselnd triffst).
Auch fehlt bei dem Ansatz die Einschränkung, dass du nicht ins negative gehen darfst. Ich habe schon einen Ansatz (siehe ein paar Posts oben), habe nur keine Zeit, das mal auszurechnen.

[glkgereon]

Ich muss ehrlich zugeben dass ich diesen Ansatz nicht verstehe...

Mein Ziel ist es im Prinzip ganz am Ende eine Liste zuhaben:
Anzahl Stein: Wahrscheinlichkeit

Die Durchschnittliche Anzahl ist mehr ein Nebenprodukt was man direkt noch mit ausrechnen kann

[Edit]
Zur Verteilung... Die sieht so aus wie im Anhang (X = so oft vorgekommen, Y = Anzahl der Steine).

[grenzgaenger]

hallo greedy,

ich hab zwar immer noch keinen plan davon, was du auswerten willst, hätt aber 'ne kleine änderung im quellcode vorzuschlagen..

Delphi-Quellcode:

TUpper = class
// ...
  FRes64: array of cardinal; //<<-- reicht doch aus, und kann der rechner besser verarbeiten
end;

procedure TUpper.Generate(Cnt: Int64);
var Akt, Rnd: Byte;
    C, Len: cardinal; //<<-- reicht doch aus, und kann der rechner besser verarbeiten
    R: Integer;
begin
  Len:=Length(FRes64+100000); //<<-- hier gleich mehr byte reservieren
  Rnd:=255;
  R:=0;
  while Cnt>0 do
  begin
    Akt:=Config.Start;
    C:=0;
    while Akt<>Config.Ziel do
    begin
      if Rnd>31 then begin R:=Random(MaxInt); Rnd:=0; end;
      if (R and (1 shl Rnd))<>0 then
        Inc(Akt)
      else if Akt>3 then Dec(Akt);
      Inc(C);
      Inc(Rnd);
    end;
    if C>=Len then
    begin
      Len:=C+1;
      SetLength(FRes64,Len+100000); //<<-- hier gleich mehr byte reservieren
    end;
    Inc(FRes64[C]);
    Dec(Cnt);
  end;
end;

PS: bei mir werden ca. 4'000'000'000 random aufrufe in ein paar wenigen sekunden abgearbeitet... also, an random kanns nicht liegen..

[glkgereon]

Also das mit 32Bit vs 64Bit habe ich auch schon ausprobiert.

Statt einem array of Int64 ein array of Integer zu nehmen bringt, es hat mich sehr erstaunt, keinen messbaren Performanceschub.
Ich habe es mehrmals gemessen, die Differenz war <2 Sekunden auf 5 Minuten.

Das mit dem SetLength ist eigentlich keine Schlechte Idee, auch wenn es hier an der falschen Stelle steht
das ganze muss eine Zeile höher.
Allerdings bringt auch dies keinen signifikanten Unterschied.

Len:=C+1; 43s für 10mio
Len:=C+100; 43s für 10mio
Len:=C+10000; 42s für 10mio


Übrigens ist mir eine Sache aufgefallen...
während folgende Abfrage:
if Random(2)=1 then Eine ziemlich glatte Kurze hervorbringt, hat bei dieser Bedingung:

Delphi-Quellcode:

if Rnd>31 then begin R:=Random(MaxInt); Rnd:=1; end;
if (R and (1 shl Rnd))<>0 then

Die Kurve deutlich ausgeprägte Spitzen!
interessanterweise in 32er Abständen...
So wie das im Moment ist scheint diese Optimierung die zufällige Verteilung etwas aus dem Gleichgewicht zu bringen.

[Edit]
Jetzt versteh ich gar nix mehr.
Ist Cardinal schneller als Integer???
if Rnd>31 then begin R:=Random(High(R))+1; Rnd:=1; end; mit Integer auf 10mio: 35s
mit Cardinal auf 10mio: 27s


[Edit2]
Das Array hingegen auf Cardinal downzugraden brachte mich lediglich von 27 auf 26s.
Die sind wahrscheinlich auch eher im nur halb so kleinen Array begründet.

[Edit3]
Im Anhang mal ein ScreenShot von den "Zacken"...
btw scheinen es nicht 32er Abstände zu sein sonderen 31er.

[Hawkeye219]

Gereon, hast du meinen Vorschlag aus Beitrag #33 einmal geprüft? Das Code-Stück ersetzt lediglich die innere WHILE-Schleife deines Codes.

Gruß Hawkeye

[glkgereon]

Zitat von Hawkeye219:

Gereon, hast du meinen Vorschlag aus Beitrag #33 einmal geprüft? Das Code-Stück ersetzt lediglich die innere WHILE-Schleife deines Codes.

Gruß Hawkeye

Ganz ehrlich würde ich so eine Lösung mit allen Mitteln vermeiden wollen

Aber ich probiere es gleich mal aus.

[Edit]
Die If-Anweisungen um Abzubrechen scheinen mehr Ticks zu brauchen als dei Auflösung der Schleife einbringt...
Es dauert 29s statt nur 27s.