Rekursiv in einer Liste "hinabsteigen"

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.
BastiL
User
Beiträge: 116
Registriert: Montag 7. Juli 2008, 20:22

Rekursiv in einer Liste "hinabsteigen"

Beitragvon BastiL » Montag 23. März 2009, 11:56

Hallo zusammen,

ich stehe hier gerade ziemlich auf dem Schlauch. Ich möchte die simplen Datentypen aus einer mehrfach geschachtelten Liste extrahieren. Ich denke am einfachsten läuft das über eine Rekursion:

Code: Alles auswählen

liste=[["hallo", "das", "ist", "eine", "Liste"],["und", "nochmal", "eine"]]

   for i in liste:
       def printitem(i):
           if type(i) == list:
               print "Verschachtelte Liste" + str(i)
              i = i[0] # extrahiere "Unterliste"
              print i
              printitem(i)
           else:
              print type(i), i


Funktiniert prima, nur laufe ich eben nicht durch die ganze Liste. Ich bekomme so nur das "hallo" und das "und" extrahiert. irgendwie müsste ich da doch anders über die Liste loopen? Aber das geht sicher noch viel einfacher?

Grüße BastiL
Benutzeravatar
helduel
User
Beiträge: 300
Registriert: Montag 23. Juli 2007, 14:05
Wohnort: Laupheim

Re: Rekursiv in einer Liste "hinabsteigen"

Beitragvon helduel » Montag 23. März 2009, 12:35

Moin,

BastiL hat geschrieben:Ich denke am einfachsten läuft das über eine Rekursion:

Am einfachsten, ja. Am besten, nein ;-). Im Extremfall gibt es einen RuntimeError mit der Message: "maximum recursion depth exceeded". Um dieses Problem erst gar nicht zu bekommen, nimmt man einen iterativen Ansatz. Ich habe vor einiger Zeit mal sowas gebastelt.

BastiL hat geschrieben:Funktiniert prima, nur laufe ich eben nicht durch die ganze Liste. Ich bekomme so nur das "hallo" und das "und" extrahiert.

Du holst dir ja auch immer nur das erste Element aus der Liste. Lass das "i = i[0]" weg.

Gruß,
Manuel
tordmor
User
Beiträge: 100
Registriert: Donnerstag 20. November 2008, 10:29
Wohnort: Stuttgart

Re: Rekursiv in einer Liste "hinabsteigen"

Beitragvon tordmor » Montag 23. März 2009, 13:09

BastiL hat geschrieben:

Code: Alles auswählen

liste=[["hallo", "das", "ist", "eine", "Liste"],["und", "nochmal", "eine"]]

   for i in liste:
       def printitem(i):
           if type(i) == list:
               print "Verschachtelte Liste" + str(i)
              i = i[0] # extrahiere "Unterliste"
              print i
              printitem(i)
           else:
              print type(i), i



Ich seh hier nur eine Funktion, die zweimal definiert und nicht verwendet wird.
BastiL
User
Beiträge: 116
Registriert: Montag 7. Juli 2008, 20:22

Beitragvon BastiL » Montag 23. März 2009, 13:21

@helduel: Das schaue ich mir mal an, danke. Ich bin sowieso kein Freund von rekursiven Dingen - zum Glück ist das in Python nicht sehr verbreitet.

@tordmor: Das verstehe ich jetzt nicht.
Edit: Ok, es gibt noch einen Funktionsaufruf für die Funktion...
BastiL
User
Beiträge: 116
Registriert: Montag 7. Juli 2008, 20:22

Beitragvon BastiL » Montag 23. März 2009, 13:44

Gut, die Lösung von helduel entpackt meine Liste. Allerdings habe ich vergessen zu erwähnen, dass ich die Struktur erhalten muss. Präzise gesagt möchte ich eine Python-Liste in eine Liste im Scheme-Syntax wandeln und in eine Datei schreiben. Aus meinem Beispiel:

Code: Alles auswählen

liste=[["hallo", "das", "ist", "eine", "Liste"],["und", "nochmal", "eine"]]


müsste also so etwas werden:
[code=](define liste '(("hallo" "das" "ist" "eine" "Liste")("und" "nochmal" "eine"))[/code]
Eigentlich müsste ich dann duch gleich während des Entpackens die Struktur irgendwo mitsichern? Oder das gleich rausschreiben?
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Montag 23. März 2009, 14:09

Da Deine Ziel-Syntax die gleiche logische Strukturierung hat, kommst Du mit Stringmanipulation des repr() Deiner Liste wahrscheinlich schneller zum Ziel.

Generell kann man sich die Baumstruktur über ID-Vergabe merken, z.B. mittels Vaterlink. Brauchst Du auch noch die Position innerhalb der Nachbarn, wäre der Index noch mitzuführen bzw. ist diese in den IDs je nach Traversionsrichtung zu einem bestimmten Vaterknoten enthalten.
BastiL
User
Beiträge: 116
Registriert: Montag 7. Juli 2008, 20:22

Beitragvon BastiL » Montag 23. März 2009, 14:12

jerch hat geschrieben:Da Deine Ziel-Syntax die gleiche logische Strukturierung hat, kommst Du mit Stringmanipulation des repr() Deiner Liste wahrscheinlich schneller zum Ziel.

Aha - und wie könnte ich das angehen?

jerch hat geschrieben: Generell kann man sich die Baumstruktur über ID-Vergabe merken, z.B. mittels Vaterlink. Brauchst Du auch noch die Position innerhalb der Nachbarn, wäre der Index noch mitzuführen bzw. ist diese in den IDs je nach Traversionsrichtung zu einem bestimmten Vaterknoten enthalten.

Aha aha - könntest du mir das bitte etwas ausführlicher erklären?
BastiL
User
Beiträge: 116
Registriert: Montag 7. Juli 2008, 20:22

Beitragvon BastiL » Montag 23. März 2009, 14:30

Ok ,den ersten Punkt habe ich verstanden und umgesetzt. Scheint für meine Zwecke ausreichend zu sein.
Punkt zwei würde mich aber trotzdem interessieren.

Grüße
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Montag 23. März 2009, 14:32

BastiL: Warum erzeugst du die Funktion jedes Mal neu? Das kostet unglaublich viel Zeit O_O
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Montag 23. März 2009, 14:58

Aha - und wie könnte ich das angehen?

Code: Alles auswählen

>>> l = [["hallo", "das", "ist", "eine", "Liste"],["und", "nochmal", "eine"]]
>>> repr(l).replace('[', '(').replace(']', ')').replace(', ', ' ').replace("'", '"')
'(("hallo" "das" "ist" "eine" "Liste") ("und" "nochmal" "eine"))'

Aha aha - könntest du mir das bitte etwas ausführlicher erklären?

Prinzipiell gibts versch. Verfahren, einen Baum samt Bauminformation zu serialisieren. (Finde grad keinen guten Artikel zum Vatermodell, hier mal ein Link zum nested sets-Modell). Je nach dem, welche Baumaktionen Du benötigst, sind die verschiedenen Modelle unterschiedl. performant.

Grobschema Vater-Modell: Jeder Knoten bekommt beim Traversieren während der Serialisation eine ID und eine VaterID (die ID des Vaterknotens :wink:) zugewiesen. Willst Du jetzt alle Kinder von xy wissen, mußt Du alle Elemente mit VaterID==xy raussuchen, sortierst Du deren IDs, hast Du auch gleich deren Nachbarschaftbeziehungen abgebildet.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Montag 23. März 2009, 17:58

DIe Lösung mit ``repr()`` fällt spätestens dann auf die Nase, wenn im String ``[`` vorkommt.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Montag 23. März 2009, 18:37

Ja leider, gleiches gilt auch für die anderen zu ersetzenden Zeichen.

@BastiL:
Das Zeichen wie [ ] , ' nicht in den einzelnen String vorkommen dürfen, ist halt eine Vorbedingung. Kannst Du die nicht sicherstellen, geht das nicht ohne weiteres mit repr().
DasIch
User
Beiträge: 2423
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Montag 23. März 2009, 19:24

Hier mal ein brauchbarer Algorithmus wie man ihn nicht umsetzen sollte :D

Code: Alles auswählen

>>> foo = lambda seq, excs=(basestring, Number): '(%s)' % ' '.join([func(seq, excs) for func in (lambda : (yield lambda seq, excs: [[lambda : '(%s)' % ' '.join(map(repr, func(item, excs))), lambda : item][isinstance(item, excs)]() for item in seq]))()][0])
>>> foo(seq)
"(('hallo' 'das' 'ist' 'eine' 'liste') ('und' 'nochmal' 'eine'))"
__doc__
User
Beiträge: 4
Registriert: Montag 24. September 2007, 09:41
Kontaktdaten:

Beitragvon __doc__ » Montag 23. März 2009, 19:33

Code: Alles auswählen

>>> liste=[["hallo", "das", "ist", "eine", "Liste"],["und", "nochmal", "eine"]]
>>> extract = lambda data: [value for item in data for value in extract(item)] if isinstance(data, list) else [data]
>>> extract(liste)
['hallo', 'das', 'ist', 'eine', 'Liste', 'und', 'nochmal', 'eine']
jerch
User
Beiträge: 1622
Registriert: Mittwoch 4. März 2009, 14:19

Beitragvon jerch » Dienstag 24. März 2009, 00:25

Ein wenig offtopic, hier mal ein Ansatz für das Vatermodell mit "horizontalem" Stack:

Code: Alles auswählen

class PNode:
    def __init__(self, n, node_id, parent_id):
        self.value = n
        self.node_id = node_id
        self.parent_id = parent_id
    def __repr__(self):
        s = '<PNode %s ID:%s parentID:%s>' \
            % (repr(self.value), self.node_id, self.parent_id)
        return(s)

def stack_the_tree(node):
    stack = []
    tmp_stack = []
    tmp_stack.append(PNode(node, 0, 0))
    id_counter = 1
    while len(tmp_stack) > 0:
        elem = tmp_stack[0]
        if isinstance(elem.value, list):
            stack.append(PNode(None, elem.node_id, elem.parent_id))
            for i in elem.value:
                tmp_stack.append(PNode(i, id_counter, elem.node_id))
                id_counter += 1
        else:
            stack.append(elem)
        tmp_stack.pop(0)
    return(stack)

ser = stack_the_tree([[[0],['test',2]],[],[{'klaus':56}]])
for i in ser:
    print i

<PNode None ID:0 parentID:0>
<PNode None ID:1 parentID:0>
<PNode None ID:2 parentID:0>
<PNode None ID:3 parentID:0>
<PNode None ID:4 parentID:1>
<PNode None ID:5 parentID:1>
<PNode {'klaus': 56} ID:6 parentID:3>
<PNode 0 ID:7 parentID:4>
<PNode 'test' ID:8 parentID:5>
<PNode 2 ID:9 parentID:5>

Um das sinnvoll nutzen zu können, fehlt noch die Unterstützung für andere iterables (im Moment nur Listen), auch PNode ist so nicht wirklich handlich.

Edit: Und noch als rekursiven Generator (vertikal):

Code: Alles auswählen

def yield_the_tree(n, node_id=0, parent_id=0):
    if node_id == 0:
        if not isinstance(n, list):
            yield PNode(n, 0, 0)
            return
        yield PNode(None, 0, 0)
    for i in n:
        node_id += 1
        if isinstance(i, list):
            yield PNode(None, node_id, parent_id)
            for j in yield_the_tree(i, node_id, node_id):
                node_id = j.node_id
                yield j
        else:
            yield PNode(i, node_id, parent_id)

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder