Komischer Zufall (Linux-Magazin, April 2018)

Wer aktiv den Aktienmarkt verfolgt, hört auch so manchen Prahlhans damit hausieren gehen, dass seine Kauf- und Verkaufsstrategie angeblich nur Gewinne und nie Verluste einfährt. Dabei weiß jeder, der "A Random Walk down Wall Street" ([2]) gelesen hat, dass wilde Aktienspekulation auf die Dauer nur in den Spielerbankrott führt. Aber was ist mit den wenigen angeblich so talentierten Fondmanagern, die ihre Einlagen seit 20 Jahren so gut verwaltet haben, dass sie Jahr für Jahr mit Gewinnen punkten?

Laut [2] gäbe es selbst bei einem Münzwurfwettbewerb mit genügend Mitspielern ein kleine Zahl meisterhaften Werfer, die zum bassen Erstaunen ihrer Mitstreiter anscheinend spielerisch 20 Mal hintereinander "Kopf" werfen, ohne dass jemals "Zahl" auftaucht. Aber wie wahrscheinlich ist das wirklich? Es lässt sich leicht errechnen, dass eine Zweierfolge derselben Münzseite mit der Wahrscheinlichkeit 0.5*0.5 also 0.25 auftritt. Ein Hat-Trick kommt mit 0.5**3=0.125, und Zwanziger-Folge ist mit 0.5**20=0.000000954 schon recht unwahrscheinlich. Dennoch, wenn ein Programm es nur oft genug probiert, klappt es auch irgendwann einmal, was wir heute auf die Probe stellen. Der kleine Python-Generator coin_throw() in Listing 1 simuliert Münzwürfe, bei denen mit jeweils 50% Wahrscheinlichkeit "Kopf" oder "Zahl" fallen.

Listing 1 teilt sich in den Wurfgenerator coin_throw() und die Auswertung des Experiments in der Funktion experiment(). In eine for-Schleife wie in Zeile 16 eingebettet, sieht es so aus, als würde coin_throw() eine lange Liste von Ergebnisstrings aus "heads" oder "tails" zurückliefern, aber in Wirklichkeit handelt es sich bei der Funktion um einen dynamischen Generator, der immer dann einen neuen Wert liefert, wenn eine Iterationspumpe wie die for-Schleife nachfragt, ob noch mehr kommt.

Abbildung 1: Münzwurf per Python-Generator

Im Haus des Generators

Wie funktioniert der Generator, dessen Ausgabe in Abbildung 1 zu sehen ist? Der Schlüssel ist der yield-Befehl in Zeile 8 in Listing 1. Python unterbricht auf ein yield hin die Ausführung der aktuellen Funktion, merkt sich deren Zustand und gibt in Zeile 8 den ihr übergebenen Zufallswert ("heads" oder "tails") zum aufrufenden Programm zurück. Dazu liefert die Methode randint(0,1) mit jeweils 50% Wahrscheinlichkeit die Integerwerte 0 oder 1, mit denen das Skript jeweils einen der beiden Einträge im Tupel sides herauspickt. Beim nächsten Aufruf der Funktion coin_throw() kehrt der Programmfluss zum Ort des letzten Absprungs zurück, um dort weiter zu machen, wo yield vorher auf gehört hat. Im vorliegenden Fall ist das die Endlosschleife mit while True in Zeile 7, deren Bedingung auch weiterhin wahr ist, worauf ein weiterer yield-Befehl erneut einen Zufallswert zurückschickt. So produziert der Generator in coin_throw() eine endlose Folge von Werten, und schiebt immer einen neuen nach, falls die for-Schleife nach mehr verlangt.

Listing 1: cointhrow

    01 #!/usr/bin/env python3
    02 import random
    03 
    04 def coin_throw():
    05   sides=('heads', 'tails')
    06 
    07   while True:
    08     yield sides[random.randint(0, 1)]
    09 
    10 def experiment():
    11   run     = 1
    12   max_run = 0
    13   prev    = ""
    14   count   = 0
    15   
    16   for side in coin_throw():
    17     count += 1
    18   
    19     if prev == side:
    20       run += 1
    21       if run > max_run:
    22         max_run = run
    23         print("max_run: %d %s (%d)" % 
    24               (max_run, side, count))
    25     else:
    26       prev = side
    27       run  = 1
    28 
    29 experiment()

Der Restcode der Funktion experiment() merkt sich die Anzahl gleichartiger Würfe in run, die maximal längste Folge so weit in max_run, den vorhergehenden Münzwurf in prev ("heads", "tails") und die Gesamtzahl der Würfe bisher in count.

Abbildung 2: Längste Folgen von identischen Münzwürfen.

Fatales Double Down

Die Ausgabe des Skripts in Abbildung 2 offenbart, dass nach 21 Millionen Durchgängen tatsächlich einmal eine Folge von 23 "tails" hintereinander aufgetreten ist. Hätte ein Spieler nach der Double-Down-Methode bei jedem Verlust jeweils den Einsatz fürs nächste Spiel verdoppelt, bräuchte er bei einem Anfangseinsatz von einem Euro insgesamt 2**23-1 = 8.388.607 Euro Spielkapital, um nicht bankrott zu gehen, falls er auf "heads" gesetzt hat und dummerweise 23 mal hintereinander "tails" kommt.

Ganz große Klasse

Python bietet aber nicht nur Generatoren mit dem yield-Schlüsselwort, auch Klassen können Generatoren als Iteratoren implementieren. Hierzu definiert der oder die Pythonista zwei Methoden, __iter__() und __next__(). Die "Dunder" genannten Quadrupel-Unterstriche kennzeichnen offizielle Eintrittspunkte für Pythons Standard-Library. Sieht der Python-Interpreter einen Schleifenkopf wie for n in Roulette(), instantiiert er ein Objekt der Klasse Roulette, greift sich mit __iter__() dessen Iterator und holt dann von letzterem mit Aufrufen von __next__() so lange neue Werte ab, bis der Iterator eine Exception wirft.

Listing 2: roulette.py

    01 #!/usr/bin/env python3
    02 import random
    03 
    04 class Roulette:
    05   slots   = 36
    06   numbers = range(slots+1)
    07 
    08   def __iter__(self):
    09     return self
    10 
    11   def __next__(self):
    12     idx=random.randint(0, __class__.slots)
    13     return __class__.numbers[idx]

In der vorliegenden Klasse in Listing 2 gibt __iter__() bequemerweise gleich die Roulette-Instanz selbst zurück, denn die Klasse braucht keinen separaten Iterator, da sie ihn mit __next__() gleich selbst implementiert. Dessen Aufruf gibt immer wieder eine neue Zufallszahl im Bereich 0-36 zurück und wirft niemals eine Exception, so dass der Fluss für die for-Schleife im Hauptprogramm niemals versiegt.

Die Klasse Roulette definiert dazu zwei Klassenvariablen, slots als die höchste Zahl im Roulette-Kreisel und numbers als eine Sequenz von Nummern von 0 bis einschließlich 36. Es ist sinnvoll, diese Variablen nur einmal für die Klasse zu definieren und nicht etwa pro Instanz oder sie gar bei jedem Aufruf des Operators zeitverschwenderisch neu aufzubauen.

Klasse oder Instanz?

Pythons Klassenvariablen unterscheiden sich von Instanzvariablen dadurch, dass der Zugriff auf sie nicht mit self.variable sondern mittels __class__.variable oder self.__class__.variable erfolgt. Bei rein lesendem Zugriff könnte man die Klassenvariable sogar über den Instanzweg self.variable referenzieren, wer letztere allerdings anschließend modifiziert, erlebt sein blaues Wunder, da Python hinterrücks eine neue Instanzvariable anlegt, die sich von der Klassenvariable abgekoppelt hat und anschließend jedes Objekt seine eigenen Werte erhält, statt etwaige Änderungen auf Klassenebene zu propagieren. Methoden finden die Klassenvariable auch nicht einfach über deren Namen, wer in __iter__() einfach slots referenziert, bekommt einen Syntaxfehler um die Ohren.

Listing 3: roulette-run

    1 $ ./roulette
    2 max_run: 2 11 (27)
    3 max_run: 3 15 (6249)
    4 max_run: 4 34 (57393)
    5 max_run: 5 1 (3363284)
    6 max_run: 6 0 (95846456)
    7 max_run: 7 26 (357289507)

Und wie so häufig in der Python-Welt gilt es auch hier, einen kleinen aber feinen Unterschied zwischen den Versionen 2 und 3 zu beachten: Der Iteratoreinstieg in die Generatorklasse heißt in Python 2 "next" und nicht "__next__" wie in Python 3, sodass Programmierer, die beide Versionen bedienen wollen, typischerweise einfach eine weitere Methode next() definieren, die ihr übergebene Parameter unmodifiziert an __next__() weiterreicht. Python 3 nutzt kein next(), so dass der Kompatibilitätstrick dort keinen Schaden anrichtet.

Die Ausgabe der statistische Auswertung des Roulette-Generators zeigt Listing 3. Nach 27 Durchgängen trat zum ersten Mal eine Doublette auf, die Zahl 11 kam zweimal hintereinander. Nach 6249 mal "Faites votre jeux" kam dann dreimal hintereinander die 15, nach 57.393 Spielen viermal die 34, und so weiter.

Tumultartige Szenen

Was wäre wohl in Las Vegas an einem Spieltisch los, an dem sechs mal hintereinander die Null käme wie in Listing 4 nach 95 Millionen Kreiseldurchgängen? Tumultartige Szenen würden sich wahrscheinlich abspielen, bevor der Pitboss erschiene und den Croupier in den Feierabend schickte, weil jeder Gast sofort vermuten würde, dass etwas nicht mit rechten Dingen zugeht. Doch statistisch gesehen läuft alles in geordneten Bahnen ab, irgendwann wiederholen sich auch Zufallswerte einfach zwangsläufig.

Tolles Lotto

Oder was würden die deutschen Fernsehzuschauer denken, falls die Lottofee die gezogenen Zahlen mit 1, 2, 3, 4, 5, und 6 ansagen würde? Da die Wahrscheinlichkeit für einen Sechser bei etwa 1:14 Millionen liegt, und es 44 Kombinationen von direkt aufeinander abfolgenden Lotto-Kombinationen gibt (1, 2, 3, 4, 5, 6 bis 44, 45, 46, 47, 48, 49), liegt die Chance einer großen Straße beim Lotto bei etwa 1:318000, und damit sollte sich das unglaubliche Ereignis mit einem schnellen Ziehungsgenerator relativ zügig einstellen.

Listing 4: lotto

    01 #!/usr/bin/env python3
    02 import random
    03 
    04 def lotto_draw():
    05   total   = 49
    06   draws   = 6
    07   numbers = list(range(1,total+1))
    08   size    = total
    09   result  = []
    10 
    11   for _ in range(draws):
    12     idx = random.randrange(size)
    13     result.append(numbers[idx])
    14     numbers[idx] = numbers[size-1]
    15     size -= 1
    16 
    17   return sorted(result)
    18 
    19 def is_consecutive(draw):
    20   prev=-1
    21   for number in draw:
    22     if prev < 0:
    23       prev=number
    24     elif prev + 1 == number:
    25       prev = number
    26     else:
    27       return False
    28   return True
    29 
    30 count = 0
    31 while True:
    32   count += 1
    33   draw=lotto_draw()
    34   if is_consecutive(draw):
    35       print("%d: %s" % (count, str(draw)))
    36       break

Listing 4 zeigt einen Ziehungsautomaten in der Funktion lotto_draw(). Von 49 numerierten Kugeln in der Liste numbers zieht er sechsmal eine zufällige und entfernt sie anschließend, um Doppelziehungen auszuschließen. Da es enorm Rechenzeit kostet, ein Element aus einer Python-Liste zu entfernen und die restlichen Elemente aufrücken zu lassen, um die Lücke zu schließen, vertauscht die Funktion den Wert des ausgewählten Elements kurzerhand mit dem letzten Element der Liste und setzt die Listenlänge size um Eins herunter. Zurück gibt lotto_draw() eine sortierte Liste mit sechs zufällig ausgewählten Kugeln, und das Hauptprogramm ab Zeile 30 prüft nun mittels is_consecutive(), ob die gezogenen Zahlen sich jeweils nur um Eins von ihrem Vorgänger unterscheiden. Ist dies der Fall, druckt Zeile 35 die Anzahl der bislang durchgeführten Ziehungen in count aus, sowie die Glückszahlen, die zum Abbruch führten. Abbildung 3 zeigt, dass dies manchmal schon nach 30.000 Durchgängen auftritt, manchmal allerdings erst bei mehr als 800.000, zufällig eben, aber im Rahmen der eingangs errechneten Wahrscheinlichkeit.

Abbildung 3: Der Lotto-Generator ermittelt die Anzahl der Ziehungen, bis ein lustiges Ergebnis erscheint.

Zur Implementierung dieser und anderer cooler Python-Tricks sei das Buch "Python Tricks" von Dan Bader empfohlen ([3]). Es zeigt eine Vielzahl von alltäglichen Programmieraufgaben, für die es elegante Lösungen in Python gibt. Es eignet sich hervorragend für Umsteiger aus anderen Programmiersprachen (wie Perl!), die sich hauptsächlich dafür interessieren, typische Idiome in sauberes Python umzusetzen und nicht bei Adam und Eva und "Hello World" anfangen wollen.

Infos

[1]

Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2018/04/snapshot/

[2]

"A Random Walk down Wall Street", Burton G. Malkiel, https://www.amazon.com/Random-Walk-Down-Wall-Street-ebook/dp/B00QH9NTSI

[3]

"Python Tricks", Dan Bader, 2017, https://www.amazon.com/Python-Tricks-Buffet-Awesome-Features-ebook/dp/B0785Q7GSY

Michael Schilli

arbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen.

POD ERRORS

Hey! The above document had some coding errors, which are explained below:

Around line 5:

Unknown directive: =desc