NB_03_Generatoren¶
(c) 2025 Technische Hochschule Augsburg - Fakultät für Informatik - Prof.Dr.Nik Klever - Impressum
Generatoren¶
Grundlegendes¶
Generatoren sind ein einfaches und leistungsstarkes Werkzeug für die Erstellung von Iteratoren. Sie werden wie normale Funktionen geschrieben, aber verwenden den yield Ausdruck, wann immer Daten zurückgegeben werden. Jedes Mal, wenn next() aufgerufen wird, wird der Generator wieder aufgerufen, und läuft dort weiter, wo er beim letzten Mal die Berechnung aufgehört hat (d.h. der Generator merkt sich alle Daten und welche Anweisung zuletzt ausgeführt worden ist). Das folgende Beispiel zeigt, dass Generatoren trivial einfach zu erstellen sind:
def reverse(data):
for index in range(len(data)-1, -1, -1):
yield data[index]
for char in reverse('golf'):
print(char)
f l o g
Alles, was mit Generatoren möglich ist, kann auch mit klassenbasierten Iteratoren, wie im vorherigen Unterkapitel Iteratoren beschrieben, durchgeführt werden. Was Generatoren so kompakt macht, ist die automtische Erstellung der __iter__() und __next__()-Methoden.
Ein weiteres wichtiges Merkmal ist, dass die lokalen Variablen und der Ausführungszustand automatisch zwischen den Aufrufen gespeichert werden. Dies bedeutet, dass die Funktionen einfacher und klarer geschrieben werden können als ein Ansatz mit Instanzvariablen wie self.index und self.data.
Neben der automatischen Methodenerstellung und dem Speichern des Programmstatus, werfen Generatoren automatisch die Ausnahme StopIteration, wenn sie beendet werden. In der Kombination dieser Features können Iteratoren ohne Mehraufwand erstellt werden und sind vom Aufwand her mit dem Schreiben normaler Funktionen vergleichbar.
%%Mooc MoocStringAssessment
Generator Rückgabe
Mit welchem Ausdruck werden die Rückgabewerte von Generatorfunktionen zurückgegeben ?
Generator Ausdrücke¶
Einige einfache Generatoren können kurz und bündig als Ausdrücke mit einer Syntax ähnlich den List Comprehensions erstellt werden, jedoch mit runden Klammern anstelle von eckigen Klammern. Diese Ausdrücke sind für solche Situationen ausgelegt, in denen der Generator sofort in einer umgebenden Funktion verwendet wird. Generatorausdrücke sind kompakter, aber weniger vielseitig als normale Generatordefinitionen und neigen dazu, weniger Speicherbedarf als äquivalente List Comprehensions zu verbrauchen.
Beispiele:
x=sum(i*i for i in range(10)) # Summe der Quadrate
print(x)
285
xvec = [10, 20, 30]
yvec = [7, 5, 3]
x=sum(x*y for x,y in zip(xvec, yvec)) # Vektorprodukt
print(x)
260
Sinus-Tabelle als Dictionary, erstellt als Generator-Ausdruck
from math import pi, sin
sine_table = {x:sin(x*pi/180) for x in range(0, 46)}
print(sine_table)
{0: 0.0, 1: 0.01745240643728351, 2: 0.03489949670250097, 3: 0.05233595624294383, 4: 0.0697564737441253, 5: 0.08715574274765817, 6: 0.10452846326765346, 7: 0.12186934340514748, 8: 0.13917310096006544, 9: 0.15643446504023087, 10: 0.17364817766693033, 11: 0.1908089953765448, 12: 0.20791169081775931, 13: 0.224951054343865, 14: 0.24192189559966773, 15: 0.25881904510252074, 16: 0.27563735581699916, 17: 0.29237170472273677, 18: 0.3090169943749474, 19: 0.32556815445715664, 20: 0.3420201433256687, 21: 0.35836794954530027, 22: 0.374606593415912, 23: 0.3907311284892737, 24: 0.40673664307580015, 25: 0.42261826174069944, 26: 0.4383711467890774, 27: 0.45399049973954675, 28: 0.4694715627858908, 29: 0.48480962024633706, 30: 0.49999999999999994, 31: 0.5150380749100542, 32: 0.5299192642332049, 33: 0.5446390350150271, 34: 0.5591929034707469, 35: 0.573576436351046, 36: 0.5877852522924731, 37: 0.6018150231520483, 38: 0.6156614753256582, 39: 0.6293203910498374, 40: 0.6427876096865393, 41: 0.6560590289905072, 42: 0.6691306063588582, 43: 0.6819983600624985, 44: 0.6946583704589973, 45: 0.7071067811865475}
Sinus-Tabelle als Liste, erstellt als List Comprehension
hier notwendig für die Verwendung mit pygal
from math import pi, sin
from pygal import XY
from IPython.display import SVG
sine_table = [(x,sin(x*pi/180)) for x in range(0, 361)]
xy = XY()
xy.add('y = sin(x pi/180)', sine_table)
SVG(xy.render())
page = """Dies ist ein aus mehreren
Zeilen bestehender
Text aus Wörtern mit mehreren
leeren Zeilen dazwischen
Dies ist ein aus mehreren Wörtern
bestehender Text"""
unique_words = set(word.lower() for line in page.split('\n') for word in line.split())
print(unique_words)
{'mit', 'ein', 'wörtern', 'zeilen', 'aus', 'bestehender', 'leeren', 'dies', 'ist', 'dazwischen', 'mehreren', 'text'}
absolventen = [(1.4,"Elisabeth"),(1.7,"Friedrich"),(1.5,"Winnifred")]
abschlussredner = min((student[0], student[1]) for student in absolventen)
print(abschlussredner)
(1.4, 'Elisabeth')
data = 'golf'
x=list(data[i] for i in range(len(data)-1, -1, -1))
print(x)
['f', 'l', 'o', 'g']
Generatorausdrücke und List Comprehensions im Vergleich¶
Zwei allgemein verbreitete Operationen bei der Rückgabe eines Iterators sind
- Durchführung irgendeiner Operation an jedem Element,
- Auswählen einer Teilmenge von Elementen, die eine bestimmte Bedingung erfüllen.
Wenn man zum Beispiel aus einer Liste von Strings alle in einer Zeile nachfolgenden Leerzeichen entfernen will oder alle Strings mit einem bestimmten Teilstring extrahieren will.
List Comprehensions und Generatorausdrücke (Kurzform: "listcomps" und "genexps") sind eine prägnante Notation für solche Operationen, diese Begriffe sind von der funktionalen Programmiersprache Haskell ausgeliehen.
Das folgende Beispiel verwirft alle Leerzeichen aus einem String von Strings:
line_list = [' line 1\n', 'line 2 \n', '\n']
# Generator Ausdruck -- gibt einen Iterator zurück
stripped_iter = (line.strip() for line in line_list)
# List Comprehension -- gibt eine Liste zurück
stripped_list = [line.strip() for line in line_list]
Es können nur bestimmte Elemente ausgewählt werden, indem eine "if" Bedingung hinzugefügt wird:
stripped_list = [line.strip() for line in line_list if line != ""]
Mit einer List Comprehension wird eine Liste zurückgegeben; stripped_list ist eine Liste mit den resultierenden Zeilen, kein Iterator. Generatorausdrücke geben einen Iterator zurück, der die Werte nach Bedarf berechnet und nicht alle Werte sofort realisieren muss. Dies bedeutet, dass List Comprehensions nicht sinnvoll sind, wenn mit Iteratoren gearbeitet wird, die einen unendlichen Datenstrom oder eine sehr große Menge an Daten zurückgeben. Generatorausdrücke sind in diesen Situationen vorzuziehen.
Generatorausdrücke sind von runden Klammern (()) und List Comprehensions von eckigen Klammern ([]) umgeben. Generatorausdrücke haben die Form:
( expression for expr in sequence1
if condition1
for expr2 in sequence2
if condition2
for expr3 in sequence3 ...
if condition3
for exprN in sequenceN
if conditionN )Nochmal, bei einer List Comprehension sind nur die äußeren Klammern unterschiedlich (eckige Klammern statt runde Klammern).
Die Elemente der berechneten Rückgabe sind die aufeinanderfolgenden Werte des Generatorausdrucks. Die if-Bedingungen sind alle optional; Wenn sie jedoch vorhanden sind, wird der Ausdruck nur ausgewertet und dem Ergebnis hinzugefügt, wenn die Bedingung wahr ist.
Generatorausdrücke müssen immer in runden Klammern geschrieben werden, aber die Klammern, die einen Funktionsaufruf signalisieren, zählen auch. Wenn also ein Iterator erstellt werden soll, der sofort an eine Funktion weitergegeben wird, kann dies wie in dem folgenden Code geschrieben werden:
obj_total = sum(len(obj) for obj in line_list)
print(obj_total)
19
Die for ... in Audrücke enthalten die zu iterierenden Sequenzen. Die Sequenzen müssen nicht die gleiche Länge haben, weil sie von links nach rechts und nicht parallel iteriert werden. Für jedes Element von sequence1 wird sequence2 von Anfang an durchlaufen. sequence3 wird dann für jedes resultierende Paar von Elementen aus sequence1 und sequence2 durchlaufen.
Um es anders auszudrücken, eine List Comprehension oder ein Generatorausdruck entspricht dem folgenden Python-Code:
for expr1 in sequence1:
if not (condition1):
continue # Skip this element
for expr2 in sequence2:
if not (condition2):
continue # Skip this element
...
for exprN in sequenceN:
if not (conditionN):
continue # Skip this element
# letztendlich die Rückgabe
# des durch die Ausdrücke berechneten WertesDies bedeutet, dass, wenn es mehrere for ... in Ausdrücke aber keine if-Bedingungen gibt, die Länge der resultierenden Ausgabe gleich dem Produkt der Längen aller Sequenzen ist. Wenn also zwei Listen der Länge 3 verwendet werden, ist die letztendlich die Ergebnisliste 9 Elemente lang:
seq1 = 'abc'
seq2 = (1,2,3)
z=[(x, y) for x in seq1 for y in seq2]
print(z)
[('a', 1), ('a', 2), ('a', 3), ('b', 1), ('b', 2), ('b', 3), ('c', 1), ('c', 2), ('c', 3)]
Um eine Mehrdeutigkeit in Pythons Grammatik zu vermeiden, muss ein Ausdruck mit Klammern umgeben sein, wenn der Ausdruck ein Tupel erzeugt. Die erste List Comprehension unten erzeugt einen Syntaxfehler, während die zweite korrekte Syntax enthält:
# Syntax error
[x, y for x in seq1 for y in seq2]
File "<ipython-input-15-6dbecc282361>", line 2 [x, y for x in seq1 for y in seq2] ^ SyntaxError: invalid syntax
# Correct
[(x, y) for x in seq1 for y in seq2]
[('a', 1),
('a', 2),
('a', 3),
('b', 1),
('b', 2),
('b', 3),
('c', 1),
('c', 2),
('c', 3)]
%%Mooc MoocMultipleChoiceAssessment
Generatorausdruck
Mit welchem Klammern werden Generatorausdrücke erstellt ?
Vertiefung¶
Generatoren sind eine spezielle Klasse von Funktionen, die das Schreibens von Iteratoren vereinfachen. Normale Funktionen berechnen einen Wert und geben diesen Wert zurück, Generatoren dagegen geben einen Iterator zurück, der einen Strom von Werten zurückgibt.
Wenn eine normale Funktion aufgerufen wird, bekommt sie einen privaten Namensraum, in dem die lokalen Variablen erstellt werden. Wenn die Funktion eine return-Anweisung erreicht, werden die lokalen Variablen zerstört und der Rückgabewert wird an den Aufrufer der Funktion zurückgegeben. Ein späterer Aufruf der gleichen Funktion erzeugt einen neuen privaten Namensraum und einen neuen Satz von lokalen Variablen. Aber wie wäre es, wenn die lokalen Variablen nicht weggeworfen werden, wenn die Funktion verlassen wird ? Was wäre, wenn die Funktion später wieder aufgenommen werden könnte. Dies ist, was Generatoren bieten; sie können als wiederaufgenommene Funktionen gedacht werden.
Hier ist ein weiteres einfaches Beispiel für eine Generatorfunktion:
def generate_ints(N):
for i in range(N):
yield i
Jede Funktion, die das Schlüsselwort yield enthält, ist eine Generatorfunktion; Dies wird durch den Bytecode-Compiler von Python erkannt, der die Funktion daraufhin speziell behandelt und kompiliert.
Wenn eine Generatorfunktion aufgerufen wird, gibt sie keinen einzelnen Wert zurück. Stattdessen gibt sie ein Generatorobjekt zurück, welches das Iteratorprotokoll unterstützt. Bei der Ausführung des yield Ausdrucks gibt der Generator den Wert von i aus, ähnlich einer return-Anweisung. Der große Unterschied zwischen yield und return ist, dass bei Erreichen des yield-Ausdrucks der Zustand des Generators vorübergehend schlafend gelegt wird und die lokalen Variablen erhalten bleiben. Beim nächsten Aufruf der Methode __next__() des Generators wird die Funktion an dieser Stelle fortgesetzt.
Hier ist eine beispielhafte Nutzung des obigen Generators generate_ints ():
gen = generate_ints(3)
gen
<generator object generate_ints at 0x7efdf2d21ba0>
next(gen)
0
next(gen)
1
next(gen)
2
next(gen)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-24-8a6233884a6c> in <module>() ----> 1 next(gen) StopIteration:
Man könnte dafür aber auch gleich
for i in generate_ints(5):
print(i)
0 1 2 3 4
oder
a,b,c = generate_ints(3)
print(a,b,c)
0 1 2
schreiben.
Innerhalb einer Generatorfunktion bewirkt ein return value-Ausdruck, dass die Ausnahme StopIteration(value) von der Methode __next__() geworfen wird. Sobald dies geschieht oder das Ende der Funktion erreicht ist, endet die Verarbeitung der Werte und der Generator kann keine weiteren Werte zurückliefern.
Der Effekt von Generatoren kann manuell durch das Schreiben einer eigenen Klasse und das Speichern aller lokalen Variablen des Generators als Instanzvariable erreicht werden. Zum Beispiel könnte eine Liste von Zahlen zurückgegeben werden, indem self.count initial auf 0 gesetzt wird und die __next__()-Methode self.count inkrementiert und zurückgibt. Jedoch kann für einen mäßig komplizierten Generator das Schreiben einer entsprechenden Klasse viel aufwändiger sein.
Die Test-Suite, die in der Python-Bibliothek im Ordner lib/test/test_generators.py enthalten ist, enthält eine Reihe von interessanten Beispielen. Zwei Beispiele in dem Modul test_generators.py produzieren Lösungen für das N-Queens-Problem (Platzierung von N-Königinnen auf einem NxN-Schachbrett, so dass keine Königin eine andere bedroht) und die Ritter-Tour (eine Route finden, die einen Ritter auf jedes Quadrat eines NxN-Schachbretts bringt ohne das Quadrat zweimal zu besuchen). Als weiteres Beispiel daraus ein Generator, der eine In-Order-Durchquerung eines Baumes mit Generatoren rekursiv implementiert:
%%Mooc MoocStringAssessment
Rückgabewert einer Generatorfunktion
Von welchem Typ ist der Rückgabewert einer Generatorfunktion ?
Rekursiver Generator inorder¶
Der rekursive Generator inorder erzeugt die Blätter eines Binär-Baumes in normaler Reihenfolge (d.h. von links nach rechts (l-r, in-order)) erzeugt:
def inorder(t):
if t:
for x in inorder(t.left):
yield x
yield t.label
for x in inorder(t.right):
yield x
Hier genutzt von der Beispielklasse Tree:
class Tree:
def __init__(self, label, left=None, right=None):
self.label = label
self.left = left
self.right = right
def __repr__(self, level=0, indent=" "):
s = level*indent + repr(self.label)
if self.left:
s = s + "\n" + self.left.__repr__(level+1, indent)
if self.right:
s = s + "\n" + self.right.__repr__(level+1, indent)
return s
def __iter__(self):
return inorder(self)
def graph(self, nodes={}, level=0):
if not nodes:
nodes = {level:[self]}
elif level in nodes:
nodes[level].append(self)
else:
nodes[level] = [self]
if self.left:
self.left.graph(nodes, level+1)
if self.right:
self.right.graph(nodes, level+1)
return nodes
Ein Baum wird aus einer Liste erzeugt, dabei wird die Mitte der Liste gesucht (mit dem // (Floor)-Operator wird die Länge der Liste durch 2 geteilt) und das Element an dieser Stelle als Wurzel des (Teil-)Baums verwendet, durch dieses Element wird die Liste in eine linke und eine rechte Teil-Liste geteilt. Eine Instanz dieses Baums wird durch dieses Wurzelelement und die beiden Teilbäume erzeugt (siehe den Rückgabewert der Funktion tree).
Letztendlich ist damit jedes Element der Liste als Instanz der Klasse Tree erzeugt worden.
def tree(list):
n = len(list)
if n == 0:
return []
i = n // 2
return Tree(list[i], tree(list[:i]), tree(list[i+1:]))
Mit dem Aufruf der Funktion tree wird letztendlich eine Instanz t der Klasse Tree erstellt, über die wiederum mittels der Attribute left und right die beiden Teilbäume erreicht werden:
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
print(t)
'N'
'G'
'D'
'B'
'A'
'C'
'F'
'E'
'K'
'I'
'H'
'J'
'M'
'L'
'U'
'R'
'P'
'O'
'Q'
'T'
'S'
'X'
'W'
'V'
'Z'
'Y'
Mit der __iter__()-Funktion wird nun der Generator inorder() aufgerufen, der den Baum in Links-Rechts-Reihenfolge durchläuft und jeweils den Blattknoten ausgibt:
for x in t:
print(x,end="")
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Besser als in der obigen Ausgabe ist die folgende Darstellung des Baumes mit der Ausgabe der Astebene (level) und den Wurzeln der linken (<-) und rechten (->) Teilbäume:
nodesdict=t.graph()
for level in nodesdict:
for node in nodesdict[level]:
if node.left and node.left.label:
l="{}<-".format(node.left.label)
else:
l=" "
m=node.label
if node.right and node.right.label:
r="->{}".format(node.right.label)
else:
r=" "
print("{}: {}{}{}".format(level,l,m,r))
0: G<-N->U 1: D<-G->K 1: R<-U->X 2: B<-D->F 2: I<-K->M 2: P<-R->T 2: W<-X->Z 3: A<-B->C 3: E<-F 3: H<-I->J 3: L<-M 3: O<-P->Q 3: S<-T 3: V<-W 3: Y<-Z 4: A 4: C 4: E 4: H 4: J 4: L 4: O 4: Q 4: S 4: V 4: Y
Noch besser aber die graphische Darstellung des Baums:
# Graphische Aufbereitung der A-Z Liste als Baum
Übergabe von Parametern an einen Generator¶
In Python 2.5 there’s a simple way to pass values into a generator. yield became an expression, returning a value that can be assigned to a variable or otherwise operated on:
Seit Python 2.5 gibt es einen einfachen Weg, um irgendwelche Werte an einen Generator zu übergeben. yield wurde ein Ausdruck, der einen Wert zurückgeben kann, der einer Variablen zugeordnet oder anderweitig verwendet werden kann:
val = (yield i)Es ist empfehlenswert, immer runde Klammern um den yield-Ausdruck zu setzen, wenn irgendetwas mit dem zurückgegebenen Wert wie im obigen Beispiel gemacht werden soll. Die Klammern sind nicht immer notwendig, aber es ist einfacher, sie immer hinzuzufügen, anstatt sich zu erinnern, wann sie gebraucht werden.
PEP 342 erklärt die genauen Regeln, dass ein yield-Ausdruck immer eingeklammert werden muss, außer wenn er auf der obersten Ebene auf der rechten Seite einer Zuordnung auftritt. Das bedeutet, dass man
val = yield ischreiben kann, aber man muss Klammern verwenden, wenn es eine Operation dazu gibt, wie in
val = (yield i) + 12Werte können dann an einen Generator übergeben werden, indem die send(value)-Methode aufgerufen wird. Diese Methode setzt den Code des Generators fort und der yield-Ausdruck gibt den angegebenen (gesendeten) Wert zurück. Wenn anschliessend regulär die __next__()-Methode aufgerufen wird, gibt yield None zurück.
Das folgende Beispiel ist ein einfacher Zähler, der jeweils um 1 erhöht, aber auch erlaubt den Wert des internen Zählers zu ändern.
def counter(maximum):
i = 0
while i < maximum:
val = (yield i)
# falls ein Wert übergeben worden ist, wird der Zähler geändert
if val is not None:
i = val
else:
i += 1
Und hier die Anwendung des Beispiels für eine Änderung des Zählers:
it = counter(10)
next(it)
0
next(it)
1
it.send(8)
8
next(it)
9
next(it)
--------------------------------------------------------------------------- StopIteration Traceback (most recent call last) <ipython-input-41-485c458c5f2b> in <module>() ----> 1 next(it) StopIteration:
Weil yield oft auch None zurückgibt, sollte dieser Fall immer abgeprüft werden. Die Übergabe eines Parameters an yield sollte daher nur dann verwendet werden, wenn sichergestellt ist, dass die send()-Methode die einzige Methode ist, die verwendet wird, um die entsprechende Generatorfunktion wieder aufzunehmen.
Zusätzlich zu send() gibt es zwei weitere Methoden bei Generatoren:
throw(type, value=None, traceback=None) wird verwendet, um eine Ausnahme innerhalb des Generators zu werfen; Die Ausnahme wird durch yield geworfen, während die Ausführung des Generators angehalten wird.
close() wirft eine GeneratorExit-Ausnahme innerhalb des Generators, um die Iteration zu beenden. Wenn der Generator diese Ausnahme erhält, dann muss der Generatorcode entweder GeneratorExit oder StopIteration werfen; Die Ausnahme abzufangen und etwas anderes zu tun ist illegal und wird einen RuntimeError auslösen. close() wird auch von Python's Garbage Collector aufgerufen, wenn der Generator alle vorhandenen Variablen als Müll sammelt und zerstört (Garbage Collection).
Wenn nach dem Auftritt einer GeneratorExit-Ausnahme aufgeräumt werden muss, dann sollte statt des Abfangens der GeneratorExit-Ausnahme eher ein try: ... finally: Ausdruck verwendet werden.
Die kumulative Wirkung dieser Veränderungen ist es, Generatoren von Einwegproduzenten von Informationen in Produzenten und Konsumenten zu verwandeln.
Generatoren können auch zu Coroutinen werden, einer allgemeinere Form von Subroutinen. Subroutinen werden an einem Punkt aufgerufen und an einem anderen Punkt (am Ende der Funktion bzw. einer return-Anweisung) verlassen, aber Coroutinen können aufgerufen, verlassen und an vielen verschiedenen Punkten (den yield Anweisungen) wieder aufgenommen werden.
%%Mooc Video
Weitere Literatur¶
%%Mooc WebReference
Generators
https://docs.python.org/3/tutorial/classes.html#generators-expressions
Hinweis: Einführung in Generatoren
%%Mooc WebReference
Generators
https://docs.python.org/3/howto/functional.html#generators
Hinweis: Weitere Informationen zu Generatoren