Rekursiver Generator zum Abflachen von verschachtelten Listen

Ich bin ein Programmier-Neuling und habe einige Schwierigkeiten, ein Beispiel aus meinem Python-Lehrbuch zu verstehen ("Beginning Python" von Magnus Lie Hetland). Das Beispiel ist für einen rekursiven Generator, der entworfen ist, um die Elemente der verschachtelten Listen (mit beliebiger Tiefe) zu glätten:

def flatten(nested): try: for sublist in nested: for element in flatten(sublist): yield element except TypeError: yield nested 

Sie würden dann eine verschachtelte Liste wie folgt eintragen:

 >>> list(flatten([[[1],2],3,4,[5,[6,7]],8])) [1,2,3,4,5,6,7,8] 

Ich verstehe, wie die Rekursion in Flatten () hilft, auf das innerste Element dieser Liste zu fallen, '1', aber was ich nicht verstehe, ist, was passiert, wenn '1' tatsächlich in flache () als "verschachtelt" zurückgegeben wird " Ich dachte, dass dies zu einem TypeError führen würde (kann nicht über eine Zahl iterieren), und dass die Ausnahmebehandlung war, was eigentlich das schwere Heben für die Erzeugung von Ausgang machen würde … aber das Testen mit modifizierten Versionen von flatten () hat mich überzeugt Dass dies nicht der Fall ist. Stattdessen scheint es, dass die 'Renditeelement' Linie verantwortlich ist.

Das heißt, meine Frage ist das … wie kann das 'Element' jemals tatsächlich ausgeführt werden? Es scheint, wie 'verschachtelt' wird entweder eine Liste sein – in welchem ​​Fall eine andere Schicht der Rekursion hinzugefügt wird – oder es ist eine Zahl und Sie erhalten einen TypeError.

Jede mögliche Hilfe mit diesem würde sehr geschätzt … besonders, würde ich lieben, durch die Kette der Fälle gegangen zu gehen, wie flatten () Handles ein einfaches Beispiel wie:

 list(flatten([[1,2],3])) 

5 Solutions collect form web for “Rekursiver Generator zum Abflachen von verschachtelten Listen”

Ich habe der Funktion eine Instrumentierung hinzugefügt:

 def flatten(nested, depth=0): try: print("{}Iterate on {}".format(' '*depth, nested)) for sublist in nested: for element in flatten(sublist, depth+1): print("{}got back {}".format(' '*depth, element)) yield element except TypeError: print('{}not iterable - return {}'.format(' '*depth, nested)) yield nested 

Ruf jetzt an

 list(flatten([[1,2],3])) 

Zeigt an

 Iterate on [[1, 2], 3] Iterate on [1, 2] Iterate on 1 not iterable - return 1 got back 1 got back 1 Iterate on 2 not iterable - return 2 got back 2 got back 2 Iterate on 3 not iterable - return 3 got back 3 

Vielleicht ist ein Teil deiner Verwirrung, dass du an die endgültige yield denkst, als ob es eine return Anweisung wäre. In der Tat haben ein paar Leute vorgeschlagen, dass, wenn ein TypeError in diesem Code geworfen wird, wird das Element übergeben "zurückgegeben". Das ist nicht der Fall!

Denken Sie daran, dass jede Zeit yield in einer Funktion erscheint, ist das Ergebnis nicht ein einzelnes Element, sondern ein iterable – auch wenn nur ein Element in der Sequenz erscheint. Also, wenn Sie 1 zu flatten , ist das Ergebnis ein Ein-Generator . Um den Artikel aus ihm herauszuholen, musst du noch darüber hinweg iterieren.

Da dieser Ein-Item-Generator TypeError ist, wirft er keinen TypeError wenn der innere Loop versucht, über ihn zu iterieren; Aber die innere Schleife führt nur einmal aus. Dann bewegt sich die äußere for Schleife in die verschachtelte Liste zum nächsten iterable.

Eine andere Möglichkeit, darüber nachzudenken, wäre zu sagen, dass jedes Mal, wenn Sie einen nicht-iterablen Wert zu flatten , es wraps den Wert in einem One-Item iterable und "gibt" zurück.

Ein guter Weg, um eine Funktion, die Sie allgemein verstehen, aber ein kleiner Teil ist stumping Sie, ist es, die Python-Debugger verwenden. Hier ist es mit Kommentaren hinzugefügt:

 -> def flatten(nested): (Pdb) l 1 -> def flatten(nested): 2 try: 3 for sublist in nested: 4 for element in flatten(sublist): 5 yield element 6 except TypeError: 7 yield nested 8 9 import pdb; pdb.set_trace() 10 list(flatten([[1,2],3])) 11 (Pdb) a nested = [[1, 2], 3] 

Oben haben wir gerade die Funktion eingegeben und das Argument ist [[1, 2], 3] . Nutzen wir die Schritt- Funktion von pdb, um durch die Funktion in alle rekursiven Anrufe zu treten, denen wir begegnen sollten:

 (Pdb) s > /Users/michael/foo.py(2)flatten() -> try: (Pdb) s > /Users/michael/foo.py(3)flatten() -> for sublist in nested: (Pdb) s > /Users/michael/foo.py(4)flatten() -> for element in flatten(sublist): (Pdb) s --Call-- > /Users/michael/foo.py(1)flatten() -> def flatten(nested): (Pdb) a nested = [1, 2] 

Wir sind in einen inneren Rahmen von flatten , wo das Argument ist [1, 2] .

 (Pdb) s > /Users/michael/foo.py(2)flatten() -> try: (Pdb) s > /Users/michael/foo.py(3)flatten() -> for sublist in nested: (Pdb) s > /Users/michael/foo.py(4)flatten() -> for element in flatten(sublist): (Pdb) s --Call-- > /Users/michael/foo.py(1)flatten() -> def flatten(nested): (Pdb) a nested = 1 

Zwei Frames in, das Argument 1 ist nicht mehr iterable. Das sollte interessant sein …

 (Pdb) s > /Users/michael/foo.py(2)flatten() -> try: (Pdb) s > /Users/michael/foo.py(3)flatten() -> for sublist in nested: (Pdb) s TypeError: "'int' object is not iterable" > /Users/michael/foo.py(3)flatten() -> for sublist in nested: (Pdb) s > /Users/michael/foo.py(6)flatten() -> except TypeError: (Pdb) s > /Users/michael/foo.py(7)flatten() -> yield nested (Pdb) s --Return-- > /Users/michael/foo.py(7)flatten()->1 -> yield nested 

OK, also wegen der except TypeError , geben wir nur das Argument selbst. Einen Rahmen!

 (Pdb) s > /Users/michael/foo.py(5)flatten() -> yield element (Pdb) l 1 def flatten(nested): 2 try: 3 for sublist in nested: 4 for element in flatten(sublist): 5 -> yield element 6 except TypeError: 7 yield nested 8 9 import pdb; pdb.set_trace() 10 list(flatten([[1,2],3])) 11 

yield element wird natürlich 1 ergeben, sobald unser TypeError Rahmen einen TypeError trifft, TypeError sich das Ergebnis den ganzen Weg bis zum äußersten Rahmen von flatten , was ihn der Außenwelt nachgibt, bevor er weiter zu weiteren Teilen des äußeren Iters bewegt wird .

Der try except Bau fängt die Ausnahme für Sie und liefert nested zurück, die nur das Argument, das gegeben wurde, flatten() zu flatten() .

Also flach (1) wird for sublist in nested: falsch gehen und fährt mit dem for sublist in nested: und Ertrag fort, der nested was 1 .

yield element kann ausgeführt werden, wenn nested ist eine Liste, aber sublist ist nicht (dh wenn nested ist eine normale "flache" Liste). In diesem Fall for sublist in nested wird gut funktionieren. Wenn die nächste Zeile rekursiv eine flache flatten sublist anruft, wird ein Typerror angehoben, wenn der rekursive Anruf versucht, über die "Unterliste" zu iterieren (was nicht iterierbar ist). Dieser TypError wird gefangen und der rekursive Aufruf liefert die gesamte Eingabeliste zurück, also wird er dann durch das for element in flatten(sublist) aufgerufen. Mit anderen Worten, for element in flatten(sublist) winds up tun for element in sublist wenn die Unterliste bereits flach ist.

Die wichtigste Sache zu erkennen ist, dass auch eine nicht verschachtelte Liste zu einem rekursiven Anruf führen wird. Ein Aufruf wie flatten([1]) führt zu zwei Ausbeuten: Der rekursive Aufruf wird dem äußeren Aufruf [1] ergeben und der äußere Aufruf sofort zurückgibt 1 .

Diese Version der Funktion kann helfen zu verstehen, was los ist:

  def flatten(nested, indent=""): try: print indent, "Going to iterate over", nested for sublist in nested: print indent, "Going to iterate over flattening of", sublist for element in flatten(sublist, indent+" "): print indent, "Yielding", element yield element except TypeError: print indent, "Type Error! Yielding", nested yield nested >>> list(flatten([[1,2],3])) Going to iterate over [[1, 2], 3] Going to iterate over flattening of [1, 2] Going to iterate over [1, 2] Going to iterate over flattening of 1 Going to iterate over 1 Type Error! Yielding 1 Yielding 1 Yielding 1 Going to iterate over flattening of 2 Going to iterate over 2 Type Error! Yielding 2 Yielding 2 Yielding 2 Going to iterate over flattening of 3 Going to iterate over 3 Type Error! Yielding 3 Yielding 3 [1, 2, 3] 
  • Python: Rekursive Funktion, um die größte Zahl in der Liste zu finden
  • Merkwürdiges Rekursionsverhalten in Python
  • Python-interpretator automatisch wiederherzustellen, ohne Antwort zurückzugeben
  • Python RuntimeError: maximale Rekursionstiefe überschritten
  • Python Recursive Funktion für Collatz Conjecture
  • Ist diese Funktion rekursiv, obwohl sie sich nicht nennt?
  • Python rekursive Funktion, die von 0 bis n?
  • Berechnungsdeterminante einer Matrix (nxn) rekursiv
  • Iteration in Rekursion umwandeln
  • Kreuz Produkt von Sets mit Rekursion
  • Python leer dict nicht durch Verweis übergeben?
  • Python ist die beste Programmiersprache der Welt.