Zufallszahlen

Zitat von Lysosom

Bubblesort ist bis jetzt der einzige Sortieralgorithmus, den ich verstanden habe....

Wenn Du das nächste Mal Karten spielst, achte mal darauf, wie Du sie auf der Hand sortierst. Kleiner Tip: Es ist garantiert nicht Bubble Sort.

Warum nur noch abschreckend, wenn er zuweilen doch der schnellste und mit Abstand kürzeste und einfachste sein kann? Selbst wenn er in diesem Fall langsamer wäre, aber eben kurz sein soll, wäre er vorzuziehen. Bei Quicksort kommen wir im C64 ohne weiteres vor allem schnell an die Grenzen, weil der Stack voll ist. Das größte Renommee eines Algorithmus' nützt mir nichts, wenn er im eingesetzten Fall nur Nachteile bringt. Insertion habe ich hier nun mal noch nicht ausprobiert.

Das Ansehen aller bekannten Sortierroutinen reicht zumindest dafür aus, dass es unzählige Literatur, Videos und Vergleiche unter allen benannten Algorithmen gibt. Gute Vergleiche berücksichtigen dann auch die völlig unterschiedlichen Einsatzszenarien, von denen es manchmal abhängt, wer gewinnt. Das hängt von der Menge der Daten und auch von der vorliegenden Verteilung ab. Und manchmal eben auch davon, wie viel Speicher ich dafür zur Verfügung stellen will oder kann.

Was ist jetzt mit BogoSort? Die Melodie war so schön. Ist der jemals fertig geworden?

Zitat von atomcode

Warum nur noch abschreckend, wenn er zuweilen doch der schnellste und mit Abstand kürzeste und einfachste sein kann?

Bubblesort ist nie schneller, kürzer oder einfacher als Insertion Sort.

atomcode , Mac Bacon

was haltet ihr von meinem Lotto PRG in post #60

Braucht im Rohzustand für das Lottoproblem ca. 1 sec!

Zitat von Nerd Deluxe

Ich grabe den Thread nochmal aus, weil ich ein kleines Programm geschrieben habe, das eine Lottoziehung simuliert. Dabei werden zunächst 6 zufällige Zahlen im Bereich 1 bis 49 generiert. In einem zweiten Schritt werden doppelt oder dreifach etc gezogene so lange durch andere Zufallszahlen ersetzt, bis man sechs unterschiedliche Zahlen hat. Im letzten Schritt werden dann diese sechs Zahlen aufsteigend angeordnet. Dieser letzte Schritt ist ziemlich verschachtelt und frisst paar Sekunden... falls jemand das Listing haben will, würde ich es hier posten. Geschrieben habe ich es auf den Frodo C64 Emulator.

Coole Sache. Eine Frage hierzu - könnte das Programm so angepasst werden, dass es immer genau die Lottozahlen bringt, die dann ein paar Tage später auch in der TV-Lotterie gezogen werden? So würde es den Usern noch mehr bringen.

Zitat von Nerd Deluxe

Ich habe die Zeit nicht gestoppt. Aber es ist tatsächlich etwas "Bedenkzeit" zu spüren. Der Algorhythmus ist bestimmt nicht optimal... ich werde mich am Wochenende damit ein wenig beschäftigen. Glaube schon zu wissen, wie ich etwa 40% Rechenzeit für den letzten Schritt spare. Ich werde berichten. Ggf. auch das Listing bzw. die Listings hier posten, sofern Interesse besteht.

Generell vom Ansatz erschlägt ein Kartenmischen das Problem natürlich, aber für diesen Fall kann man ja auch etwas gezielter herangehen. Da muss man nicht wild 49 Zahlen herumpermutieren nur damit man dann 6 Zahlen am Rand abzwackt.

Ich hätte vorgeschlagen die 1 bis 49 in ein Array zu legen. Zufällig eine Position 1 bis 49 auswählen, Position 49 mit der Zufallszahl tauschen, dann der nächste Schritt mit zufällig eine Position von 1 bis 48 wählen. Diese mit Position 48 tauschen. Das dann noch analog 4 mal so weiter. In Position 44 bis 49 stehen dann die 6 zufällig "gezogenen" Zahlen. Das sind 6x Zufallszahl ermitteln und 6x vertauschen. Da müsste auch in BASIC ohne merkbare Verzögerung gehen ...

Zitat von JeeK

Zitat von Nerd Deluxe

Ich habe die Zeit nicht gestoppt. Aber es ist tatsächlich etwas "Bedenkzeit" zu spüren. Der Algorhythmus ist bestimmt nicht optimal... ich werde mich am Wochenende damit ein wenig beschäftigen. Glaube schon zu wissen, wie ich etwa 40% Rechenzeit für den letzten Schritt spare. Ich werde berichten. Ggf. auch das Listing bzw. die Listings hier posten, sofern Interesse besteht.

Generell vom Ansatz erschlägt ein Kartenmischen das Problem natürlich, aber für diesen Fall kann man ja auch etwas gezielter herangehen. Da muss man nicht wild 49 Zahlen herumpermutieren nur damit man dann 6 Zahlen am Rand abzwackt.

Ich hätte vorgeschlagen die 1 bis 49 in ein Array zu legen. Zufällig eine Position 1 bis 49 auswählen, Position 49 mit der Zufallszahl tauschen, dann der nächste Schritt mit zufällig eine Position von 1 bis 48 wählen. Diese mit Position 48 tauschen. Das dann noch analog 4 mal so weiter. In Position 44 bis 49 stehen dann die 6 zufällig "gezogenen" Zahlen. Das sind 6x Zufallszahl ermitteln und 6x vertauschen. Da müsste auch in BASIC ohne merkbare Verzögerung gehen ...

Die sind dann aber nicht der grösse nach sortiert, oder?

In meinem einfachen Prog #60 werden sie sortiert ausgegeben, braucht aber 3 arrays!

Startet doch halt wieder eine Competition mit Zeitmessung. Womak legt vor. Obwohl, lohnt sich ja kaum noch.

Zitat von Womak

Zitat von JeeK

Generell vom Ansatz erschlägt ein Kartenmischen das Problem natürlich, aber für diesen Fall kann man ja auch etwas gezielter herangehen. Da muss man nicht wild 49 Zahlen herumpermutieren nur damit man dann 6 Zahlen am Rand abzwackt.

Ich hätte vorgeschlagen die 1 bis 49 in ein Array zu legen. Zufällig eine Position 1 bis 49 auswählen, Position 49 mit der Zufallszahl tauschen, dann der nächste Schritt mit zufällig eine Position von 1 bis 48 wählen. Diese mit Position 48 tauschen. Das dann noch analog 4 mal so weiter. In Position 44 bis 49 stehen dann die 6 zufällig "gezogenen" Zahlen. Das sind 6x Zufallszahl ermitteln und 6x vertauschen. Da müsste auch in BASIC ohne merkbare Verzögerung gehen ...

Die sind dann aber nicht der grösse nach sortiert, oder?

[..]

Für die Sortierung muss man dann nur den Schritt hinzunehmen, beim Tausch dann nicht an eine fixe Position, sondern gleich ala "Insertion-Sort" in den Plätzen (49 - durchlauf + 1) bis 49 einsortiert. Da haben wir dann bei 6 Entnahmen max. 5*(5-1)/2 = 10 weitere Vertauschungen für das Einsortieren in den "Ergebnisbereich".

Zitat von Womak

atomcode , Mac Bacon

was haltet ihr von meinem Lotto PRG in post #60

Braucht im Rohzustand für das Lottoproblem ca. 1 sec!

Naja, es geht schneller, kürzer und verständlicher - aber ich kann durchaus nachvollziehen, dass das nicht gegen das Gefühl ankommt, das Problem selbständig gelöst zu haben.

Zitat von Nerd Deluxe

@ Jeek : ja, schlauer Ansatz. Wobei dann noch die Sortierung von oben nach unten gemacht werden muss.

Also aufsteigend/abfallend kann man dann mit leicht regulieren indem man den Vergleichsoperator zwischen <= und >= wechselt. In meinem Beispiel (wenn man es selbst lösen will, dann eben nicht spoilern) ist das in Zeile 160: <= für aufsteigend, >= für absteigend.

Korrektur zu #70: Bei 5 Elementen, wo einsortiert werden muss, hat man laut Summenformel (n*(n+1)/2) maximal 5*6/2 zusätzliche Vertauschungen bzw. Vergleich.

Zitat von Mac Bacon

Bubblesort ist nie schneller [...] als Insertion Sort.

Der schnellste von allen meinte ich auch gar nicht. Das wäre natürlich eine unhaltbare Behauptung. Ich schrieb ja, dass ich Insertion im vorliegenden Beispiel noch nicht berücksichtigt hatte, so wie viele andere nicht. Gegenüber Quicksort, der generell einer der schnellsten ist, war Bubble jetzt hier aber schneller. Und damit gibt es mit Sicherheit noch so einige Kandidaten, die aufgrund ihrer Komplexität bei kleinen Mengen langsamer sind. Bei einem 10-Kampf fragt man ja auch nicht erst im Publikum, ob da noch einer sitzt, der schneller ist. Da ist der schnellste immer erst mal der von den antretenden Sportlern.

Dass Bubble grundsätzlich langsamer ist als Insertion, ist ja kein Geheimnis. Gibt genügend Erklärungen im Netz und Videos, die die Berechnung der Anzahl von Operationen zeigen.

Zitat von Mac Bacon

Bubblesort ist nie [...] kürzer oder einfacher als Insertion Sort.

Das sehe ich anders. Ich habe deine eigene Version aus dem Sortier-Thread herangezogen, die dann der Mike noch optimiert hatte (sogar mit einer offenen Schleife! von wegen einfacher), und die ich selbst nochmals zusammengestaucht habe. Trotz allem ist Bubble bei gleichen Bedingungen und Variablennamen noch ein Byte kürzer (73 vs 74). Der Geschwindigkeitsunterschied lag durchschnittlich bei ca. 90ms.

Im Anhang Quick vs. Bubble vs. Insertion. Diesmal mit 6 verschiedenen aus 49.

Zitat von Womak

was haltet ihr von meinem Lotto PRG in post #60

Braucht im Rohzustand für das Lottoproblem ca. 1 sec!

Bin jetzt erst dazu gekommen, das zu analysieren.

Die Grundidee, statt einer Ziehung zunächst nur eine Auswahl zu treffen, um damit schon die halbe Miete für den ansonsten eher langsamen IndexSort zu haben, ist sehr gut. Die Sortierung bzw. Zusammenschiebung auf 6 aufeinander folgende Zahlen dauert dann etwa so lange wie BubbleSort.

Die Auswahl selbst ist hier allerdings wieder indeterministisch. Ein Determinismophiler würde Angst haben, dass das Programm stehen bleibt und die Welt untergeht. Das lässt sich aber leicht durch eine deterministische Variante ersetzen, die nicht länger ist und auch, ohne das Grundprinzip für den IndexSort ändern zu müssen.

Ich habe deine Version entsprechend verändert und komprimiert. Benötigt dann für die determ. Auswahl von 6 aus 49 und die Sortierung zusammen etwa nur 650ms.

Dieser Code in weiter komprimierter Form (dann 850ms) ist von allen mir bekannten Möglichkeiten mit Abstand der kürzeste, nämlich nur 116 Bytes in zwei Zeilen:

Drei Arrays waren es anfangs. Wenn man die 6 ausgewählten Zahlen an den Anfang eines der beiden großen Arrays schiebt, dann sind es noch zwei (s.o.). Anstatt ein zweites großes Array für die Speicherung der Auswahl zu verwenden, lässt sich die Auswahl auch im ersten Array in Bit 7 oder 8 speichern. Dann ist es nur noch ein einziges Array, allerdings zulasten der Geschwindigkeit, versteht sich. Hier mal wieder indeterministisch ... geht aber auch in Kombination mit der obigen Lösung. Es werden nur I, N und Z() verwendet:

Noch etwas schneller war allerdings die normale determ. Ziehung von 6 aus 49 mit anschließender Sortierung durch rückwärts laufendem InsertSort: 616ms bei 4 Zeilen Code, 2 für die Ziehung und 2 für die Sortierung:

Abschließend noch mal die vier geprüften Sorts im Vergleich:

Zitat von jolu

Zitat von franky74

Hat mal jemand eine Statistik erstellt, inwieweit beim jeweiligen C64-Modell Zufallszahlen wirklich Zufall sind?

Das nicht, aber als wir damals Ende der 80er in Mathe mit Stochastik angefangen haben, hatten wir als Hausaufgabe, sehr oft zu Würfeln und die Ergebnisse aufzuschreiben, um zu sehen, wie Gleichverteilung aussieht. Natürlich haben die meisten Computerbesitzer das ihre Rechenknechte machen lassen.

Alle Besitzer desselben Computermodells hatten dieselben Ergebnisse.

Siehe auch Pseudozufallszahlen.

Bei der RND-Funktion von BASIC V2 hängt es beim C64 vom Parameter ab. Wie schlecht hier beispielsweise RND(0) ist, sieht man beim entsprechenden Beispiel zum Artikel RND im C64-Wiki. Üblicherweise initialisiert man den Startwert mit einem möglichst zufälligen (etwa von der hardware abhängigen) Startwert, z.B. RND(-TI). Die Folge RND(1) liefert dann eine bestimmte Folge für diesen Startwert. Die Qualität der hängt dann davon ab, wie lange der Zyklus ist, bis sich die Zahlenreihe wiederholt. Das ziemlich einfache Polynom bei RND hat recht viele kurze Zyklen, was die Qualität ziemlich drückt. Ich weiß jetzt nicht, ob in dem Artikel Verweise auf genauere Untersuchungen angegeben sind, jedenfalls bilde ich mir ein, so etwas gelesen zu haben (möglichweise auch in einem anderen Thread hier bereits diskutiert).

Ergänzung zum Programm bei Posting #73: In Zeile 110 wird N nicht richtig berechnet (die Entnahme aus der Restmenge).

Im Wesentlichen entspricht es der von atomcode vorgestellten Variante mit Insertion-Sort, allerdings alles in einem Array (in-place sozusagen). Irgendwie finde ich die Index-Sort-Variante im Falle einer schwachen Besetzung verschwenderisch, wo sich die 6 Werte in Index-Array mit 49 Elementen verlieren. Gut, man könnte vorzeitig abbrechen, wenn man bereits das 6. Element gefunden hat. So richtig spielt Index-Sort in dieser Variante seine Vorteile dann aus, wenn mehr als 10 Elemente in Reihenfolge zu bringen wären. Sonst ist der Worst-Case von Insertion-Sort (rein von den Durchläufen) günstiger. Auch dass man 2 Arrays braucht, stört mich als platzknausrigen Programmierer immer wieder. Wenn man den Platz hat und auch hinsichtlich der Übersichtlichkeit und Klarheit, sind mehrere Array natürlich auch immer sinnvoll.

Das 4. Beispiel von Posting #77 verwendet RND(.) (also 0), was von der Qualität suboptimal ist (bei den anderen Beispielen wird mit einem Wert >0) gearbeitet, was besser sein sollte.

In der unten angeführten Variante von Posting #73, ist etwas auf Zeitmessung optimiert (abgesehen von der Zusammenstauchung auf möglichst wenig Zeilen) und braucht so zwischen 0,60 und 0,72 s.

Bei der Zeitnehmung mittels Zurücksetzen von TI$ muss man aufpassen, da der Seed der Zufallsreihe immer wieder zurückgesetzt wird, daher kein Neustart mit RUN, sondern mit GOTO21.

In Zeile 6 kann man 6 aus 49 auch entsprechend parametrisieren.

Ich habe gerade mal die Equal Sequences aus 10.000 Stellen gezählt ..

1) aus Nachkommastellen der Zahl Pi im Bereich um 32mio,

2) generiert durch INT(RND(1)*10)

3) und generiert durch INT(RND(0)*10), absichtlich unverzögert und gleichmäßig.

Ergebnis: Das Verhalten von RND(1) entspricht sehr gut den Nachkommastellen von Pi. RND(0) in der oben beschriebenen Verwendungsart zeigte in der Anzahl der Ziffern, aber vor allem auch in der Anzahl der Sequenzen, starke Unregelmäßigkeiten gegenüber Pi. Besonders unbeliebt war die Ziffer 2. Dennoch kann man bei der Betrachtung von 10.000 Ziffern noch nicht sagen, ob diese Verteilung auch noch bei 100.000 oder 1mio so ausfiele. Wahrscheinlich würde schon eine kleine zeitliche Störung die Verhältnisse ändern. Gleichmäßigkeit ist jedenfalls schlecht für RND(0).

Nebeneinander liegende Duplikate von Floats mit RND(0 oder 1) tauchen auch nach Millionen von Tests nicht auf.

Auch die Zahl 0.5 kam in 10 Millionen Tests nie vor; interessant für Richtungsentscheidungen mit SGN(RND(1)-.5).

Equal Sequences bei generierten Integers sind bei RND(0) offenbar etwas mehr als bei RND(1) und bei RND(1) mit eingestreutem RND(0) etwas weniger als nur mit RND(1).

Der Grund dürfte darin liegen, dass (laut Wiki) RND(0) im Prinzip nichts anderes sei als RND(-TI), weil es mit relativ wenig Schüttelaufwand aus TI generiert wird. Darum ist RND(0) auch schneller als RND(1). Die reinen Pseudozufallszahlen aus RND(1) werden dagegen ausschließlich algorithmisch generiert und brauchen daher länger. RND(1) habe einen Bug, der (unter nicht näher erklärten Bedingungen) bewirken könnte, dass sich die Zahlen schneller wiederholen. RND(0) ist geeignet, wenn die Abfrage nicht zu schnell und stattdessen ungleichmäßig aufeinander bzw. sporadisch erfolgt, da die Uhr auch nur eine unstetige lineare Funktion ist. Besonders durch die zeitliche Abhängigkeit von Benutzereingaben wird aus RND(0) dann eine gute Zufallszahl. RND(1) ist auf jeden Fall sinnvoll, wenn man über längere Zeit oder größere Mengen generieren muss, und wegen des Bugs vllt. bei Gelegenheit mal mit RND(0) neu geseedet.

Nehmen wir also mal die ersten Nachkommastellen der Zahl Pi als Ansammlung von Pseudozufallszahlen aus 0 bis 9, entstanden durch die Summe sehr vieler überlagerter Stammbrüche (Leibniz-Reihe), die entweder endlich sind oder einem Muster entsprechen (Periode). Dass dabei schon ab der 762. Stelle 6 Neunen in Folge auftauchen, ist aber kein Fehler in der Matrix, sondern gewissermaßen Zufall (im Sinne von unüberschaubarem Zusammenfall von Ereignissen). Und genauso dürfte das auch schon mal bei einem Generator passieren. Wenn man das nicht möchte, dann hat das weniger mit Zufall zu tun als mit einer möglichst unregelmäßigen Verteilung der Zahlen.

Allerdings halte ich für Spiele die Vorgehensweise zur Gewinnung von Zufallszahlen für nicht so wichtig. Zufall ist gerade bei Spielen erst richtig interessant, wenn er zufällig Muster hervorbringt, so wie auf dem Mars die vielen Aliens und Gebäude-Bruchstücke, die man da immer wieder sieht. Aktuell sieht ein Wissenschaftler(!) da sogar Insekten. https://www.scinexx.de/news/ko…ht-insekten-auf-dem-mars/

Zwei gleiche gibt es im Lotto ja eh nicht, aber 1999 und 2014 gab es jeweils 5 aufeinander folgende Zahlen (2,3,4,5,6 und 9,10,11,12,13). Im ersten Fall gab es nur 194€ für 5 Richtige.

btw Viel interessanter als die Diskussion, wie man vermeintlich perfekte Zufallszahlen erzeugen kann, fände ich die Überlegung, wie man mit Zufallszahlen überhaupt geschickt in Spielen Bestandteile und Inhalte erzeugt. Auch unveränderlicher Content lässt sich mit Hilfe von festen Pseudozufallszahlen, in Assembler mit schnellen Schieberegistern, erzeugen. Das Thema bietet sich gerade für kleine Systeme an, auf denen der Speicherplatz beschränkt ist.