Python DFS 嵌套字典

Question

我编写了一个函数，它应该能够使用 DFS 搜索嵌套字典以查找特定值。递归元素似乎工作正常，但是，当基本情况应该 return 正确时，它根本就没有。

obj = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'i':'j'}]}

def obj_dfs(obj, target):
  
  if type(obj) == dict:
    for key, val in obj.items():
      obj_dfs(key, target)
      obj_dfs(val, target) 
  
  elif type(obj) in (list, tuple):
    for elem in obj:
      obj_dfs(elem, target)
  else:
    if obj == target:
      print(f"{obj} == {target}")
      return True
    else:
      print(f"{obj} != {target}")  
  return False 

obj_dfs(obj, 'j')

和结果。如您所见，标准输出“i==i”显示该元素已正确求值，但 return True 语句未按预期运行。我已经验证如果我调用 obj_dfs(obj, 'j')，会遇到同样的错误。

a != j
c != j
d != j
e != j
f != j
b != j
g != j
h != j
i != j
j == j
False

这是为什么？我该如何解决这个问题？

Answer 1

我对您的代码进行了一些修改

obj = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'i':'j'}]}

def obj_dfs(obj, target):
  if type(obj) == dict:
    for key, val in obj.items():
      if(key==target):
        return val
      else:
        result=obj_dfs(val, target)
        if result!=None: return result
  elif type(obj) in (list, tuple):
    for elem in obj:
      result=obj_dfs(elem, target)
      if result!=None: return result
  else: 
    if obj==target: return True

print(obj_dfs(obj, 'i'))

我不知道为什么你只是 return true 而不是值，所以我说如果它是字典键它会 return 值，而不是 return true，表示找到了

Answer 2

扩展我的评论，试试这个，我们将 return 值传递到链上，并且如果 child returned 总是 return True True:

obj = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'i':'j'}]}
obj2 = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'g':'j'}]}

def obj_dfs(obj, target):
    if type(obj) == dict:
        for key, val in obj.items():
            keyret = obj_dfs(key, target)
            valueret = obj_dfs(val, target)
        if keyret is True or valueret is True:
            return True
        else:
            return False
    elif type(obj) in (list, tuple):
        rets = []
        for elem in obj:
            rets.append(obj_dfs(elem, target))
        if True in rets:
            return True
        else:
            return False
    else:
        if obj == target:
            print(f"{obj} == {target}")
            return True
        else:
            print(f"{obj} != {target}")
            return False

print(obj_dfs(obj, 'i'))
print(obj_dfs(obj2, 'i'))

Answer 3

正如评论所指出的，您需要 return 递归调用的结果。由于您只是在寻找 True/False 匹配项，因此您可以将递归调用传递给 any() ，如果有匹配项，它将以 True 提前退出。基本情况可以简单为是否 obj == target.

obj = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'i':'j'}]}

def obj_dfs(obj, target):
    if obj == target:
        return True

    if isinstance(obj, dict):
        return any(obj_dfs(v, target) for v in obj.items())
    
    elif isinstance(obj, (list, tuple)):
        return any(obj_dfs(l, target) for l in obj)

    return False
                   
obj_dfs(obj, 'i'), obj_dfs(obj, 'j'), obj_dfs(obj, 'd'), obj_dfs(obj, 'x')
# (True, True, True, False)

这允许三个简单的块。请注意，我们正在检查 tuple 以及最后一个 isinstance 中的 list。这使您可以简单地传入字典 item()，而不是独立地遍历键和值。

添加 print(obj) 作为函数的第一行将显示您遍历数据的顺序。例如 obj_dfs(obj, 'j') 将打印：

{'a': [{'c': 'd'}, {'e': 'f'}], 'b': [{'g': 'h'}, {'i': 'j'}]}
('a', [{'c': 'd'}, {'e': 'f'}])
a
[{'c': 'd'}, {'e': 'f'}]
{'c': 'd'}
('c', 'd')
c
d
{'e': 'f'}
('e', 'f')
e
f
('b', [{'g': 'h'}, {'i': 'j'}])
b
[{'g': 'h'}, {'i': 'j'}]
{'g': 'h'}
('g', 'h')
g
h
{'i': 'j'}
('i', 'j')
i
j

Answer 4

递归是一种函数式继承，因此将它与函数式风格结合使用会产生最佳效果。这意味着解耦问题并将副作用推到程序的边缘。 obj_dfs 在搜索逻辑中执行 depth-first 遍历和混合。并且出于调试目的，包括 print 副作用。

分解产生的函数更易于编写、测试和在我们程序的各个部分中重用。我们将从通用的 dfs 开始遍历 -

def dfs(t, path = []):
  if isinstance(t, dict):
    for key, val in t.items():
      yield from dfs(val, [*path, key])
  elif isinstance(t, (list, tuple)):
    for key, val in enumerate(t):
      yield from dfs(val, [*path, key])
  else:
    yield path, t

obj = {'a': [{'c':'d'}, {'e':'f'}],
       'b': [{'g':'h'}, {'i':'j'}]}

for path, val in dfs(obj):
  print(path, val) # side effect decided by caller

['a', 0, 'c'] d
['a', 1, 'e'] f
['b', 0, 'g'] h
['b', 1, 'i'] j

此处建议的解决方案和其他答案折叠了 key 和 value 之间的语义差异，不区分 target。像上面写的dfs，就可以知道obj的哪一部分匹配了。

keys	values
['a', 0, 'c']	d
['a', 1, 'e']	f
['b', 0, 'g']	h
['b', 1, 'i']	j

has_value 和 has_key 很容易根据 dfs -

定义

def has_value(t, target):
  for path, val in dfs(t):
    if val == target:
      return True
  return False

def has_key(t, target):
  for path, val in dfs(t):
    if target in path:
      return True
  return False

print(has_value(obj, "j"))   # True
print(has_key(obj, "j"))     # False

print(has_value(obj, "i"))   # False
print(has_key(obj, "i"))     # True

Python DFS 嵌套字典

Python DFS nested dictionary

python

dictionary

recursion

tree

depth-first-search