Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
talit:generators [2024-05-06 13:35] – [Iterables] hoftalit:generators [2025-08-15 07:36] (aktuell) – [Aufgabe 4: Pre-Order Traversierung] hof
Zeile 1: Zeile 1:
 # Iteratoren und Generatoren in Python # 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? 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 ### 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| ++++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> </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. 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 ## 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 ### 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! 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| ++++Lösung|
 <code python> <code python>
Zeile 49: Zeile 92:
 ++++ ++++
 </nodisp> </nodisp>
 +
 ## Iterables ## 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: 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: 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%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. 
  
-Die Funktionen `__iter__` und `__next__` dürfen auch von derselben Klasse implementiert werden 
-. 
 ## Yield ## Yield
  
Zeile 81: Zeile 149:
 Ein Generator ist ein Iterable und kann damit auch als Ausdruck nach `in` in einer `for ... in <expression>` stehen. 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 ### Iteration beenden
  
 Sind keine Elemente mehr übrig, wird einfach nichts zurückgegeben bzw. ein normales `return`. 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. Verändere den obigen Code um ein optionales Limit einzubauen, wieviele Elemente erzeugt werden sollen.
Zeile 93: Zeile 171:
 Der folgende Code soll also `143` ausgeben: 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 ## 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`. Manchmal möchten wir eine andere Iteration (bzw. einen anderen Generator) in die gerade laufende Iteration einbinden. Dazu dienen die Keywords `yield from`.
Zeile 100: Zeile 183:
 Beispiel: ein einfacher Binärbaum besteht aus Knoten (_en_: Nodes), die jeweils bis zu zwei Kinder haben können. 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}}+[[https://magjac.com/graphviz-visual-editor/?dot=digraph%20%7B%0A%20%20%20%205%20-%3E%202%3B%0A%20%20%20%202%20-%3E%201%3B%0A%20%20%20%202%20-%3E%203%3B%0A%20%20%20%205%20-%3E%207%3B%0A%7D|{{.:generators:pasted:20250815-073341.png?nolink&300}}]]
  
 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. 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 106: Zeile 189:
 Eine rekursive Umsetzung könnte wie folgt aussehen - beachte, wie `yield from` eingesetzt wird, um die rekursive Traversierung zu erreichen. 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 4: 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(2, Node(1), Node(3)), 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_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.+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 2 1 3 7` ausgeben.
  
 ### Weiter? ### 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`. 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`.
  • talit/generators.1715002502.txt.gz
  • Zuletzt geändert: 2024-05-06 13:35
  • von hof