23.2    Generatoren 

In diesem Abschnitt beschäftigen wir uns mit dem Konzept der Generatoren, mit deren Hilfe sich Folgen von Werten komfortabel erzeugen lassen. Weil sich das noch sehr abstrakt anhört, beginnen wir direkt mit einem Beispiel. Sie erinnern sich sicherlich noch an die Built-in Function range, die im Zusammenhang mit for-Schleifen eine wichtige Rolle spielt:

>>> for i in range(10):
...     print(i, end=" ")
0 1 2 3 4 5 6 7 8 9

Wie Sie bereits wissen, gibt range(10) ein iterierbares Objekt zurück, mit dem sich die Zahlen 0 bis 9 in der Schleife durchlaufen lassen. Sie haben bereits gelernt, dass range dafür keine Liste mit diesen Zahlen erzeugt, sondern sie erst bei Bedarf generiert. Es kommt häufig vor, dass man eine Liste von Objekten mit einer Schleife verarbeiten möchte, ohne dass dabei die gesamte Liste als solche im Speicher liegen muss. Für das oben genannte Beispiel bedeutet dies, dass wir zwar die Zahlen von 0 bis 9 verarbeiten, die Liste [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] aber zu keiner Zeit benötigen.

Dieses Prinzip wird nun verallgemeinert, um beliebige Sequenzen von Objekten, die nicht alle zusammen im Speicher stehen müssen, mithilfe von Schleifen durchlaufen zu können. Beispielsweise möchten wir über die ersten n Quadratzahlen iterieren.

An dieser Stelle kommen die sogenannten Generatoren ins Spiel. Ein Generator ist eine Funktion, die beim Aufruf ein iterierbares Objekt erzeugt, welches der Reihe nach die Elemente einer virtuellen[ 103 ](Mit »virtuell« ist gemeint, dass diese Sequenz zu keiner Zeit komplett im Speicher abgelegt werden muss und trotzdem durchlaufen werden kann. ) Sequenz liefert. Für unser Beispiel bräuchten wir also einen Generator, der nacheinander die ersten n Quadratzahlen zurückgibt. Die Definition dieser auch Generatorfunktionen genannten Konstrukte ist der von normalen Funktionen ähnlich. Der von uns benötigte Generator lässt sich folgendermaßen implementieren:

def square_generator(n):
    i = 1
    while i <= n:
        yield i*i
        i += 1

Mit diesem Generator können wir nun auf elegante Weise die ersten zehn Quadratzahlen auf dem Bildschirm ausgeben:

>>> for i in square_generator(10):
...     print(i, end=" ")
1 4 9 16 25 36 49 64 81 100

Der Funktionsaufruf square_generator(10) gibt ein iterierbares Objekt (die generator-Instanz) zurück, das mit einer for-Schleife durchlaufen werden kann.

>>> square_generator(10)
<generator object square_generator at 0x7feb157ebbf8>

Der Knackpunkt bei Generatoren liegt in der yield-Anweisung, mit der wir die einzelnen Werte der virtuellen Sequenz zurückgeben. Die Syntax von yield unterscheidet sich dabei nicht von der der return-Anweisung und muss deshalb nicht weiter erläutert werden. Entscheidend ist, wie yield sich im Vergleich zu return auf die Verarbeitung des Programms auswirkt.

Wird in einer normalen Funktion während eines Programmlaufs ein return erreicht, wird der Kontrollfluss an die nächsthöhere Ebene zurückgegeben und der Funktionslauf beendet. Außerdem werden alle lokalen Variablen der Funktion wieder freigegeben. Bei einem erneuten Aufruf der Funktion würde Python wieder am Anfang der Funktion beginnen und die komplette Funktion erneut ausführen.

Im Gegensatz dazu werden beim Erreichen einer yield-Anweisung die aktuelle Position innerhalb der Generatorfunktion und ihre lokalen Variablen gespeichert, und es erfolgt ein Rücksprung in das aufrufende Programm mit dem hinter yield angegebenen Wert. Beim nächsten Iterationsschritt macht Python dann hinter dem zuletzt ausgeführten yield weiter und kann wieder auf die alten lokalen Variablen, in dem Fall i und n, zugreifen. Erst wenn das Ende der Funktion erreicht wird, beginnen die endgültigen Aufräumarbeiten.

Generatoren können durchaus mehrere yield-Anweisungen enthalten:

def generator_mit_mehreren_yields():
    a = 10
    yield a
    yield a*2
    b = 5
    yield a+b

Auch dieser Generator kann mit einer for-Schleife durchlaufen werden:

>>> for i in generator_mit_mehreren_yields():
...     print(i, end=" ")
10 20 15

Im ersten Iterationsschritt wird die lokale Variable a in der Generatorfunktion angelegt und ihr Wert dann mit yield a an die Schleife übergeben. Beim nächsten Schleifendurchlauf wird dann bei yield a*2 weitergemacht, wobei die zurückgegebene 20 zeigt, dass der Wert von a tatsächlich zwischen den Aufrufen erhalten geblieben ist. Während des letzten Iterationsschritts erzeugen wir zusätzlich die lokale Variable b mit dem Wert 5 und geben die Summe von a und b an die Schleife weiter, wodurch die 15 ausgegeben wird. Da nun das Ende der Generatorfunktion erreicht ist, bricht die Schleife nach drei Durchläufen ab.

Es ist auch möglich, eine Generatorfunktion frühzeitig zu verlassen, wenn dies erforderlich sein sollte. Um dies zu erreichen, verwenden Sie die return-Anweisung ohne Rückgabewert. Der folgende Generator erzeugt abhängig vom Wert des optionalen Parameters auch_jungen eine Folge aus zwei Mädchennamen oder zwei Mädchen- und Jungennamen:

def namen(auch_jungen=True):
    yield "Carina"
    yield "Lina"
    if not auch_jungen:
        return
    yield "Phillip"
    yield "Sven"

Mithilfe der Built-in Function list können wir aus den Werten des Generators eine Liste erstellen, die entweder nur "Carina" und "Lina" oder zusätzlich "Phillip" und "Sven" enthält:

>>> list(namen())
['Carina', 'Lina', 'Phillip', 'Sven']
>>> list(namen(False))
['Carina', 'Lina'] 

 

23.2.1    Subgeneratoren 

Ein Generator kann die Kontrolle an einen anderen Generator abgeben. Dadurch wird es möglich, Teile eines Generators in separate Generatoren auszulagern. Beispielsweise können wir den Generator namen aus dem vorangegangenen Abschnitt in die beiden Subgeneratoren jungen und maedchen aufspalten.

def jungen():
    yield "Phillip"
    yield "Sven"

def maedchen():
    yield "Carina"
    yield "Lina"

def namen(auch_jungen=True):
    yield from maedchen()
    if auch_jungen:
        yield from jungen()

Der neue Generator namen verhält sich genau wie die Version ohne Subgeneratoren.

>>> list(namen())
['Carina', 'Lina', 'Phillip', 'Sven']
>>> list(namen(False))
['Carina', 'Lina']

Beachten Sie, dass die Werte, die ein Subgenerator erzeugt, direkt an die aufrufende Ebene durchgereicht werden. Der delegierende Generator hat keinen Zugriff auf diese Werte. Im Beispiel werden die Namen Carina, Lina, Phillip und Sven von den Generatoren maedchen und jungen direkt in die resultierende Liste geschrieben, ohne dass der Generator namen sie zu Gesicht bekommt. Um Daten an den delegierenden Generator zurückzugeben, verwenden Sie die return-Anweisung. Die yield from-Anweisung nimmt dabei nach dem Durchlaufen des Subgenerators den zurückgegebenen Wert an. Als Beispiel erweitern wir die beiden Subgeneratoren jungen und maedchen, sodass sie die Anzahl der jeweiligen Namen per return zurückgeben.

def jungen():
    yield "Phillip"
    yield "Sven"
    return 2

def maedchen():
    yield "Carina"
    yield "Lina"
    return 2

def namen(auch_jungen=True):
    anzahl_maedchen = (yield from maedchen())
    print("{} Mädchen".format(anzahl_maedchen))
    if auch_jungen:
        anzahl_jungen = (yield from jungen())
        print("{} Jungen".format(anzahl_jungen))

Nun gibt der Generator namen die jeweiligen Anzahlen mit print aus.

>>> list(namen())
2 Mädchen
2 Jungen
['Carina', 'Lina', 'Phillip', 'Sven']

Traversieren eines Binärbaums mit Subgeneratoren

Ein praxisnäheres Beispiel für Subgeneratoren ist die Traversierung eines Binärbaums. Ein Binärbaum ist eine Datenstruktur, die sich aus einer baumartigen Verkettung von Knoten zusammensetzt. Jeder Knoten hat dabei einen Wert und kann ein linkes oder rechtes Kind haben, die jeweils wieder Knoten sind. Ein Beispiel für einen Binärbaum zeigt Abbildung 23.1.

Abbildung 23.1    Ein Binärbaum

Bei der Traversierung des Baums werden der Reihe nach alle Knoten durchlaufen. Dies lässt sich beispielsweise durch die sogenannte In-Order-Traversierung erreichen. Dabei wird an einem Knoten zuerst der linke Teilbaum durchlaufen, dann der Wert des Knotens selbst ausgegeben und anschließend der rechte Teilbaum durchlaufen. Dies lässt sich durch die folgende Klasse Knoten realisieren, die eine Methode traversiere besitzt.

class Knoten:
    def __init__(self, wert, links=None, rechts=None):
        self.links = links
        self.wert = wert
        self.rechts = rechts

    def traversiere(self):
        if self.links:
            for k in self.links.traversiere():
                yield k
        yield self.wert
        if self.rechts:
            for k in self.rechts.traversiere():
                yield k

Die beiden for-Schleifen in der Generatormethode traversiere durchlaufen die Werte der linken und rechten Teilbäume und greifen dazu rekursiv auf die Generatormethode traversiere des jeweiligen Teilbaums zurück. Hier kann nun explizit mit yield from die Kontrolle abgegeben werden, sodass die Methode traversiere sich folgendermaßen umschreiben lässt:

def traversiere(self):
    if self.links:
        yield from self.links.traversiere()
    yield self.wert
    if self.rechts:
        yield from self.rechts.traversiere()

Den Beispielbaum aus Abbildung 23.1 können wir nun aufbauen und traversieren.

bl_ = Knoten(links=Knoten(12), wert=1, rechts=Knoten(3))
bl = Knoten(links=bl_, wert=5, rechts=Knoten(6))

br_ = Knoten(links=Knoten(2), wert=8)
br = Knoten(links=Knoten(9), wert=7, rechts=br_)

baum = Knoten(links=bl, wert=11, rechts=br)
print(list(baum.traversiere()))

Als Ausgabe erhalten wir eine Liste aller Knoten des Baums:

[12, 1, 3, 5, 6, 11, 9, 7, 2, 8]

 

23.2.2    Generator Expressions 

In Abschnitt 23.1.1 haben Sie List Comprehensions kennengelernt, mit denen Sie auf einfache Weise Listen erzeugen können. Beispielsweise erzeugt die folgende List Comprehension eine Liste mit den ersten zehn Quadratzahlen:

>>> [i*i for i in range(1, 11)]
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Wenn wir nun die Summe dieser ersten zehn Quadratzahlen bestimmen wollen, können wir das mithilfe der Built-in Function sum erreichen, indem wir schreiben:

>>> sum([i*i for i in range(1, 11)])
385

So weit, so gut. Allerdings wird hier eine nicht benötigte list-Instanz erzeugt, die Speicherplatz vergeudet.

Um auch in solchen Fällen nicht auf den Komfort von List Comprehensions verzichten zu müssen, gibt es Generator Expressions. Generator Expressions sehen genauso aus wie die entsprechenden List Comprehensions, mit dem Unterschied, dass anstelle der eckigen Klammern [] runde Klammern () als Begrenzung verwendet werden. Damit können wir das oben dargestellte Beispiel speicherschonend mit einer Generator Expression formulieren:

>>> sum((i*i for i in range(1, 11)))
385

Die umschließenden runden Klammern können entfallen, wenn der Ausdruck sowieso schon geklammert ist. In unserem sum-Beispiel können wir also ein Klammernpaar entfernen:

>>> sum(i*i for i in range(1, 11))
385

Generatoren können Ihnen helfen, Ihre Programme sowohl in der Lesbarkeit als auch hinsichtlich der Ausführungsgeschwindigkeit zu verbessern. Immer dann, wenn Sie es mit einer komplizierten und dadurch schlecht lesbaren while-Schleife zu tun haben, sollten Sie prüfen, ob ein Generator die Aufgabe nicht eleganter übernehmen kann.

Wir haben uns in diesem Abschnitt auf die Definition von Generatoren und ihre Anwendung in der for-Schleife oder mit list beschränkt. Im folgenden Abschnitt werden Sie die Hintergründe und die technische Umsetzung kennenlernen, denn hinter den Generatoren und der for-Schleife steht das Konzept der Iteratoren.