时间戳

首页 > 解决方案 > 解析列表中也分组的项目

python - 解析列表中也分组的项目

问题描述

我有一个看起来像这样的字典：

{
    "group-1": ["a.b", "c.d", "group-2"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["group-1", "group-2"],
}

字典很大，但很适合记忆（几千个项目）。

我正在尝试解决这些组，以便每个组都获得所有成员的列表。

所以在这种情况下，“解决方案”-dict 将是：

{
    "group-1": ["a.b", "c.d", "e.f"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["a.b", "c.d", "e.f"],
}

因为每组

我不知道如何去做这件事，而不是令人难以置信的低效。

到目前为止，我得到了这样的东西，它不起作用，并且可能是错误的方向：

from pprint import pprint
from collections import defaultdict

def normalize(data):
    group_map = defaultdict(set)

    found_some = True
    while found_some:
        found_some = False
        for k, v in data.items():
            for i in v:
                if "." in i:
                    if i not in group_map[k]:
                        group_map[k].add(i)
                        found_some = True
                else:
                    ....

    return group_map

标签： pythonpython-3.xalgorithm

解决方案

您可以尝试使用递归函数来继续解析元素：

def resolve(d, key):
    for x in d[key]:
        if x in d:
            yield from resolve(d, x)
        else:
            yield x

或者在一行中：

def resolve(d, key):
    return (y for x in d[key] for y in (resolve(d, x) if x in d else [x]))

应用于您的示例：

d = {
    "group-1": ["a.b", "c.d", "group-2"],
    "group-2": ["e.f", "c.d"],
    "group-3": ["group-1", "group-2"],
}
r = {k: sorted(set(resolve(d, k))) for k in d}
# {'group-1': ['a.b', 'c.d', 'e.f'],
#  'group-2': ['c.d', 'e.f'],
#  'group-3': ['a.b', 'c.d', 'e.f']}

请注意，如果您的 dict 非常大，您可能应该添加@functools.lru_cache(None)装饰器以将 memoization 添加到函数中。在这种情况下，您将不得不删除不可散列的d参数（并使用d来自周围分数的 ）。根据引用的“深度”，您可能还必须增加递归限制。当然，如果存在循环依赖关系，这将不起作用（但我认为对于任何其他方法也是如此）。

推荐阅读