Rekursive Generator-Funktionen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Rekursive Generator-Funktionen

Beitragvon windner » Freitag 9. November 2007, 12:32

Im Internet kursiert PocketPCPyton (v 2.2 aufgebohrt) für Windows CE.

Während einer längeren Zugfahrt wollte ich so etwas wie "find text in files" implementieren, damit ich die Dok. durchsuchen kann. Leider fehlt in os die Funktion walk(), also wollte ich einen Ersatz schaffen. Dabei wollte ich eine rekursive Generator-Funktion schreiben, um mir eine lange Liste zu ersparen. Das ist aber nicht so einfach, wie es klingt.

Rekursives Durchlaufen ist ja einfach, ich verwende zB eine Liste:

Code: Alles auswählen

>>> baum = (
   1,
   (2, 3, (4, 5, 6)),
   7,
   8,
   ((9, 10), 11)) # ein Baum für die Rekursion
>>> import types
>>> def walk(baum, resultat_liste):
   for ent in baum:
      if type(ent) == types.TupleType:
         walk(ent, resultat_liste)
      else:
         resultat_liste.append(ent)
   return resultat_liste # damit ich statt über die liste gleich über walk iterieren kann
>>> l=[]
>>> for ent in walk(baum, l): print ent,

1 2 3 4 5 6 7 8 9 10 11


Soweit ist alles klar. Daran stört mich nur diese Liste, ich denke, dass das mit yield klarer wäre. Also:

Code: Alles auswählen

>>> def iwalk(baum):
   for ent in baum:
      if type(ent) == types.TupleType:
         iwalk(ent)
      else:
         yield ent
>>> for ent in iwalk(baum): print ent,

1 7 8


Da kommen nur die singulären Werte zurück. Das ist mir noch klar, weil ja der Aufruf iwalk(ent) einen ungenützten Iterator erzeugt.

Wie aber macht man eine Funktion iwalk() mit yield, die sich so verhält wie meine Funktion walk()?
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Freitag 9. November 2007, 12:38

Öhm, vielleicht steh ich grade auf'n Schlauch, aber... Wozu? Dieser "Baum" ist für mich kein Baum o_o Du müsstest einfach nur die Verschachtelung rausnehmen und dann könntest du normal iterieren. Aber vielleicht hab ich das einfach nur nicht verstanden...
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Beitragvon windner » Freitag 9. November 2007, 12:46

Dieser "Baum" ist für mich kein Baum o_o Du müsstest einfach nur die Verschachtelung rausnehmen und dann könntest du normal iterieren.


Könnte ich. Sollte aber nur ein Beispiel sein, in Wahrheit arbeite ich mit os.listdir() und der Baum ist mein Dateisystem. Weil der Code aber mit einem Tuple-Baum übersichtlicher ist, habe ich es so gepostet.
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Beitragvon keppla » Freitag 9. November 2007, 12:50

Wie aber macht man eine Funktion iwalk() mit yield, die sich so verhält wie meine Funktion walk()?


Keine ahnung, obs cooler geht, aber eine Lösung wäre, dass du im generator über den erzeugten untergenerator iterierst, und alles yieldest:

Code: Alles auswählen

def walk(tree):
   for item in tree:
      if type(item) == types.TupleType:
         for result in walk(item):
            yield result
      else:
         yield item
BlackJack

Beitragvon BlackJack » Freitag 9. November 2007, 12:52

@BlackVivi: Wieso ist das kein Baum? Und darum die Verschachtelung per *Programm* zu entfernen geht es ja gerade. Auf windner's ursprüngliches Problem bezogen gleicht das dem Rat keine Unterverzeichnisse zu benutzen sondern alles in `/` oder `C:\` zu speichern. ;-)

@windner: Du musst die einzelnen Elemente aus dem ("Sub")Iterator "yield"en:

Code: Alles auswählen

In [503]: def iwalk(forest):
   .....:     for item in forest:
   .....:         if isinstance(item, tuple):
   .....:             for subitem in iwalk(item):
   .....:                 yield subitem
   .....:         else:
   .....:             yield item
   .....:

In [504]: list(iwalk(baum))
Out[504]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
windner
User
Beiträge: 76
Registriert: Freitag 19. Oktober 2007, 11:25

Beitragvon windner » Freitag 9. November 2007, 12:56

Danke euch beiden! Da bin ich ja schön auf der Leitung gestanden. Habe verstanden.

Wachse, Forest, wachse!
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Freitag 9. November 2007, 12:57

BlackJack hat geschrieben:@BlackVivi: Wieso ist das kein Baum? Und darum die Verschachtelung per *Programm* zu entfernen geht es ja gerade. Auf windner's ursprüngliches Problem bezogen gleicht das dem Rat keine Unterverzeichnisse zu benutzen sondern alles in `/` oder `C:\` zu speichern. ;-)
Dann hab' ich das tatsächlich falsch gelesen und verstanden. Verzeihung.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder