# Iteratoren und Generatoren in Python Eine [[wpde>Folge_(Mathematik)|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? ## Die Fibonacci-Folge Wir möchten wiederverwendbaren Code schreiben, der die [[wpde>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. ### Aufgabe 1: Fibonacci-Liste 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)) ++++Lösung| 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. ## Iteratoren 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](https://docs.python.org/3/library/functions.html#next) kann verwendet werden, um aus einem Iterator das nächste Element zu holen. ### Aufgabe 2: Fibonacci-Iterator 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)) ++++Lösung| 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})') ++++ ## Iterables 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](https://docs.python.org/3/library/stdtypes.html#iterator-types). 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. ## Yield 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 _[[wp>Generator_(computer_programming)|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 ` 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 ### Iteration beenden Sind keine Elemente mehr übrig, wird einfach nichts zurückgegeben bzw. ein normales `return`. ### Aufgabe 3: Limitieren 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))}') ## Yield From 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. {{:talit:generators:pasted:20240506-131941.png?nolink&400}} Um den Baum zu traversieren (d.h. alle Knoten zu besuchen), können wir zum Beispiel die [[wpde>Binärbaum#Traversierung|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) ### Aufgabe 4: Pre-Order Traversierung 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. ### Weiter? Zurück zum [[talit:algorithmen#aufgabe_4_-_graph_walk|Graph Walk]] in den Graphenalgorithmen - implementiere einen Depth-First Graph Walk mit deinem Wissen über Generators und `yield` bzw. `yield from`.