Python - 高效解析扁平字符串为嵌套字典

Question

Python - 高效解析扁平字符串为嵌套字典

3

我正在从专有数据库获取目录和项列表。这些列表可能非常庞大，包含数千个视图和各种嵌套。以下是列表示例：

"MIPK",
"MIPK\/CM.toroidal",
"MIPK\/CM.Supervoid",
"MIPK\/DORAS",
"MIPK\/DORAS\/CRUDE",
"MIPK\/DORAS\/CRUDE\/CM.forest",
"MIPK\/DORAS\/CRUDE\/CM.benign",
"MIPK\/DORAS\/CRUDE\/CM.dunes",
"MIPK\/DORAS\/COMMODITIES",
"MIPK\/DORAS\/COMMODITIES\/CRUDE",
"MIPK\/DORAS\/COMMODITIES\/CRUDE\/CM.tangeant",
"MIPK\/DORAS\/COMMODITIES\/CRUDE\/CM.astral",
"MIPK\/DORAS\/COMMODITIES\/CRUDE\/CM.forking"

目录使用大写字母 \/ 分隔，大小写混合表示项目。

我的当前返回的 JSON 如下：

    {
    "contents": [{
        "root_path": "MIPK",
        "root_name": "MIPK",
        "directories": [{
            "subd_name": "DORAS",
            "subd_path": "MIPK.DORAS"
        }],
        "views": [{
                "view_name": "CM.toroidal"
            },
            {
                "view_name": "CM.Supervoid"
            }
        ]
    }, {
        "root_path": "MIPK.DORAS",
        "root_name": "DORAS",
        "directories": [{
                "subd_name": "CRUDE",
                "subd_path": "MIPK.DORAS.CRUDE"
            },
            {
                "subd_name": "COMMODITIES",
                "subd_path": "MIPK.DORAS.COMMODITIES"
            }
        ],
        "views": []
    }, {
        "root_path": "MIPK.DORAS.CRUDE",
        "root_name": "CRUDE",
        "directories": [],
        "views": [{
                "view_name": "CM.forest"
            },
            {
                "view_name": "CM.benign"
            },
            {
                "view_name": "CM.dunes"
            }
        ]
    }, {
        "root_path": "MIPK.DORAS.COMMODITIES",
        "root_name": "COMMODITIES",
        "directories": [{
            "subd_name": "CRUDE",
            "subd_path": "MIPK.DORAS.COMMODITIES.CRUDE"
        }],
        "views": []

    }, {
        "root_path": "MIPK.DORAS.COMMODITIES.CRUDE",
        "root_name": "CRUDE",
        "directories": [],
        "views": [{
                "view_name": "CM.tangeant"
            },
            {
                "view_name": "CM.astral"
            },
            {
                "view_name": "CM.forking"
            }
        ]
    }]

}

当前代码：

import logging
import copy
import time

def fetch_resources(input_resources_list):
    '''
    :return: Json list of dictionaries each dictionary element containing:
    Directory name, directory path, list of sub-directories, list of views

    resource_list is a flattened list produced by a database walk function
    '''

    start = time.time()
    resources = {
        'contents': [{}]
    }

    for item in input_resources_list:
        # Parsing list into usable pieces
        components = item.rsplit('\\', 1)

        if len(components) == 1:
            # Handles first element
            root_dict = {'root_path': components[0],
                         'root_name': components[-1],
                         'directories': [],
                         'views': []
                         }
            resources['contents'][0].update(root_dict)
        else:
            #  Enumerate resources in list so search by key value can be done and then records can be appended.
            for ind, content in enumerate(copy.deepcopy(resources['contents'])):

                if resources['contents'][ind]['root_path'] == components[0]:
                    # Directories are upper case, adds a new entry if
                    if clean_item.isupper() :
                        root_dict = {'root_path': components[0],
                                     'root_name': components[-1],
                                     'directories': [],
                                     'views': []
                                     }
                        resources['contents'].append(root_dict)
                        sub_dict = {'subd_path': components[0],
                                    'subd_name': components[-1]}
                        resources['contents'][ind]['directories'].append(sub_dict)
                    elif clean_item.isupper() == False :
                        resources['contents'][ind]['views'] \
                            .append({'view_name':components[-1]})
    print 'It took {}'.format((time.time() - start)*1000) 
    return resources

这在小工作负载（大约100-500）上运行良好，但在目标工作负载（000的）上则不是。

如何优化该方法以节省时间？
目前，“枚举”循环为了按“root_path”键值搜索输入列表中的每个项而被重建。是否有更简单的方法来搜索字典列表的键值，并将条目附加到该条目的目录和视图列表中？

- crowgers

2

不要使用嵌套的推导式，用for循环语句编写代码可能会更清晰易懂，也不会那么难以正确实现。并非所有东西都必须尽可能地紧凑。 - abarnert

但与此同时，直接在步行中生成所需内容可能会更容易，而不是使用步行来构建字符串列表，然后尝试解析这些字符串。 - abarnert

此外，如果目录包含子目录，则将其存储为字典，但如果包含文件，则将其存储为列表。如果一个目录同时包含两者，应该怎么办？这是一个错误吗？ - abarnert

针对您的最后一条评论，它们可以包含文件和目录... 我已经在输出格式中添加了解释。如果是这种情况，结构应该是什么样子？ - crowgers

你完全改变了你要求的结构。同时，你展示的结构与你在我的答案评论中所要求的结构完全不同。无论你想要哪种格式，你都可以使用我答案中的基本结构来构建，但是当然有些细节会有所不同，我不能给你可复制和处理你可能询问的所有内容的代码。 - abarnert

我已经更新了评论和问题，以更准确地反映我的需求，并使所需的格式更加规范，正如您提到的存在不一致性。我并不是要为每种情况编写代码，只是想知道如何处理上述情况。非常感谢您迄今为止提供的信息！ - crowgers

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- abarnert · Accepted Answer

您在构建这些字符串时丢失了很多信息。例如，当您看到MIPK\/DORAS时，无法知道它是一个文件（应该只是父目录列表中的一个字符串），还是叶子目录（应该是父目录字典中的一个列表），或者是中间目录（应该是父目录字典中的一个字典）。最好的方法（没有二次嵌套搜索）就是猜测，然后如果您猜错了再进行更改。

此外，有时您的中间目录甚至不会单独显示出来，而只会出现在以后的路径组件中，但其他时候它们确实会出现。因此，有时需要修正的“猜测”将是根本不存在该目录。

最后，如果任何直接包含文件和目录（它应该是字典还是列表）或根本没有任何内容（应该是空字典、空列表还是仅一个字符串？），则所需格式是模棱两可的。

然而，事情似乎是按排序顺序排列的，并且模棱两可的情况似乎并没有真正出现。如果我们可以依赖这两点，我们可以通过查看它是否是前缀或下一个条目来确定某个内容是目录。然后，我们只需读取叶子并将它们放入0个或多个嵌套字典内的列表内的字符串集合中。

因此，首先，我们要迭代路径的相邻对，以便更轻松地进行“它是否是下一个值的前缀？”检查：

output = {}

it1, it2 = itertools.tee(paths)
next(it2)
pairs = itertools.zip_longest(it1, it2, fillvalue='')
for path, nextpath in pairs:
    if nextpath.startswith(path):
        continue

现在我们知道path是一个叶节点，所以我们需要找到要附加它的列表，如果需要的话创建一个新列表，这可能意味着需要递归地创建字典。

components = path.split(r'\/')
d = output
for component in components[:-2]:
    d = d.setdefault(component, {})
d.setdefault(components[-2], []).append(components[-1])

我没有测试过这个方法，但对于非歧义的输入应该能够做正确的事情，如果任何目录既包含文件也包含子目录，或者任何一级目录包含文件，或任何其他歧义情况（除了空目录，将被视为文件），则会引发某种异常。

当然，这有点丑陋，但这是解析一个依赖许多特例规则来处理本来可能会产生歧义的丑陋格式所固有的。