Iteratoren und Generatoren in Python

Eine Folge ist in der Mathematik eine Auflistung von endlich oder unendlich vielen fortlaufend nummerierten Objekten (beispielsweise Zahlen). Nur, wie gehen wir praktisch in Python mit dieser Unendlichkeit um? Und könnte uns das Prinzip auch anderweitig weiterhelfen?

Wir möchten wiederverwendbaren Code schreiben, der die Fibonacci-Folge generiert. Zur Erinnerung: die Fibonacci-Folge beginnt mit den Werten 1 und 1 (oder 0 und 1), der nächste Wert ergibt sich immer aus der Summe der beiden vorherigen.

Unser erster Versuch: Schreibe eine Funktion, die die ersten n Elemente der Fibonacci-Folge generiert und in einer Liste zurückgibt. Untenstehender Code funktioniert nur für $n\le10$ – ändere den Code so, dass er für beliebig grosse $n$ das richtige Resultat zurückgibt!

def fibonacci(n=10): first_few = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] result = [] for i in range(n): result.append(first_few[i]) return result print(fibonacci(10))

def fibonacci(n=10):
    result = []
    one = 0
    two = 1
    for i in range(n):
        # Python erlaubt Zuweisungen von Tupeln -
        # natürlich lässt sich die Zuweisung auch auf
        # mehrere Zeilen verteilen.
        one, two = two, one + two
        result.append(one)
    return result
 
print(fibonacci(10))

Das Problem ist nur, dass die Liste viel Speicher benötigt, wenn wir eine grosse Anzahl Elemente benötigen. Beispiel: wir möchten die Summe der ersten n Fibonacci-Zahlen berechnen, ohne den Speicherplatz für die Liste aufzuwenden. Oder wir wissen gar nicht im Voraus, wieviele Elemente nötig sind, wenn wir zum Beispiel die erste Fibonacci-Zahl grösser als 1000 suchen.

Natürlich könnten wir für beide Probleme eine eigene, effiziente Funktion schreiben, die ohne Liste auskommt - aber als faule Informatiker:innen möchten wir es vermeiden, den gleichen Code zweimal zu schreiben…

Gesucht ist also ein Stück Code, das einen Strom von Fibonacci-Zahlen liefert, die wir kontinuierlich konsumieren können, bis wir genug haben.

Solche Strom-Objekte heissten Iteratoren. Ein Iterator hat nur eine einzige Funktion, __next__, die jeweils das nächste Element zurückgibt. Der Iterator muss sich irgendwie den Zustand merken, also wo in der Fibonacci-Folge er gerade steckt. Die Funktion wirft eine StopIteration Exception wenn es keine weiteren Elemente gibt.

Die built-in function next kann verwendet werden, um aus einem Iterator das nächste Element zu holen.

Analysiere den untenstehenden Code und führe ihn aus. Ändere den Code, so dass die erste Fibonacci Zahl ausgegeben wird, die grösser als 1000 ist!

class FiboIterator: def __init__(self, limit = -1): # Constructor - hier wird der Initial-Zustand gespeichert self.one = 0 self.two = 1 self.limit = limit def __next__(self): if self.limit == 0: raise StopIteration() self.one, self.two = self.two, self.one + self.two self.limit -= 1 return self.one iterator = FiboIterator() print(next(iterator)) print(next(iterator)) print(next(iterator))

iterator = FiboIterator()
res = 0
count = 0
while res < 1000:
    res = next(iterator)  # Die eingebaute Funktion next ruft __next__ auf.
    count += 1
print(f'Erste Fibonacci-Zahl grösser als 1000 ist {res} (#{count})')

Möchten wir unseren Iterator in einer for-Schleife einsetzen, müssen wir zusätzlich das Iterable-Protokoll beachten: Iterables müssen eine __iter__ Funktion haben, die einen neuen, von vorne beginnenden Iterator zurückgibt. Wieso benötigen wir sowohl Iterable als auch Iterator? Stell dir vor, eine Liste möchte das Iterable-Protokoll implementieren - es ist entscheidend, dass jede neue Schleife wieder von vorne beginnt:

alphabet = 'abcdef'
for letter1 in alphabet:      # Erster Iterator über die Sequence alphabet
    for letter2 in alphabet:  # Zweiter, unabhängiger Iterator über die gleiche Sequence
        print(letter1 + letters)

Spickzettel:

• __iter__ wird einmal aufgerufen, wenn die for-Schleife startet, und gibt einen neuen Iterator zurück.
• __next__ wird vor jedem Schleifendurchgang aufgerufen und das Resultat der Schleifenvariable zugewiesen.

Die Funktionen werden hier beschrieben.

Untenstehender Code fügt dem bestehenden Iterator ein Iterable hinzu, so dass wir eine for-Schleife nützen können:

class FiboIterator: def __init__(self, limit = -1): # Hier wird der Zustand gespeichert self.one = 0 self.two = 1 self.limit = limit def __next__(self): if self.limit == 0: raise StopIteration() self.one, self.two = self.two, self.one + self.two self.limit -= 1 return self.one class FiboIterable: # Wird einmal aufgerufen, wenn Python die for-Schleife startet. def __iter__(self): return FiboIterator() sequence = FiboIterable() for num in sequence: if num > 1000: print(f'Erste Fibonacci-Zahl grösser als 1000 ist {num}') break

Die Funktionen __iter__ und __next__ dürfen auch von derselben Klasse implementiert werden.

Das ganze leuchtet ein, aber ist ziemlich kompliziert. Zu Glück hat Python eine Abkürzung für uns bereit: Sobald unsere Funktion yield statt return verwendet, erzeugt Python automatisch einen Generator, d.h. ein Objekt, das sowohl Iterator als auch Iterable ist und sich den ganzen Zustand der Funktion merkt, wenn ein Element mit yield zurückgegeben wird.

Die erzeugte __next__ Funktion setzt die Ausführung beim wiederholten Aufruf dort fort, wo das letzte yield erfolgt ist.

Ein Generator ist ein Iterable und kann damit auch als Ausdruck nach in in einer for ... in <expression> stehen.

def fibo(): one = 0 two = 1 while True: one, two = two, one + two yield one for num in fibo(): if num > 1000: print(f'Erste Fibonacci-Zahl grösser als 1000 ist {num}') break

Sind keine Elemente mehr übrig, wird einfach nichts zurückgegeben bzw. ein normales return.

Verändere den obigen Code um ein optionales Limit einzubauen, wieviele Elemente erzeugt werden sollen.

Der folgende Code soll also 143 ausgeben:

def fibo(limit=-1): pass n=10 print(f'Summe der ersten {n} Fibonacci-Zahlen: {sum(fibo(n))}')

Manchmal möchten wir eine andere Iteration (bzw. einen anderen Generator) in die gerade laufende Iteration einbinden. Dazu dienen die Keywords yield from.

Beispiel: ein einfacher Binärbaum besteht aus Knoten (en: Nodes), die jeweils bis zu zwei Kinder haben können.

Um den Baum zu traversieren (d.h. alle Knoten zu besuchen), können wir zum Beispiel die In-Order Traversierung wählen: Zuerst wird der linke Teilbaum durchlaufen, anschliessend der Knoten selbst, zum Schluss der rechte Teilbaum.

Eine rekursive Umsetzung könnte wie folgt aussehen - beachte, wie yield from eingesetzt wird, um die rekursive Traversierung zu erreichen.

class Node: def __init__(self, key, left=None, right=None): self.key = key self.left = left self.right = right def in_order_traversal(self): if self.left: yield from self.left.in_order_traversal() yield self if self.right: yield from self.right.in_order_traversal() tree = Node(5, Node(1), Node(7)) for node in tree.in_order_traversal(): print (node.key)

Füge eine Methode pre_order_traversal hinzu, die zuerst jeweils den Knoten selbst, dann den linken und rechten Teilbaum besucht. Die Reihenfolge des Besuchs sollte also 5 1 7 ausgeben.

Zurück zum Graph Walk in den Graphenalgorithmen - implementiere einen Depth-First Graph Walk mit deinem Wissen über Generators und yield bzw. yield from.