Hello, Guest the thread was called4.9k times and contains 44 replays

last post from Womak at the

Zufallszahlen

    Wie wäre es damit?

    Code
    1. 10 printti$
    2. 20 x=99:dima(x):fori=0tox:a(i)=i:next
    3. 30 n=int(rnd(1)*x):ifn<>xthenb=a(x):a(x)=a(n):a(n)=b
    4. 40 x=x-1:on-(x>0)goto30
    5. 50 printti$

    Zeile 20: Zuerst wird ein Array aufsteigend mit Zahlen von 0-99 gefüllt.
    Zeile 30: Zufallszahl n wird ermittelt - und zwar nur von den verbleibenden Zahlen x.
    Die erhobene Zufallszahl wird mit der letzten Zahl im Array getauscht, sofern eh nicht bereits identisch mit der bestehenden Zahl.
    Das sorgt dafür, dass nur noch verbleibende Zahlen im Array 0-x vorhanden sind.
    Zeile 40: index x wird um 1 verringert. Das wird solange wiederholt, bis x den Wert -1 erreicht hat.


    Die Routine benötigt etwa 4-5 Sekunden.


    EDIT: Mac Bacon war schneller :)

    Quote from Mac Bacon

    (das angehängte Programm nicht ansehen, wenn Du selber knobeln willst)


    Quote from wizball6502

    Die Routine benötigt etwa 4-5 Sekunden.

    Wow, sehr gut und konstant schnell! :thumbup:


    Meine Routine geht einen etwas anderen Weg und ist leider sehr unkonstant im Tempo, dafür aber sehr "klein".


    Das "on-(x>0)goto30" find ich Klasse! Ist wohl auch schneller als eine if -Abfage?

    Ich stoße gerade durch Zufall hier drauf. Es geht noch schneller, auch ich brauche nur ein Feld, aber ich komme ohne if aus. Daher sind die Zeiten immer gleich, bei 100 Zahlen benötigt man knapp 4 sec. Getestet mit WinVice und C64Studio.


    Das Feld wird initialisiert und mit Werten belegt. Dann kann man in einer weiteren Schleife alles mischen: Beim 1. Element kann man dieses mit irgendeinem der restlichen tauschen (also 100), dann das 2. Element mit einem der restlichen (also 99) usw. Die Variable P ist die Position, an der ich gerade mische, die Anzahl der noch nicht gemischten sind N-P. Z ist meine zufällige Zahl (zwischen 0 und N-P-1), sodass ich einfach die Stelle P mit (N-1) - Z tauschen kann.
    P muss dann nur von 0 bis N-2 laufen (das letzte Element N-1 kann man ja nicht mehr tauschen).


    Wenn man die ganzen REMs ab 100 entfernt, geht es noch etwas schneller. :-)


    So ist es noch ein bisschen schneller (ca. 3. 2 Sekunden für 100 Zahlen). Die Laufzeit und durchmischte Zahlenreihenfolge werden im Anschluss ausgegeben.

    Hinweis:
    rnd(0) ist ein wenig schneller als rnd(1), folgt aber einem "Fibonacci"-Muster. Empfehlenswert ist somit zumindest eine Seed-Initialisierung mit rnd(-ti) bei Programmstart, ansonsten ist die Zufallsfolge immer gleich, wenn das Programm geladen und gestartet wird - sofern bis zu diesem Zeitpunkt noch keine Zufallszahlabfrage erfolgt ist.


    "on x goto 50" macht sich ein Verhalten zunutze, als dass nur Zahlen ausgeführt werden, zu denen es Goto's gibt. Die Bedingung ist in diesem Fall erst bei der Zahl 1 erfüllt. "onxgoto50:goto30" ist tatsächlich messbar schneller als "if x>1 goto30".


    Die Schreibweise mit dem führenden Minus-Zeichen "on-(a=b)goto" ist ebenfalls ein klassischer Trick um eine If-Abfrage zu ersetzen und wird vor allem bei Zehnzeilern gerne genutzt. Eine Logischer-Vergleich (a=b) ergibt entweder 0 oder -1. mit dem führenden Minus wird die -1 zu einer +1 und damit wird der goto ausgeführt.


    EDIT: Gerade noch überprüft: Die Abfrage "ifn<>xthen" kostet in der Summe mehr Zeit als dass sie hilft. Weglassen bringt das ganze auf konstante 3.2 Sekunden. Habe das im Code-Beispiel korrigiert.

    Quote from Kosmas

    wizball6502 : Da hatten wir die gleiche Idee, aber Du warst schneller.

    Nun ja, es scheint so, als ob Mac Bacon noch etwas schneller war. Und seine Routine ist vom Prinzip her auch die Schnellste, indem dort eine For/Next-Schleife für das Runterzählen sorgt. Macht Sinn. Auch hatte ich bei mir noch einen dummen Fehler drin, der dafür sorgte, dass der letzte Eintrag "a(99)" nie eine 99 hätte sein können. Gleichzeitig habe ich aber noch gesehen, dass man das INT weglassen kann. Ein Array kann auch mit einer Floatingpointzahl umgehen, z.B. "a(58.2345)" entspricht "a(58)".


    Mit dieser Erkenntnis konnte ich die Routine nochmals beschleunigen und komme damit auf 2.7 Sekunden.

    Auf jeden Fall hat die kleine Hirnakrobatik und Code-Optimierung viel Spass gemacht. Wäre mal einen Versuch Wert, damit einen Blackjack-Zehnzeiler (PUR-80) zu schreiben :D

    Viel hat das nicht mehr gebracht, aber immerhin. Wir sind nun bei 2.6 Sekunden. Das Bildschirmabschalten empfehle ich aber eh nicht, weil ja jemand dann strandet, wenn er genau dann das BASIC-Programm abbricht. Das "rnd(0)" durch "rnd(.)" zu ersetzen hat wohl nur eine hundertstel Sekunde gespart. Ich schätze Bildschirm abschalten und 0 durch . ersetzen sind nur ca. 0.8 Sekunden Gewinn. Der zusätzliche poke/peek benötigt halt auch schon etwas Zeit.

    Was man aber sinnvollerweise machen kann, ist, ab dem zweiten Mischen die Intialisierung (in Zeile 20) auszulassen. Die haben wir ja nur gebraucht um die Zahlen 0-99 in den Array zu schaufeln. Und die sind im gemischelten Array ja nach wie vor so vorhanden. Ab dem zweiten Aufruf dauert die Verarbeitung dann nur noch 2.1 Sekunden. :thumbsup:

    Kleines Update.
    Ich hab "meine" Routine etwas umgebaut und komme jetzt gerade auf ziemlich Konstante 4,2 - 3,9 sek für 98 Zahlen!
    AUF REAL HARDWARE GEMESSEN!
    Ich hab aber noch eine Verbesserungsidee die einiges an Geschwindigkeit bringen könnte!
    Mal sehen, konstant eine 3,x wäre mein Ziel!!! :thumbup:

    Quote from Vernunftmensch

    Echte Zufallszahlen sollten auf einer Gleichverteilung gebunden sein

    Totaler Blödsinn, Zufallszahlen können jede beliebige Verteilung haben. Und mit "echt" oder
    "unecht" hat das rein garnichts zu tun.


    Edit: du kannst z.B. mit Methoden wie Box-Muller aus Zuvallsvariablen beliebiger Verteilungen
    normalverteilte Zufallszahlen machen. Und umgekehrt können aus normalverteilten Zuvallszahlen
    neue beliebiger Verteilung generiert werden. Das würde ja heissen, dass aus "unecht" "echt" und
    wieder zurück werden kann, d.h. ist ein wenig spooky.