Iteratoren und Generatoren in Python [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
# Iteratoren und Generatoren in Python

<html><script type="module" src="https://bottom.ch/ksr/ed/bottom-editor.js"></script></html>
 
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!

<html><bottom-editor>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))</bottom-editor></html>

<nodisp 0>
++++Lösung|
<code python>
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))
</code>
++++
</nodisp>

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!

<html><bottom-editor>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))</bottom-editor></html>


<nodisp 0>
++++Lösung|
<code python>
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})')
</code>
++++
</nodisp>

## 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:

<code python>
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)
</code>

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:

<html><bottom-editor>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
</bottom-editor></html>

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 <expression>` stehen.

<html><bottom-editor>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
</bottom-editor></html>

### 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:

<html><bottom-editor>def fibo(limit=-1):
    pass

n=10
print(f'Summe der ersten {n} Fibonacci-Zahlen: {sum(fibo(n))}')
</bottom-editor></html>

## 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.

<html><bottom-editor>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)
</bottom-editor></html>

### 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`.