(c) 2023 Technische Hochschule Augsburg - Fakultät für Informatik - Prof.Dr.Nik Klever - Impressum
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
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']
Zwei allgemein verbreitete Operationen bei der Rückgabe eines Iterators sind
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
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
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=