Random(2) in schnell

[Nikolas]

Für welche Anzahl an Stufen ist denn die Grafik oben erstellt worden?
Kannst du mal ein paar Testergebnisse also (Levelzahl/durchschnittlicheSteinZahl)-Paare angeben?

[glkgereon]

Zitat von Nikolas:

Für welche Anzahl an Stufen ist denn die Grafik oben erstellt worden?
Kannst du mal ein paar Testergebnisse also (Levelzahl/durchschnittlicheSteinZahl)-Paare angeben?

Es geht grundsätzlich nur um 0-15.
Bei den Grafiken oben ist x=So oft und y=Anzahl steine

Durchschnitt ist ca. 162

[Nikolas]

Ich kann dir sagen, der Durchschnitt liegt bei exakt 162. Allgemein wird dein Wahrscheinlicher Wert bei n Steinen (und drei Stufen, auf denen man nicht zurückfallen kann) bei (n+1)*n+6 liegen.
Beweis kommt nachher, jetzt hab ich Nachhilfe.

[Hawkeye219]

Hallo Gereon,

Zitat von glkgereon:

Die If-Anweisungen um Abzubrechen scheinen mehr Ticks zu brauchen als dei Auflösung der Schleife einbringt...

Die IF-Anweisungen sind auch in deinem Code enthalten, sie stecken in der WHILE-Anweisung. Der Verzicht auf den Bitzähler sowie der Ersatz von Sprüngen ("if Akt > 3..." etc.) durch arithmetische Operationen sollten eine Geschwindigkeitssteigerung bringen.

Kannst du die beiden verglichenen Generate-Methoden (mit und ohne "loop unrolling") einmal als Quelltext hier einstellen? Welche Werte hast du für Config.Start und Config.Ziel beim Testen genommen?

Gruß Hawkeye

[grenzgaenger]

hallo geron,
mach doch erst mal 2 tests

• ein neues programm, wo du mit random(2) direkt arbeitest und so oft durch gehst, wie bei deinem anderem progy. mess dabei die zeit.
• auch ein neues program, wo du den code aus deiner routine hineinkopierst, kommentiere die zuweisung der ergebnisse (dein array) aus. und mess auch dort die zeit

als ergebnis sollten wir sehen wo die zeit verbraten wird, 'n profiler haste wohl nicht? da gings direkt... aber so gehts auch ganz gut..., dann wissen wir hier doch mal, wo man am besten anfängt zu optimieren...

[grenzgaenger]

Zitat von glkgereon:

[Edit]
Jetzt versteh ich gar nix mehr.
Ist Cardinal schneller als Integer???

nein, eigentlich nicht, ein cardinal, ist ein integer...

[Nikolas]

Also noch der Beweis:
Deine gesuchte Zahl ist 162. Für die ersten drei Stufen brauchst du 6 Steine (dafür brauchst du keine Simulation, dafür Wertest du die Summe über k*(0.5)^k von 1 bis unendlich aus (Der Erwartungswert für die Anzahl der Schritte um ein Feld nach oben zu kommen, wenn du nicht nach unten darfst. (habe ich, ehrlich gesagt, Maple machen lassen). Du hast Drei solcher Stufen, brauchst im Mittel also sechs Steine, um auf Stufe 3 zu kommen.
Jetzt beginnt der interessante Teil der Rechnung. Im Matheboard habe ich den entscheidenen Hinweis auf die Rekursionsvorschrift bekommen, ihn in eine Matrix umgeschrieben und Matlab drauf losgelassen, was mir dann die untere Matrix in meinem Post dort gebracht hat. (in der oberen habe ich statt 0.5 eine 3 geschrieben, weil die Matrix sonst nicht ins Fenster gepasst hätte. Ausserdem ist n=15 gewählt, bei deinem Spezialfall ist natürlich n=12 notwendig, da die ersten drei Schritte oben schon abgehandelt wurden. Diese Matrix führt dann auf eine durchschnittliche Steinanzahl bis zum ersten erreichen der letzten Stufe von 156. (Wenn man die Matrix zu Fuss löst, kommt man auf n(n+1)=12*13=156)
Mit den Sechs Steinen von oben dann also auf die 162 die du in der Simulation auch gefunden hast.
Wenn also SFix deine Stufenanzahl ist, bei denen du nicht fallen kannst und SFall deine Stufenanzahl mit Fallmöglichkeit, brauchst du also durchschnittlich

Code:

SFix*2+SFall(SFall+1)

Steine, um die höchste Stufe das erste Mal zu erreichen. Und das sollte fast in geringerer Zeit als ein random(2)-Aufruf zu berechnen sein

Code:

(Matlab)
% Matrixdarstellung und Gauß
%
% n=12;
% 
% M=zeros(n,n+1);
% 
% for j=1:(n)
%     M(j,n+1)=1;
% end
% 
% for j=(1:n-2)
%         M(j+1,j+1)=1;
%         M(j+1,j)=-0.5;
%         M(j+1,j+2)=-0.5;
%     end
% end
% 
% M(1,1)=0.5;
% M(1,2)=-0.5;
% M(n,n)=1;
% M(n,n-1)=-0.5;
% 
% 
% rref(M)

% Auswertung der gefundenen Formel n(n+1)
n=30; 

N=zeros(2,n);

for i=1:n 
    N(1,i)=i;
     if i<5 
       N(2,i)=i*2;
   else
       s=i-3;
       N(2,i)=6+s*(s+1);
   end
end

[glkgereon]

ich glaub das muss ich mir mal in ruhe auf ein blatt papier malen was du da mit den matrizen machst^^


gibt es denn eine Möglichkeit die Wahrscheinlichkeit für eine bestimmte Anzahl an Schritten zu berechnen?

[Nikolas]

Wahrscheinlich schon, aber dafür brauchst du einen anderen Ansatz. Melde dich doch mal beim Board an und frage nach einer Möglickeit. Wenn du Probleme mit der Ausführung hast, kannst du ja auch noch hier fragen. Da wirst du schneller zu einer sauberen Lösung finden, als wieder eine Simulation zu schreiben.
Mit Simulationen wirst du hier auch nicht froh. Bei 100 Steinen gibt es schließlich 1,3*10^30 Mögliche Verläufe (stark übertrieben, da du schon nach dem ersten erreichen der letzten Stufe abbrichst, aber auch ein paar Größenordnungen weniger sind noch zu viele)

[Nikolas]

Hier noch die Matrix zu Berechung auf Wunsch von glkgereon.