Python中的递归函数:获取特定嵌套项列表的最佳方法

Question

我有一个嵌套字典树.这是一个小提取物,只是为了给你一个想法:

db = {
    'compatibility': {
        'style': {
            'path_to_file': 'compatibility/render/style.py',
            'checksum': {
                '0.0.3':'AAA55d796c25ad867bbcb8e0da4e48d17826e6f9fce',
                '0.0.2': '55d796c25ad867bbcb8e0da4e48d17826e6f9fe606',}}},
    'developer': {
        'render': {
            'installation': {
                'path_to_file': 'developer/render/installation.py',
                'checksum': {
                    '0.0.1': 'c1c0d4080e72292710ac1ce942cf59ce0e26319cf3'}},
            'tests': {
                'path_to_file': 'developer/render/test.py',
                'checksum': {
                    '0.0.1': 'e71173ac43ecd949fdb96cfb835abadb877a5233a36b115'}}}}}

我想获得嵌套在树中的所有字典模块的列表.这样我就能循环列表并测试每个文件的校验和(注意模块可能处于不同的级别,如上例所示).

为此,我编写了以下递归函数.我知道每个模块都有一个"path_to_file"和"checksum"键,所以我用它来测试dict是否是一个模块.请注意,我必须将递归函数包装在另一个保存列表的函数中,以便每次递归函数运行时都不会覆盖该列表.

def _get_modules_from_db(dictionary):
    def recursive_find(inner_dictionary):
        for k, v in inner_dictionary.iteritems():
            if (isinstance(v, dict) and
                    not sorted(v.keys()) == ['path_to_file', 'sha512sum']):
                recursive_find(v)
            else:
                leaves.append(v)
    leaves = []
    recursive_find(dictionary)
    return leaves

这种方法有效,但不得不包装该函数对我来说似乎非常难看.那么,我在Stack Overflow上的专业人士的问题:

是否有更简单(或更好)的方法,你建议实现这一点,而不必包装功能？

Answer 1

首先,你需要换行功能的唯一原因是因为你让recursive_find变异的leaves就地封闭小区,而不是return荷兰国际集团它.有时这是一个有用的性能优化(尽管经常是悲观),有时它不清楚如何做到这一点,但这次它是微不足道的:

def _get_modules_from_db(dictionary):
    leaves = []
    for k, v in dictionary.iteritems():
        if (isinstance(v, dict) and
            not sorted(v.keys()) == ['path_to_file', 'sha512sum']):
            leaves.extend(_get_modules_from_db(v))
        else:
            leaves.append(v)
    return leaves

为了进一步改进:我可能会把它变成一个发生器(至少在3.3+中,yield from在2.7中我可能会想到两次).而且,当我们处于它时,我会将键视图(在3.x中)或set(v)(在2.x中)与一组进行比较,而不是进行不必要的排序(并且没有任何理由.keys()使用set或者sorted),以及使用!=而不是not和==.并且,除非有充分的理由只接受实际dict和dict子类,否则我要么使用它或者使用它collections.[abc.]Mapping.所以:

def _get_modules_from_db(dictionary):
    for k, v in dictionary.items():
        if isinstance(v, Mapping) and v.keys() != {'path_to_file', 'sha512sum'}:
            yield from _get_modules_from_db(v)
        else:
            yield v

或者,将基本情况拉出来,这样您就可以直接在字符串上调用它:

def _get_modules_from_db(d):
    if isinstance(d, Mapping) and d.keys() != {'path_to_file', 'sha512sum'}:
        for v in d.values():
            yield from _get_modules_from_db(v)
    else:
        yield d

我认为这比你的可读性更强一点,它是6行而不是11行(尽管2.x版本将是7行).但是我没有看到你的版本出现任何问题.

如果您不确定如何将3.3+代码转换为2.7/3.2代码:

• 改写yield from eggs为for egg in eggs: yield egg.
• Mapping是collections,而不是collections.abc.
• 用set(v)而不是v.keys().
• 可能使用itervalues而不是values(2.x only).