在嵌套字典和列表中查找某个键的所有出现位置
- 2024-12-30 08:41:00
- admin 原创
- 46
问题描述：
我有一本这样的字典：
{
"id": "abcde",
"key1": "blah",
"key2": "blah blah",
"nestedlist": [
{
"id": "qwerty",
"nestednestedlist": [
{
"id": "xyz",
"keyA": "blah blah blah"
},
{
"id": "fghi",
"keyZ": "blah blah blah"
}
],
"anothernestednestedlist": [
{
"id": "asdf",
"keyQ": "blah blah"
},
{
"id": "yuiop",
"keyW": "blah"
}
]
}
]
}
基本上是一个具有任意深度的嵌套列表、字典和字符串的字典。
遍历此内容以提取每个“id”键的值的最佳方法是什么？我想实现与“//id”等 XPath 查询相同的功能。“id”的值始终是一个字符串。
所以从我的例子来看，我需要的输出基本上是：
["abcde", "qwerty", "xyz", "fghi", "asdf", "yuiop"]
顺序并不重要。
解决方案 1：
我发现这个问答非常有趣，因为它为同一个问题提供了几种不同的解决方案。我把所有这些函数都拿来，用一个复杂的字典对象对它们进行了测试。我不得不从测试中剔除两个函数，因为它们有太多失败的结果，而且它们不支持将列表或字典作为值返回，而我认为这很重要，因为一个函数应该为几乎所有即将到来的数据做好准备。
因此我通过该模块对其他函数进行了 100,000 次迭代timeit，输出结果如下：
0.11 usec/pass on gen_dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
6.03 usec/pass on find_all_items(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.15 usec/pass on findkeys(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1.79 usec/pass on get_recursively(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.14 usec/pass on find(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.36 usec/pass on dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
所有函数都有相同的搜索针（“logging”）和相同的字典对象，其构造如下：
o = { 'temparature': '50',
'logging': {
'handlers': {
'console': {
'formatter': 'simple',
'class': 'logging.StreamHandler',
'stream': 'ext://sys.stdout',
'level': 'DEBUG'
}
},
'loggers': {
'simpleExample': {
'handlers': ['console'],
'propagate': 'no',
'level': 'INFO'
},
'root': {
'handlers': ['console'],
'level': 'DEBUG'
}
},
'version': '1',
'formatters': {
'simple': {
'datefmt': "'%Y-%m-%d %H:%M:%S'",
'format': '%(asctime)s - %(name)s - %(levelname)s - %(message)s'
}
}
},
'treatment': {'second': 5, 'last': 4, 'first': 4},
'treatment_plan': [[4, 5, 4], [4, 5, 4], [5, 5, 5]]
}
所有函数都提供相同的结果，但时间差异很大！该函数gen_dict_extract(k,o)是我从此处的函数改编而来的，实际上它非常类似于findAlfe 的函数，主要区别在于，我正在检查给定的对象是否具有 iteritems 函数，以防在递归期间传递字符串：
# python 2
def gen_dict_extract(key, var):
if hasattr(var,'iteritems'): # hasattr(var,'items') for python 3
for k, v in var.iteritems(): # var.items() for python 3
if k == key:
yield v
if isinstance(v, dict):
for result in gen_dict_extract(key, v):
yield result
elif isinstance(v, list):
for d in v:
for result in gen_dict_extract(key, d):
yield result
因此，此变体是此处最快且最安全的函数。 和find_all_items非常慢，与第二慢的函数相差甚远get_recursivley，而除 之外的其余函数dict_extract彼此接近。fun和函数keyHole仅在您查找字符串时才有效。
这里有有趣的学习方面:)
解决方案 2：
d = { "id" : "abcde",
"key1" : "blah",
"key2" : "blah blah",
"nestedlist" : [
{ "id" : "qwerty",
"nestednestedlist" : [
{ "id" : "xyz", "keyA" : "blah blah blah" },
{ "id" : "fghi", "keyZ" : "blah blah blah" }],
"anothernestednestedlist" : [
{ "id" : "asdf", "keyQ" : "blah blah" },
{ "id" : "yuiop", "keyW" : "blah" }] } ] }
def find(field_name, d, current_path=''):
if not isinstance(d, dict):
return
if field_name in d:
yield current_path
for k in d:
if isinstance(d[k], list):
index = 0
for array_element in d[k]:
for j in find(field_name, array_element, current_path + f'.{k}.[{index}]'):
yield j
index += 1
elif isinstance(d[k], dict):
for found in find(field_name, d[k], current_path + f'.{k}'):
yield found
>>> list(find('id', d))
['', '.nestedlist.[0]', '.nestedlist.[0].nestednestedlist.[0]', '.nestedlist.[0].nestednestedlist.[1]', '.nestedlist.[0].anothernestednestedlist.[0]', '.nestedlist.[0].anothernestednestedlist.[1]']
解决方案 3：
d = { "id" : "abcde",
"key1" : "blah",
"key2" : "blah blah",
"nestedlist" : [
{ "id" : "qwerty",
"nestednestedlist" : [
{ "id" : "xyz", "keyA" : "blah blah blah" },
{ "id" : "fghi", "keyZ" : "blah blah blah" }],
"anothernestednestedlist" : [
{ "id" : "asdf", "keyQ" : "blah blah" },
{ "id" : "yuiop", "keyW" : "blah" }] } ] }
def findkeys(node, kv):
if isinstance(node, list):
for i in node:
for x in findkeys(i, kv):
yield x
elif isinstance(node, dict):
if kv in node:
yield node[kv]
for j in node.values():
for x in findkeys(j, kv):
yield x
print(list(findkeys(d, 'id')))
解决方案 4：
def find(key, value):
for k, v in value.items():
if k == key:
yield v
elif isinstance(v, dict):
for result in find(key, v):
yield result
elif isinstance(v, list):
for d in v:
for result in find(key, d):
yield result
编辑：@Anthon 注意到这不适用于直接嵌套列表。如果您的输入中包含此内容，则可以使用以下内容：
def find(key, value):
for k, v in (value.items() if isinstance(value, dict) else
enumerate(value) if isinstance(value, list) else []):
if k == key:
yield v
elif isinstance(v, (dict, list)):
for result in find(key, v):
yield result
但我认为原始版本更容易理解，所以我将保留它。
解决方案 5：
pip install nested-lookup
正是您想要的：
document = [ { 'taco' : 42 } , { 'salsa' : [ { 'burrito' : { 'taco' : 69 } } ] } ]
>>> print(nested_lookup('taco', document))
[42, 69]
解决方案 6：
我只是想通过使用yield from和接受顶级列表来迭代@hexerei-software 的优秀答案。
def gen_dict_extract(var, key):
if isinstance(var, dict):
for k, v in var.items():
if k == key:
yield v
if isinstance(v, (dict, list)):
yield from gen_dict_extract(v, key)
elif isinstance(var, list):
for d in var:
yield from gen_dict_extract(d, key)
解决方案 7：
另一种变体，其中包括找到的结果的嵌套路径（注意：此版本不考虑列表）：
def find_all_items(obj, key, keys=None):
"""
Example of use:
d = {'a': 1, 'b': 2, 'c': {'a': 3, 'd': 4, 'e': {'a': 9, 'b': 3}, 'j': {'c': 4}}}
for k, v in find_all_items(d, 'a'):
print "* {} = {} *".format('->'.join(k), v)
"""
ret = []
if not keys:
keys = []
if key in obj:
out_keys = keys + [key]
ret.append((out_keys, obj[key]))
for k, v in obj.items():
if isinstance(v, dict):
found_items = find_all_items(v, key, keys=(keys+[k]))
ret += found_items
return ret
解决方案 8：
此函数以递归方式搜索包含嵌套字典和列表的字典。它构建一个名为 fields_found 的列表，其中包含每次找到字段时的值。'field' 是我在字典及其嵌套列表和字典中寻找的键。
def get_recursively(search_dict, field):
"""Takes a dict with nested lists and dicts,
and searches all dicts for a key of the field
provided.
"""
fields_found = []
for key, value in search_dict.iteritems():
if key == field:
fields_found.append(value)
elif isinstance(value, dict):
results = get_recursively(value, field)
for result in results:
fields_found.append(result)
elif isinstance(value, list):
for item in value:
if isinstance(item, dict):
more_results = get_recursively(item, field)
for another_result in more_results:
fields_found.append(another_result)
return fields_found
解决方案 9：
glom是一个很棒的搜索和重构库，还可以使用 glob 进行嵌套查找。示例：
In [1]: import glom
In [2]: data = { "id" : "abcde", "key1" : "blah", ... } # OP example
In [3]: glom.glom(data, '**.id')
Out[3]: ['abcde', 'qwerty', 'xyz', 'fghi', 'asdf', 'yuiop']
嵌套级别用点分隔（将它们视为 Unix 全局变量中的斜线），单星号表示一层的占位符，双星号表示多层的占位符。在上面的例子中，**.id表示“id任何层上的键”。更多示例：
In [4]: glom.glom(d, ('*.*.id', glom.Flatten()))
Out[4]: ['qwerty']
这将仅遍历第三级的所有键并提取的值id，而空结果将被丢弃（嵌套结果列表被展平）。
id另一个仅收集列表中特定值的示例anothernestednestedlist：
In [5]: glom.glom(d, ('nestedlist', [('anothernestednestedlist', ['id'])]))
Out[5]: [['asdf', 'yuiop']]
但是，该库的功能远不止这些。请阅读glom文档了解更多功能。
解决方案 10：
我无法让这里发布的解决方案立即可用，所以我想写一些更灵活的东西。
下面的递归函数应该允许您在任意深度嵌套的字典和列表中收集满足给定键的某些正则表达式模式的所有值。
import re
def search(dictionary, search_pattern, output=None):
"""
Search nested dictionaries and lists using a regex search
pattern to match a key and return the corresponding value(s).
"""
if output is None:
output = []
pattern = re.compile(search_pattern)
for k, v in dictionary.items():
pattern_found = pattern.search(k)
if not pattern_found:
if isinstance(v, list):
for item in v:
if isinstance(item, dict):
search(item, search_pattern, output)
if isinstance(v, dict):
search(v, search_pattern, output)
else:
if pattern_found:
output.append(v)
return output
如果您想搜索特定术语，您可以始终将搜索模式设置为类似r'some_term'。
解决方案 11：
以下是我对此的尝试：
def keyHole(k2b,o):
# print "Checking for %s in "%k2b,o
if isinstance(o, dict):
for k, v in o.iteritems():
if k == k2b and not hasattr(v, '__iter__'): yield v
else:
for r in keyHole(k2b,v): yield r
elif hasattr(o, '__iter__'):
for r in [ keyHole(k2b,i) for i in o ]:
for r2 in r: yield r2
return
前任。：
>>> findMe = {'Me':{'a':2,'Me':'bop'},'z':{'Me':4}}
>>> keyHole('Me',findMe)
<generator object keyHole at 0x105eccb90>
>>> [ x for x in keyHole('Me',findMe) ]
['bop', 4]
解决方案 12：
跟进@hexerei 软件的回答和@bruno-bronosky 的评论，如果您想遍历键列表/集合：
def gen_dict_extract(var, keys):
for key in keys:
if hasattr(var, 'items'):
for k, v in var.items():
if k == key:
yield v
if isinstance(v, dict):
for result in gen_dict_extract([key], v):
yield result
elif isinstance(v, list):
for d in v:
for result in gen_dict_extract([key], d):
yield result
请注意，我传递的是一个包含单个元素 ([key]} 的列表，而不是字符串键。
解决方案 13：
由于Python 中存在最大递归深度，因此我会考虑实现任意大小的迭代方法：
def get_ids(data: Dict, key: str) -> List:
stack = [data]
result = []
while stack:
elem = stack.pop()
if isinstance(elem, dict):
for k, v in elem.items():
if k == key:
result.append(v)
if isinstance(elem, (list, dict)):
stack.append(v)
elif isinstance(elem, list):
for obj in elem:
stack.append(obj)
return result
解决方案 14：
简介
得益于 Python 十年的演进（致力于 3.11），在对投票最多的解决方案发表评论后，我开发了一个变体，事后我意识到它遵循了许多提议解决方案的步骤。不过，我的目标是从深度和广度两方面为响应添加背景信息。
XPath 解决方案
我的解决方案不仅为找到的节点提供了一种 XPath，还根据需要提供了周围的上下文。为此，它接受一个可迭代的键，与目标键一起输出。显然，它提供了key: value字典元素，以提高可读性：
def extract(var, key, context_keys=(), xpath=''):
if isinstance(var, dict):
if key in var:
yield {f'{xpath}.{key}': var[key]} | {f'{xpath}.{key}': value for key, value in var.items() if key in context_keys}
for subkey, value in var.items():
yield from extract(value, key, context_keys, f'{xpath}.{subkey}')
elif isinstance(var, list):
for i, elem in enumerate(var):
yield from extract(elem, key, context_keys, f'{xpath}[{i}]')
通过此查找'id'可以检索到：
[
{
".id": "abcde"
},
{
".nestedlist[0].id": "qwerty"
},
{
".nestedlist[0].nestednestedlist[0].id": "xyz"
},
{
".nestedlist[0].nestednestedlist[1].id": "fghi"
},
{
".nestedlist[0].anothernestednestedlist[0].id": "asdf"
},
{
".nestedlist[0].anothernestednestedlist[1].id": "yuiop"
}
]
显然，由于所有键都代表不同的 XPath，我们可以将条目统一到一个字典中，使用reduce或理解，得到如下结果：
{
".id": "abcde",
".nestedlist[0].id": "qwerty",
".nestedlist[0].nestednestedlist[0].id": "xyz",
".nestedlist[0].nestednestedlist[1].id": "fghi",
".nestedlist[0].anothernestednestedlist[0].id": "asdf",
".nestedlist[0].anothernestednestedlist[1].id": "yuiop"
}
上下文可以用于这样的情况：
>>> pp(reduce(lambda acc, elem: acc | elem, extract(d, 'id', 'keyA')))
{
".id": "abcde",
".nestedlist[0].id": "qwerty",
".nestedlist[0].nestednestedlist[0].id": "xyz",
".nestedlist[0].nestednestedlist[0].keyA": "blah blah blah", # <-- HERE
".nestedlist[0].nestednestedlist[1].id": "fghi",
".nestedlist[0].anothernestednestedlist[0].id": "asdf",
".nestedlist[0].anothernestednestedlist[1].id": "yuiop"
}
我正在研究一种解决方案，返回一个具有与原始结构相同的对象，但只包含所需的键。如果我让它工作，我会在这里添加它。
相关推荐
热门文章
项目管理软件有哪些？
- 2024年20款好用的项目管理软件推荐，项目管理提效的20个工具和技巧
- 2024年开源项目管理软件有哪些？推荐5款好用的项目管理工具
- 2024年常用的项目管理软件有哪些？推荐这10款国内外好用的项目管理工具
- 项目管理软件有哪些？推荐7款超好用的项目管理工具
- 项目管理软件有哪些最好用？推荐6款好用的项目管理工具
- 项目管理软件哪个最好用？盘点推荐5款好用的项目管理工具
- 项目管理软件有哪些，盘点推荐国内外超好用的7款项目管理工具
- 项目管理软件排行榜：2024年项目经理必备5款开源项目管理软件汇总
- 2024项目管理软件排行榜（10类常用的项目管理工具全推荐）
- 项目管理必备:盘点2024年13款好用的项目管理软件
热门标签
云禅道AD
