19
Gesetzt haben wir diese dict:Kennen Sie die Tiefe eines Wörterbuchs
d = {'a':1, 'b': {'c':{}}}
Was die Verschachtelung Tiefe es die einfachste Möglichkeit, zu wissen wäre?
A
Antwort
28
Sie werden recurse haben:
def depth(d, level=1):
if not isinstance(d, dict) or not d:
return level
return max(depth(d[k], level + 1) for k in d)
max() benötigt, um die größte Tiefe für den aktuellen Wörterbuch unter die Lupe genommen auf jeder Ebene, ein Wörterbuch mit 3 Schlüsseln jeder unterschiedlichen Tiefen holen sollte das widerspiegeln größte Tiefe auf dieser Ebene.
Demo:
>>> d = {'a':1, 'b': {'c':{}}}
>>> depth(d)
3
>>> d = {'foo': {'bar': {'baz': 0}, 'spam': {'ham': {'monty': 1}, 'eric': 'idle'}}, 'john': 'cleese'}
>>> depth(d)
5
+0
+1 der eine Vorbehalt: sollten keine und {} 1 zurückgeben? Aber das ist eine Frage der Konvention. –
+1
@lukas: Die Technik kann optimiert werden; Der Punkt war mehr zu zeigen, was getan werden muss. Die Schlüsselpunkte hier sind Rekursion und die Verwendung von 'max()', würde ich sagen. –
+0
Der Standardwert von level sollte 0 und nicht 1 sein. Ein einfaches dict gibt 2 als Tiefe zurück, was nicht korrekt ist. Auch für None und leere dicts sollte die Tiefe 0 und nicht 1 sein. –
16
Sie benötigen eine rekursive Funktion zu erstellen:
>>> def depth(d):
... if isinstance(d, dict):
... return 1 + (max(map(depth, d.values())) if d else 0)
... return 0
...
>>> d = {'a':1, 'b': {'c':{}}}
>>> depth(d)
3
4
Eine nicht-rekursive Lösung:
def depth(d):
depth=0
q = [(i, depth+1) for i in d.values() if isinstance(i, dict)]
max_depth = 0
while (q):
n, depth = q.pop()
max_depth = max(max_depth, depth)
q = q + [(i, depth+1) for i in n.values() if isinstance(i, dict)]
print max_depth
3
Iterative Lösung:
from collections import deque
def depth(d):
q = deque([d])
q2 = deque()
max_depth = 0
while q:
curr_dict = q.popleft()
if isinstance(curr_dict, dict):
for di in curr_dict.itervalues():
q2.append(di)
if not q:
q, q2 = q2, q
max_depth += 1
return max_depth
print depth(None)
print depth({})
print depth({"a": "b"})
print depth({"a": "b", "c": {"d": "e"}, "f": {"g": "h"}, "i": {"j": "k"}, "x": {}, "z": {} })
print depth({'a':1, 'b': {'c':{}}})
print depth({'foo': {'bar': {'baz': 0}, 'spam': {'ham': {'monty': 1}, 'eric': 'idle'}}, 'john': 'cleese'})
Könnte es verzweigen, oder nur ein Schlüssel pro Schicht? – mhlester
ist es nur verschachtelt, dass Sie sich Sorgen machen, oder könnte das Diktat Werte haben, die auch andere Container sind? – mgilson
Ich werde der Idiot sein zu sagen, dass die (einfachste) Antwort für das Beispiel, das du gabst, wäre, es anzusehen. Auch kann ich nicht glauben, dass dies kein Duplikat ist (aber es scheint zu überprüfen!) – keyser