Das deutsche Python-Forum

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

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

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.

@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...

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: Alles auswählen

(define liste '(("hallo" "das" "ist" "eine" "Liste")("und" "nochmal" "eine"))

Eigentlich müsste ich dann duch gleich während des Entpackens die Struktur irgendwo mitsichern? Oder das gleich rausschreiben?

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.

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?

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

BastiL: Warum erzeugst du die Funktion jedes Mal neu? Das kostet unglaublich viel Zeit O_O

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

) 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.

DIe Lösung mit ``repr()`` fällt spätestens dann auf die Nase, wenn im String ``[`` vorkommt.

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().

Hier mal ein brauchbarer Algorithmus wie man ihn nicht umsetzen sollte

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'))"

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']

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)

Das deutsche Python-Forum

Rekursiv in einer Liste "hinabsteigen"

Rekursiv in einer Liste "hinabsteigen"

Re: Rekursiv in einer Liste "hinabsteigen"

Re: Rekursiv in einer Liste "hinabsteigen"