Über beliebig tiefes Dictionary iterieren

[anogayales]

Hallo allerseits,

ich versuche grade etwas simples zu lösen: Ich habe ein Dictionary mit beliebiger Tiefe iterieren. Das Dictionary enthält Dictionary Einträge und diese wiederum Dictionary Einträge usw.

Ich suche dafür eine pythonische Lösung, bisher bin ich nur auf sehr hässlichen Code gekommen, den ich sofort wieder weggeschmissen hab. Gibts dafür vielleicht sogar schon vordefinierte Python Funktionen?

Edit: Spezifikation erweitert
Schlüssel sind beliebige Objekte wobei die Values Dictionaries sind. Values müssen nicht notwendigerweise Dictionaries sein. Es soll über innere Knoten sowieso Blätter iteriert werden.

Code: Alles auswählen

def iter_deep(input):
    for key, value in input.iteritems():
        if isinstance(value, dict):
            yield key
            for i in iter_deep(value):
                yield i
        else:
            yield key, value

Test Daten:

Code: Alles auswählen

testing = {"Main":
                    {"Sub" :
                             {"Deep1":1, "Deep12" :2},
                     "Sub2":
                            {"Deep2" : 2}

                    }
        }

Leider ist das oben rekursiv formuliert und ist nicht wirklich sauber. Hat jemand Vorschläge? Das isinstance stört mich auch ein bisschen.

Momentane Ausgabe

Code: Alles auswählen

Main
Sub2
('Deep2', 2)
Sub
('Deep12', 2)
('Deep1', 1)

Grüße,
anogayales

[pillmuncher]

Ich würde sowas machen:

Code: Alles auswählen

from collections import Mapping

def iteritems_flattened(mapping):
    items = mapping.items()
    while items:
        key, value = items.pop()
        yield key, value
        if isinstance(value, Mapping):
            items.extend(value.iteritems())

Beispiel:

Code: Alles auswählen

>>> for k, v in iteritems_flattened({1:2, 3:{4:5, 6:{7:8, 9:0}}}):
...     print k, v
...
3 {4: 5, 6: {9: 0, 7: 8}}
6 {9: 0, 7: 8}
7 8
9 0
4 5
1 2

Deine rekursive Variante würde ich dahingehend umbauen:

Code: Alles auswählen

def iteritems_flattened(mapping):
    for key, value in mapping.iteritems():
        yield key, value
        if isinstance(value, Mapping):
            for each in iteritems_flattened(value):
                yield each

Das Ergebnis ist vergleichbar dem oben, nur die Reihenfolge ist anders.

Sowas ist natürlich auch möglich:

Code: Alles auswählen

def iter_paths(mapping):
    for key, value in mapping.iteritems():
        if isinstance(value, Mapping):
            for each in iter_paths(value):
                yield [key] + each
        else:
            yield [key, value]

Ergebnis:

Code: Alles auswählen

>>> for each in iter_paths({1:2, 3:{4:5, 6:{7:8, 9:0}}}):
...     print each
...
[1, 2]
[3, 4, 5]
[3, 6, 9, 0]
[3, 6, 7, 8]

Gruß,
Mick.

[sma]

Leider ist das oben rekursiv formuliert und ist nicht wirklich sauber. Hat jemand Vorschläge? Das isinstance stört mich auch ein bisschen.

Die rekursive Lösung ist elegant (und damit ausreichend pythonisch). Um das "isinstance" kommst du nicht herum. Wie in pillmunchers Beispiel könnte man statt "dict" auch die abstrakte Basisklasse benutzen, aber das finde ich der Mühe nicht wert. In jedem Fall finde ich die rekursive funktionale Version besser als den Vorschlag von pillmuncher, eine items-Liste mit pop() und extends() zu manipulieren.

Stefan

[Hyperion]

@sma: Hui, jetzt kocht bestimmt die Metadiskussion hoch, ob Python für Rekursion ausgelegt ist oder nicht...

[snafu]

Und dass JavaScript alles viel besser kann. ;P *SCNR*

[pillmuncher]

@sma: Ich finde ebenfalls die rekursive Version schöner, aber nicht in jedem Fall besser. Wenn die Rekursionstiefe zu groß wird funktioniert Rekursion einfach nicht in Python. Ohne tail calls ist Rekursion irgendwie witzlos. DIY ist zwar auch pythonisch, aber für generator functions lässt sich wohl nur mit viel Mühe ein Trampolin bauen.

Apropos Mühe:

Code: Alles auswählen

def iter_paths(mapping):
    items = [mapping.items()]
    stack = []
    while items:
        while items[-1]:
            key, value = items[-1].pop()
            if isinstance(value, Mapping):
                items.append(value.items())
                stack.append(key)
            else:
                yield stack + [key, value]
        del items[-1]
        del stack[len(items) - 1:]

[cofi]

@sma: Hui, jetzt kocht bestimmt die Metadiskussion hoch, ob Python für Rekursion ausgelegt ist oder nicht...

Warum denn? Alleine die Existenz des Rekursionslimits macht die Diskussion ziemlich einseitig Dazu noch die relativ teuren Funktionsaufrufe und das Fehlen von TCO und die Diskussion ist so ziemlich gegessen

Das ist jetzt kein sonderlich grosses Problem weil man die Rekursion durch eine Queue ganz einfach zu einer Iteration abflacht, wie sma es schon vorgeschlagen hat, aber Python ist ganz sicher nicht fuer Rekusion _ausgelegt_, unterstuetzt wird es natuerlich schon.

Aber gerade mit der Anforderung "beliebig tiefe Dictionaries" scheidet imho eine Rekursion aus.

[sma]

Aber gerade mit der Anforderung "beliebig tiefe Dictionaries" scheidet imho eine Rekursion aus.

Und man kann doch diskutieren: beliebig tief ist für alle praktischen Belange garantiert < 1000 oder wo das willkürlich gesetzte Limit bei Python eben liegt. Beliebig ist sehr relativ. Theoretisch könnte das Limit von Python natürlich immer genau ein bisschen zu klein sein, aber es ging ja auch um Eleganz und Eleganter als Rekursion als einzig ware Schleife geht nicht

Stefan

[lunar]

@cofi: Ich hoffe mal, „beliebige Tiefe“ ist nicht wörtlich zu nehmen. Hat man nicht vorher schon irgendwo etwas unschön gelöst, wenn man nun mehr als 1000(!) geschachtelte Wörterbücher glätten muss?

Und solange beliebig eher etwas der Art „zwischen fünf und 20“ meint, ist Rekursion eine gute und schöne Lösung. „Readability counts“

[BlackJack]

@lunar: Man könnte sich eine Baumstruktur mit ein paar Millionen Knoten vorstellen. Was wäre daran unschön?

[cofi]

@lunar(, sma): stimmt schon, dass man sich Gedanken machen sollte, wenn es _so_ tief wird, aber in erster Linie ist die Anforderung ja: Ohne Einschraenkung der Tiefe, darum sollte man sich nicht so eine Beschraenkung durch die Hintertuer einhandeln -- unnoetig .

[Hyperion]

... aber es ging ja auch um Eleganz und Eleganter als Rekursion als einzig ware Schleife geht nicht

Ich schlage das als (LISP)-Ausspruch der Woche vor!

Uns fehlt für solche Sachen ein MOtD-Modul in diesem Forum