Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- talit:generators [2024-05-06 13:26] – [Aufgabe 3: In-Order Traversierung] hof
+++ talit:generators [2024-05-22 18:20] (aktuell) – hof
@@ Zeile 1: / Zeile 1: @@
 # 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?
@@ Zeile 9: / Zeile 11: @@
 ### 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.
+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!
-<nodisp 1>
+<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|
-<html><iframe frameborder="0" width="100%" style="height: 15lh;" allow="clipboard-write" src="https://tkilla77.github.io/python_editor_wasm/embed.html?code=def+fibonacci%28limit%3D10%29%3A%0A++++result+%3D+%5B%5D%0A++++one+%3D+0%0A++++two+%3D+1%0A++++for+i+in+range%28limit%29%3A%0A++++++++one%2C+two+%3D+two%2C+one+%2B+two%0A++++++++result.append%28one%29%0A++++return+result%0A%0Aprint%28fibonacci%2810%29%29
+<code python>
-"></iframe></html>
+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 frisst, 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.
+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 möchten wir es vermeiden, den gleichen Code zweimal zu schreiben...
+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.
@@ Zeile 26: / Zeile 50: @@
 ## Iteratoren
-Soche 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.
+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.
-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><iframe frameborder="0" width="100%" style="height: 25lh;" allow="clipboard-write" src="https://tkilla77.github.io/python_editor_wasm/embed.html?code=class+FiboIterator%3A%0A++++def+__init__%28self%2C+limit+%3D+-1%29%3A%0A++++++++%23+Hier+wird+der+Zustand+gespeichert%0A++++++++self.one+%3D+0%0A++++++++self.two+%3D+1%0A++++++++self.limit+%3D+limit%0A++++%0A++++def+__next__%28self%29%3A%0A++++++++if+self.limit+%3D%3D+0%3A%0A++++++++++++raise+StopIteration%28%29%0A++++++++self.one%2C+self.two+%3D+self.two%2C+self.one+%2B+self.two%0A++++++++self.limit+-%3D+1%0A++++++++return+self.one%0A%0Aiterator+%3D+FiboIterator%28%29%0Aprint%28next%28iterator%29%29%0Aprint%28next%28iterator%29%29%0Aprint%28next%28iterator%29%29
+<html><bottom-editor>class FiboIterator:
-"></iframe></html>
+    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 1>
+<nodisp 0>
 ++++Lösung|
 <code python>
@@ Zeile 49: / Zeile 92: @@
 ++++
 </nodisp>
 ## Iterables
@@ Zeile 68: / Zeile 112: @@
 Untenstehender Code fügt dem bestehenden Iterator ein Iterable hinzu, so dass wir eine for-Schleife nützen können:
-<html><iframe frameborder="0" width="100%" style="height: 15lh;" allow="clipboard-write" src="https://tkilla77.github.io/python_editor_wasm/embed.html?code=class+FiboIterator%3A%0A++++def+__init__%28self%2C+limit+%3D+-1%29%3A%0A++++++++%23+Hier+wird+der+Zustand+gespeichert%0A++++++++self.one+%3D+0%0A++++++++self.two+%3D+1%0A++++++++self.limit+%3D+limit%0A++++%0A++++def+__next__%28self%29%3A%0A++++++++if+self.limit+%3D%3D+0%3A%0A++++++++++++raise+StopIteration%28%29%0A++++++++self.one%2C+self.two+%3D+self.two%2C+self.one+%2B+self.two%0A++++++++self.limit+-%3D+1%0A++++++++return+self.one%0A%0Aclass+FiboIterable%3A%0A++++%23+Wird+einmal+aufgerufen%2C+wenn+Python+den+die+for-Schleife+startet.%0A++++def+__iter__%28self%29%3A%0A++++++++return+FiboIterator%28%29%0A++++%0Asequence+%3D+FiboIterable%28%29%0Afor+num+in+sequence%3A%0A++++if+num+%3E+1000%3A%0A++++++++print%28f%27Erste+Fibonacci-Zahl+gr%C3%B6sser+als+1000+ist+%7Bnum%7D%27%29%0A++++++++break%0A
+<html><bottom-editor>class FiboIterator:
-"></iframe></html>
+    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
@@ Zeile 80: / Zeile 149: @@
 Ein Generator ist ein Iterable und kann damit auch als Ausdruck nach `in` in einer `for ... in <expression>` stehen.
-<html><iframe frameborder="0" width="100%" style="height: 15lh;" allow="clipboard-write" src="https://tkilla77.github.io/python_editor_wasm/embed.html?code=def+fibo%28%29%3A%0A++++one+%3D+0%0A++++two+%3D+1%0A++++while+True%3A%0A++++++++one%2C+two+%3D+two%2C+one+%2B+two%0A++++++++yield+one%0A%0Afor+num+in+fibo%28%29%3A%0A++++if+num+%3E+1000%3A%0A++++++++print%28f%27Erste+Fibonacci-Zahl+gr%C3%B6sser+als+1000+ist+%7Bnum%7D%27%29%0A++++++++break%0A
+<html><bottom-editor>def fibo():
-"></iframe></html>
+    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
+### Aufgabe 3: Limitieren
 Verändere den obigen Code um ein optionales Limit einzubauen, wieviele Elemente erzeugt werden sollen.
@@ Zeile 92: / Zeile 171: @@
 Der folgende Code soll also `143` ausgeben:
-<html><iframe frameborder="0" width="100%" style="height: 15lh;" allow="clipboard-write" src="https://tkilla77.github.io/python_editor_wasm/embed.html?code=def+fibo%28limit%3D-1%29%3A%0A++++pass%0A%0An%3D10%0Aprint%28f%27Summe+der+ersten+%7Bn%7D+Fibonacci-Zahlen%3A+%7Bsum%28fibo%28n%29%29%7D%27%29
+<html><bottom-editor>def fibo(limit=-1):
-"></iframe></html>
+    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`.
@@ Zeile 99: / Zeile 183: @@
 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}}
+{{: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.
@@ Zeile 105: / Zeile 189: @@
 Eine rekursive Umsetzung könnte wie folgt aussehen - beachte, wie `yield from` eingesetzt wird, um die rekursive Traversierung zu erreichen.
-<html><iframe frameborder="0" width="100%" style="height: 25lh;" allow="clipboard-write" src="https://tkilla77.github.io/python_editor_wasm/embed.html?code=class+Node%3A%0A++++def+__init__%28self%2C+key%2C+left%3DNone%2C+right%3DNone%29%3A%0A++++++++self.key+%3D+key%0A++++++++self.left+%3D+left%0A++++++++self.right+%3D+right%0A++++%0A++++def+pre_order_traversal%28self%29%3A%0A++++++++if+self.left%3A%0A++++++++++++yield+from+self.left.pre_order_traversal%28%29%0A++++++++yield+self%0A++++++++if+self.right%3A%0A++++++++++++yield+from+self.right.pre_order_traversal%28%29%0A%0A%0Atree+%3D+Node%285%2C+Node%281%29%2C+Node%287%29%29%0A%0Afor+node+in+tree.pre_order_traversal%28%29%3A+print+%28node.key%29
+<html><bottom-editor>class Node:
-"></iframe></html>
+    def __init__(self, key, left=None, right=None):
-### Aufgabe 3: In-Order Traversierung
+        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?
-Füge eine Methode `pre_order_traversierung` 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 [[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`.